THE EQUIVALENCE OF CONTEXT LIMITED GRAMMARS TO CONTEXT FREE GRAMMARS
SYSTEM DEVELOPMENT CORP SANTA MONICA CA
Pagination or Media Count:
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.