Accession Number : AD0662633

Title :   AN N2-RECOGNIZER FOR CONTEXT FREE GRAMMARS,

Corporate Author : CARNEGIE-MELLON 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 context-free 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