Preservation of Unambiguity and Inherent Ambiguity in Context Free Languages

摘要

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)