[Solved]: 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?

Problem Detail: 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.

Asked By : jmite

Answered By : Yuval Filmus

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12365  Ask a Question  Download Related Notes/Documents