3
$\begingroup$

A DPDA which accepts by empty stack cannot accept all Regular Languages? Is it true that the DPDA cannot accept all regular languages?

I am not able to understand this.As per my knowledge DPDA are more powerful than regular languages as they have finite automate and also the stack.So finite automate can handle all the regular languages.So why above statement is true?

$\endgroup$
3
  • 1
    $\begingroup$ Hint: acceptance with final state and acceptance with empty stack are different criteria. They may or may not be equivalent. (It's an easy exercise to show that they are equivalent for NPDA.) $\endgroup$ – Raphael Sep 17 '17 at 17:34
  • 1
    $\begingroup$ The answer might depend on the definition of PDA, as is visible from the two answers. In the classical definition a PDA cannot move on the empty stack. A certain book (I will not mention names) advocates moves on the empty stack, so it is possible to continue computations on empty stack. (Brrr.) $\endgroup$ – Hendrik Jan Sep 17 '17 at 22:47
  • $\begingroup$ Does this also mean that the set of all languages accepted by DPDA with empty stack is proper subset of regular languages? $\endgroup$ – anir Jan 22 '19 at 12:50
6
$\begingroup$

It is the property "accepting by empty stack" what makes the DPDA weaker. If a language $L$ is accepted by a DPDA by empty stack, then $L$ has the prefix property. The following language $L = \{ b^n \mid n \geq 0\}$ clearly does not have prefix property since if $b^k \in L$ then $b^m \in L$ as well for $m < k$. So this language is not accepted by a DPDA by empty stack.

Assume that $w \in L$ and $wv \in L$ and $L$ does not have prefix property. Assume also that $L$ is accepted by some DPDA $M$ by empty stack. Since $w$ is accepted by $M$, there is a computation path from $(q_0, w, S_0)$ to $(q_k, \epsilon, \epsilon)$. Since $M$ is deterministic, the only possible computation for input $wv$ is $(q_0, w, S_0) \Rightarrow^* (q_k, v, \epsilon)$. But $M$ has already had empty stack and so it cannot move further from $(q_k, v, \epsilon)$ and hence does not accept $wv$.


Definition: A language $L$ has prefix property if $w \in L$ implies no proper prefix of $w$ is in $L$.

$\endgroup$
0

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.