Seymour Ginsburg
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].
- 1 CHrOMSK, N., AND MILLI, G.A. Finite .tate lnguages. Inf. Contr. I (1958), 91-112.Google Scholar
- 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.Google Scholar
- 3 EIGoT, C. DccisioI problems of finite utomata design and related problems. Tranz. Am Math. Soc. 98 (1961), 21-51.Google Scholar
- 4 GINGNSUG, ., AND ROSE G.F. Operations which preservo definability in languages J. ACM 10 (1963), 175-195. Google Scholar
- 5 -- aND ULLAN, J. Ambiguity in context-free languages. J. ACM 13 (1966), 6289. Google Scholar
- 6 HIBBAND, T., AND ULIAN, I. The independence of inherent ambiguity from coplementedness among context-free lnguages. In press, J. ACM. Google Scholar
- 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.Google Scholar
Index Terms
- Preservation of unambiguity and inherent ambiguity in context-free languages
Recommendations
The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages
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 ...
Inherent Ambiguity of Languages Generated by Spine Grammars
There have been many arguments that the underlying structure of natural languages is beyond the descriptive capacity of context-free languages. A well-known example is tree adjoining grammars; less common are spine grammars, linear indexed grammars, ...
Bracketed context-free languages
A bracketed grammar is a context-free grammar in which indexed brackets are inserted around the right-hand sides of the rules. The language generated by a bracketed grammar is a bracketed language. An algebraic condition is given for one bracketed ...
Comments