Accession Number:

AD0662633

Title:

AN N2-RECOGNIZER FOR CONTEXT FREE GRAMMARS,

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1967-09-01

Pagination or Media Count:

21.0

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

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE