8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As a note: the slides follow the same argument as the one I use in a related question on Pumping Lemma's for deterministic CFL. (This is a non-pumping argument of course.) $\endgroup$ – Hendrik Jan May 30 '13 at 8:14
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Awesome! Thank you so much! I'd seen references to that paper but had trouble finding a PDF copy. $\endgroup$ – jmite May 30 '13 at 1:32
  • 1
    $\begingroup$ Out of curiosity, how did you find that? Did you just know offhand what paper it was in, or did you search for it somehow? I'm trying to develop my paper-searching abilities... $\endgroup$ – jmite May 30 '13 at 5:10
  • 1
    $\begingroup$ I googled "deterministic context free" and it was one of the top results. The abstract didn't look too promising, but in the introduction they mention this result. $\endgroup$ – Yuval Filmus May 30 '13 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.