[Solved]: Relaxing the stack in a push down automata

Problem Detail: 

Given a non-deterministic push down automata (we define "accept" here using accept states), if we assume any operation popping from the stack and checking if the top of the stack contains some symbol can succeed (i.e. "getting rid" of the stack), we get a non-deterministic finite automata.

If we convert two such PDAs, whose languages recognized are the same, and assuming all states are reachable, to NFAs in this fashion, are the languages recognized by the NFAs still the same?

---

Here's a simple example. Consider the language $\{a^n b^n : n \in \mathbb{N}\}$. Here's one simple PDA for it. The PDA has two states, $q_0,q_1$. When it is in state $q_0$ and it reads the symbol $a$ on the input tape, it pushes $A$ on the stack and remains in state $q_0$. When it reads the symbol $b$ on the input table and the stack is non-empty, it pops whatever is on the stack and moves to state $q_1$. The PDA accepts if the stack is empty at the end of the input string. If we convert this PDA to a NFA, we get a NFA with two states $q_0,q_1$ and transitions $q_0 \stackrel{a}{\to} q_0$, $q_0 \stackrel{b}{\to} q_1$, $q_1 \stackrel{b}{\to} q_1$. This NFA accepts the language $a^* b^*$. There are other ways to build a PDA for the language $\{a^n b^n : n \in \mathbb{N}\}$; if we apply the same conversion to them, does the corresponding NFA always accept the language $a^* b^*$?

Asked By : simonzack

Answered By : D.W.

I think the answer is no, even if we disallow unreachable states.

Consider the language $L$ given by the grammar $S ::= \varepsilon \mid abS \mid aSb$. In this language, every word $w \in L$ has the same number of $a$'s and $b$'s, and every prefix of $w$ has at most as many $b$'s as $a$'s. Also, if $w \in L$ is not empty, then $w$ starts with $a$ and has length $\ge 2$.

First PDA

Here's one PDA that can recognize that grammar. It has two states $q_0,q_1$, and the following transitions:

$q_0 \stackrel{a,\epsilon\to \alpha}{\to} q_0$

$q_0 \stackrel{b,\alpha \to \epsilon}{\to} q_0$

$q_0 \stackrel{\epsilon, \epsilon \to \epsilon}{\to} q_1$.

The state $q_1$ is the accept state, and both states are reachable.

If you convert this to a NFA, then the NFA accepts the language $(a|b)^*$.

Second PDA

Here's another PDA that accepts the language $L$. It has four states $q_0,q_1,q_2,q_3$, and transitions

$q_0 \stackrel{a,\epsilon \to \alpha}{\to} q_1$

$q_1 \stackrel{a,\epsilon\to \alpha}{\to} q_2$

$q_1 \stackrel{b,\alpha \to \epsilon}{\to} q_2$

$q_2 \stackrel{a,\epsilon\to \alpha}{\to} q_2$

$q_2 \stackrel{b,\alpha \to \epsilon}{\to} q_2$

$q_2 \stackrel{\epsilon, \epsilon \to \epsilon}{\to} q_3$

Here $q_0,q_3$ are the accepting states. All states are reachable.

If you convert this to a NFA, it accepts the language $\varepsilon | a (a|b)^*$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18955

3.2K people like this

 Download Related Notes/Documents