PRESERVATION OF UNAMBIGUITY AND INHERENT AMBIGUITY IN CONTEXT FREE LANGUAGES.
Abstract
Various elementary operations are studied to find whether they preserve unambiguity and inherent ambiguity of languages ('language' means 'context free language'). The following results are established: (1) If L is an unambiguous language and S is a generalized sequential machine then (a) S(L) is an unambiguous language if S is one-to-one on L, and (b) S(-1)(L) is an unambiguous language. (2) Inherent ambiguity is preserved by every generalized sequential machine which is one-to-one on the set of all words. (3) The product (either left or right) of a language and a word preserves both unambiguity and inherent ambiguity. (4) Neither unambiguity nor inherent ambiguity is preserved by any of the following languagepreserving operations: (a) one-state complete sequential machine; (b) product by a two-element set; (c) Init(L) = (u is not equal to E/uv in L for some v); (d) Subw(L) = ( w is not equal to E/uwv in L for some u, v). (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 12, 1965
- Accession Number
- AD0614073
Entities
People
- Joseph Ullian
- Seymour Ginsburg
Organizations
- System Development Corporation