Accession Number:

AD0657317

Title:

THE EQUIVALENCE OF CONTEXT LIMITED GRAMMARS TO CONTEXT FREE GRAMMARS

Descriptive Note:

Corporate Author:

SYSTEM DEVELOPMENT CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1967-01-16

Pagination or Media Count:

66.0

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.

Subject Categories:

  • Linguistics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE