A Direct Proof of the Inherent Ambiguity of a Simple Context-Free Language
- 1 April 1969
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 16 (2) , 256-260
- https://doi.org/10.1145/321510.321517
Abstract
A direct and self-contained proof is given of the inherent ambiguity of the context-free language L = { a i b i c i ∣ i,j > 1} ∪ { a i b i c i ∣ i,j > 1}, which is the solution to an open problem pointed out by Ginsburg.Keywords
This publication has 3 references indexed in Scilit:
- On Context-Free LanguagesJournal of the ACM, 1966
- Ambiguity in context free languagesJournal of the ACM, 1966
- Finite state languagesInformation and Control, 1958