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?

  • 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

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$.

  • $\begingroup$ We can accept $\{b^n|n\geq 0\}$ by DPDA as well by using enough stack's symbols and states. Consider the DPDA which for $w=\lambda$ has state $q_1$ which pop $S_0$. For odd $n$ it adds one $A$ to the top of the stack and go to $q_2$ and going forward and backward between another state $q_3$ and when the input word finished popping the two last symbols. For $n$ even similar way is possible using another stack symbol $B$. $\endgroup$ – Doralisa Sep 17 '17 at 18:23

Acceptance by empty stack for DPDA is weaker than acceptance by final state, but any regular language can be accepted by a DPDA on empty stack.

Definition of empty stack for DPDA can be defined as follows

$$\mathcal{L}(DPDA)_{EmptyStack}=\{w\in \Sigma^*\;|\;(q_0,w,$)\rightarrow (q,\lambda,\lambda)\}$$

where all transition rules are uniquely determined.

Suppose you have a regular language $L$. Because it is regular you can make a DFA for it. You can improve this DFA to DPDA by adding a stack (that contains one beginning symbol $\$$) and copy all the transition rules (neglecting what about the pop and push of stack by using $\lambda$ and some other symbols). Just for those transitions of DFA which put it in the final state you should consider the top of the stack and pop the last symbols by adding few more states.

Edit: Note that unlike DFA a DPDA can continue its way after reading its input's word is finished. You should Just pay attention when you are adding the rules like $(q_i,\lambda,S)\rightarrow (q_j,\lambda,\lambda)$ you still keep the transition rule deterministic. It is possible by adding more states.


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.