AN N2-RECOGNIZER FOR CONTEXT FREE GRAMMARS,

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)

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1967
Accession Number
AD0662633

Entities

People

  • Jay Earley

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Context Free Grammars
  • Grammars
  • Linguistics

Fields of Study

  • Computer science
  • Physics

Readers

  • Computational Linguistics
  • Operations Research

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers