(1) If every set in @@@@ is a subset of a* and the empty word belongs to one of them, then 7(@@@@)=7 (@@@@). One consequence is that 7(L) is always principal for L ≤ a*. (2) On the other hand, there is a language L ≤ a*b* such that 7(L) is not principal. (3) There are subsets J and K of a* such that 7(J) @@@@ 7(K) is not principal.

It is shown that there is no “partial algorithm” (effective procedure that may fail to terminate) by which, given a context free grammar, one can always find an unambiguous context free grammar generating the same language if such an unambiguous grammar exists. The argument turns on the degree of unsolvability of the inherent ambiguity problem for context free languages.

Four principal results about ambiguity in languages (i.e., context free languages) are proved. It is first shown that the problem of determining whether an arbitrary language is inherently ambiguous is recursively unsolvable. Then a decision procedure is presented for determining whether an arbitrary bounded grammar is ambiguous. Next, a necessary and sufficient algebraic condition is given for a bounded language to be inherently ambiguous. Finally, it is shown that no language contained in w 1 * w 2 *, each w 1 a word, is inherently ambiguous.

Various elementary operations are studied to find whether they preserve on ambiguity and inherent ambiguity of language (“language” means “context-free language”) The following results are established: 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. Inherent ambiguity is preserved by every generalized sequential machine which is one-to-one on the set of all words. The product (either left or right) of a language and a word preserves both unambiguity and inherent ambiguity. Neither unambiguity nor inherent ambiguity is preserved by any of the following language preserving operations: (a) one state complete sequential machine; (b) product by a two-element set; (c) Init ( L ) = [ u ≠ dur in L for some v ]; (d) Subw ( L ) = [ w ≠ durr in L for some u , v ].

Call a (context-free) language unambiguous if it is not inherently ambiguous. In the absence of evidence to the contrary, the suspicion has arisen that the unambiguous languages might be precisely those languages with context-free complements. The two theorems presented in this paper lay the suspicion to rest by providing (1) an inherently ambiguous language with context-free complement and (2) an unambiguous language without context-free complement. This establishes the independence of inherent ambiguity from complementedness among the context-free languages.

Basic notation in this paper is as in [3]. From [5] and [9] the following additional notation is derived,ϕiis the partial recursive function with indexi, Wiits range. ∅ is the empty set. ‘≡’ denotes isomorphism between sets, ‘≡m’ many-one equivalence, ‘≡T’ Turing equivalence, ‘≦1’ and ‘≦m’ signify one-one and many-one reducibility respectively. ‘Recursive’ is used throughout for ‘general recursive’.