Preservation of unambiguity and inherent ambiguity in context-free languages

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].

REFERENCES

• 1: CHrOMSK, N., AND MILLI, G.A. Finite .tate lnguages. Inf. Contr. I (1958), 91-112.
• 2: ---- AND SCnSZENBE(R, M. P. The algebraic theory of context-free languages. Computer Programmincj and Formal Sysem, Y. Braffort and D. Hirschberg (Eds.), Norb,- ttoliand Publishing Co., Amsterdam, 1963, pp. 118-161.
• 3: EIGoT, C. DccisioI problems of finite utomata design and related problems. Tranz. Am Math. Soc. 98 (1961), 21-51.
• 4: Seymour Ginsburg , G. F. Rose, Operations Which Preserve Definability in Languages, Journal of the ACM (JACM), v.10 n.2, p.175-195, April 1963 [doi>10.1145/321160.321167]
• 5: Seymour Ginsburg , Joseph Ullian, Ambiguity in context free languages, Journal of the ACM (JACM), v.13 n.1, p.62-89, Jan. 1966 [doi>10.1145/321312.321318]
• 6: Thomas N. Hibbard , Joseph Ullian, The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages, Journal of the ACM (JACM), v.13 n.4, p.588-593, Oct. 1966 [doi>10.1145/321356.321366]
• 7: PARIKH, R.J. Language-generating devices. Quart. Prog. Rep. No. 60, Res. Lab. of Elec tronies, Massachusetts Institute of Technology, Jan. 1961, pp- 199-212.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Design, Languages, Performance, Theory, Verification