2
$\begingroup$

My first intuition was to take two languages $L_1$ and $L_2$ (symbol $d$ at the end is to fulfill prefix property):

$$L_1 = \{ a^i b^i c^j d : i,j \ge 0 \} \mathrm{\ \ and\ \ } L_2 = \{ a^i b^j c^j d : i,j \ge 0 \}$$

So their union would be: $ L = L_1 \cup L_2 = \{ a^i b^i c^k d : i=j \lor j=k \} $

Then to prove $L$ not even being DCFL (e.g. in similar way as Example 10.1 from "Introduction to Automata Theory, Languages, and Computation" by Hopcroft & Ullman).

Big inconvenience would be the need to include in the proof also the proofs of all other properties (assuming this class is - just as "regular" DCFL - closed under complement etc.)


But I was told that precisely because the question is about DCFL being accepted by empty stack, the proof is actually trivial and could be expressed in just few sentences.

$\endgroup$

1 Answer 1

2
$\begingroup$

Indeed, the requirement that the DPDA accepts by empty stack has some "severe" consequences.

Under the standard definitions, an automaton with empty stack is blocked from further computations, as normally one would pop a stack single symbol at each computational step. As a consequence DPDA languages by empty stack are prefix-free: if the accepted language contains a string $x$ then it will not contain any string $xy$ with $y\neq \varepsilon$.

Now the language $\{a,aa\}$ is an easy counterexample.

$\endgroup$
2
  • $\begingroup$ It hurts me how trivial it is. I was hoping it was something I didn't understood, but no, it's just me being oblivious. Thank you $\endgroup$ May 7, 2021 at 17:24
  • $\begingroup$ @Jorengarenar Haha, don't worry, we all have those moments. $\endgroup$ May 8, 2021 at 15: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.