Preservation of unambiguity and inherent ambiguity in context-free languages

Publisher Website
Google Scholar
Abstract
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 ].

This publication has 4 references indexed in Scilit: