Relaxing the stack in a push down automata

Question

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^*$?

Answer 1

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)^*$.

Answer 2

I think the general answer is no, two PDAs that recognise the same language could yield NFAs that recognise different languages.

We can construct (at least) two PDAs for the empty language (i.e. that don't recognise anything), but have unreachable states. For example, the first can have states $A$ and $B$, with one transition $A \stackrel{a,\alpha\rightarrow\varepsilon}{\longrightarrow}B$, with $B$ as the accept state. The second has states $X$ and $Y$, transition $X \stackrel{b,\alpha\rightarrow\varepsilon}{\longrightarrow}Y$ with $Y$ as an accept state. There is no transition to push $\alpha$ to the stack, so the only transition in both is unusable, so the language of both is $\emptyset$. However removal of the stack makes the transition usable, but the languages are now $\{a\}$ for the first machine and $\{b\}$ for the second.

This basic construction could be done for any language by adding an unusable transition in both that adds a new string to both that differentiates them.

So the interesting question is now do any two PDAs with no unreachable states generating the same language yield via stack removal two NFAs which have the same language?

Answer 3

Your own example has a stack-ignore language $a^*b^*$. Let me answer your question by demonstrating that every context-free language over alphabet $\Sigma$ has a PDA with a stack-ignore language $\Sigma^*$, by building a single state PDA for it.

Start with a CFG for the language. From this we build a one-state PDA that accepts by empty stack using a standard "expand-match" technique. For $A\to \alpha$ in the grammar we add PDA "expand" instruction $(q,\varepsilon,A,q,\alpha)$; pop $A$ push $\alpha$. We also have "match" $(q,a,a,q,\varepsilon)$; read $a$ when $a$ is on top of the stack (and pop it).

Answer 4

You can always build a PDA with just one state for any CFL (just work through building a PDA from a grammar using top-down parsing), the result of your construction will accept essentially anything.