patternMinor
Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?
Viewed 0 times
papermidfreewithgeqcupthatdeterministiccontextnot
Problem
These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$
cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give no references as to where the proof comes from.
I was wondering, does anybody know of an academic paper or textbook that gives a full proof? I'd love to be able to cite it, but I haven't been able to find one.
cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give no references as to where the proof comes from.
I was wondering, does anybody know of an academic paper or textbook that gives a full proof? I'd love to be able to cite it, but I haven't been able to find one.
Solution
The result is proved in Ginsburg and Greibach, Deterministic context free languages, Inform. Control 9(6), 620–648, 1966, Theorem 4.1 on page 24 (643). However, the proof looks somewhat different.
Context
StackExchange Computer Science Q#12365, answer score: 6
Revisions (0)
No revisions yet.