THE EQUIVALENCE OF CONTEXT LIMITED GRAMMARS TO CONTEXT FREE GRAMMARS

Abstract

A grammar G is context limited if there exists a partial ordering on the alphabet of G under which, for every production alpha to beta of G, every letter of alpha is smaller than some letter of beta. It is proved that the languages generated by context limited grammars are just the context free languages. Unambiguity of general grammars is defined and discussed carefully, preparatory to proving that the languages generated by unambiguous context limited grammars are just the unambiguous context free languages.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 16, 1967
Accession Number
AD0657317

Entities

People

  • Thomas N. Hibbard

Organizations

  • System Development Corporation

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Alphabets
  • Ambiguity
  • Automata
  • Computational Science
  • Context Free Grammars
  • Context Sensitive Grammars
  • Contracts
  • Grammars
  • Language
  • Materials
  • Notation
  • Phrase Structure Grammars
  • Production
  • Scientific Research
  • Theses

Readers

  • Analytical Mechanics
  • Computational Linguistics