
Accession Number : AD0662633
Title : AN N2RECOGNIZER FOR CONTEXT FREE GRAMMARS,
Corporate Author : CARNEGIEMELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Earley,Jay
Report Date : SEP 1967
Pagination or Media Count : 21
Abstract : An algorithm is described which is a recognizer for any contextfree grammar. It is shown that the bound on the time the algorithm takes to recognize any string with respect to an unambiguous grammar is proportional to n2, where n is the length of the string, that a bound on the time for recognizing any string is proportional to n3, and that a bound on the space required is proportional to n2. (Author)
Descriptors : (*CONTEXT FREE GRAMMARS, *ALGORITHMS), GRAMMARS, LINGUISTICS, SYMBOLS, SCANNING, LANGUAGE, EFFICIENCY, TOPOLOGY, THEOREMS
Subject Categories : Linguistics
Distribution Statement : APPROVED FOR PUBLIC RELEASE