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.

Improve this question
$\endgroup$
1
  • $\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, 2013 at 8:14

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Awesome! Thank you so much! I'd seen references to that paper but had trouble finding a PDF copy. $\endgroup$
    – jmite
    May 30, 2013 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, 2013 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, 2013 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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