Ambiguity in context free languages
- 1 January 1966
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 13 (1) , 62-89
- https://doi.org/10.1145/321312.321318
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 w 1 * w 2 *, each w 1 a word, is inherently ambiguous.Keywords
This publication has 9 references indexed in Scilit:
- Bounded 𝐴𝐿𝐺𝑂𝐿-like languagesTransactions of the American Mathematical Society, 1964
- Operations Which Preserve Definability in LanguagesJournal of the ACM, 1963
- On The Ambiguity Problem of Backus SystemsJournal of the ACM, 1962
- Two Families of Languages Related to ALGOLJournal of the ACM, 1962
- Note on the boolean properties of context free languagesInformation and Control, 1960
- On certain formal properties of grammarsInformation and Control, 1959
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959
- Three models for the description of languageIEEE Transactions on Information Theory, 1956
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946