Ambiguity in context free languages

ABSTRACT

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 w1*w2*, each w1 a word, is inherently ambiguous.

REFERENCES

• 1: BAR-HILLEEL, PERLES, AND SHAMIR. On forraal properties of simple phrase structure grammars. Z. Phonetik. Sprachwiss. Kommunikationsforsch. 14 (1961), 143-172.
• 2: David G. Cantor, On The Ambiguity Problem of Backus Systems, Journal of the ACM (JACM), v.9 n.4, p.477-479, Oct. 1962 [doi>10.1145/321138.321145]
• 3: CoisKr, N. On certain formal properties of grammars. Inform. Control. 2 (1959), 137- 167.
• 4: Three models for the description of language. IRE Trans. on Information Theory 2 (1956), 113-124.
• 5: AND SCHUTZENBERGER, M. P. The algebraic theory of context-free languages. In Computer Programming and Formal Systems, Braffort and Hirschberg (Eds.), North- Holland Publishing Co., Amsterdam, 1963.
• 6: EVEY, J. The theory and applications of pushdown store machines. Mathematical Linguistics and Automatic Translation, Rep. No. NSF-10, Comput. Lab., Harvard U., 1963.
• 7: Seymour Ginsburg , H. Gordon Rice, Two Families of Languages Related to ALGOL, Journal of the ACM (JACM), v.9 n.3, p.350-371, July 1962 [doi>10.1145/321127.321132]
• 8: 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]
• 9: --- kND SpANIEI, E.H. Bounded ALGOL-like languages. Trans. Amer. Math. ocl 113 (1964), 333-368.
• 10: --- AND . Semigroups, Presburger formulas, and languages. Pacific J. Math., to appear.
• 11: GaIBACR, S.A. Inverses of phrase structure generators. Mathematical Linguistics and Automatic Translation, Rep. No. NSF-11, Comput. Lab., Harvard U., 1963.
• 12: PARIKH, R.. J. Language-generating devices. Quart. Prog. Rep. No. 60, Res. Lab. of Electronics, MIT, Jan. 1961, 199-212.
• 13: PosT, E.L. A variant of a recursively unsolvable problem. Bull. Amer. Math. Soc. 52 (1946), 264-268.
• 14: RABIN, M., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Develop. 3 (1959), 114-125.
• 15: SCHINBRO, S. Note on the Boolean properties of contex free languages. Infor. ContrS (1960), 372-375.

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)

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Languages, Performance, Theory, Verification