patternMinor
Does DPDA accept all regular languages?
Viewed 0 times
alllanguagesacceptregulardpdadoes
Problem
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?
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?
Solution
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$.
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$.
Context
StackExchange Computer Science Q#81309, answer score: 9
Revisions (0)
No revisions yet.