The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages

ABSTRACT

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.

REFERENCES

• 1: GINSBURG, S., AND SPANIR, E. H. Semigroups, Presburger formulas, and languages. Pacific J. Math. 16 (June 1966), 285-296.
• 2: 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]
• 3: Koing, D. Theorie der endlichen und unendlichen Graphen. Chelsea Pub. Co., New York, 1950.
• 4: PAmH, R.J. Language-generating devices. Quart. Prog. Rep. No. 60, Res. Lab. of Electronics, MIT, Jan. 1961, pp. 199-212; reprinted with minor editorial revisions as: On context-free languages, J. ACM I5 (Oct. 1966), 570-581 (this issue).n

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:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory

General Terms:
Languages, Performance, Theory, Verification