HiveBrain v1.2.0
Get Started
← Back to all entries
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?

Submitted by: @import:stackexchange-cs··
0
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.

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.