Pushdown Automata and Determinism

Let’s consider the following PDA, which accepts the language $L = \{n_b(w) = n_a(w) + 1\mid w \in (a+b)^*\}$.

In the diagram above, we initiated the stack with an $X$, which effectively increments the count of $b$’s in a string accepted by the PDA. Using such a stack “start symbol” can be helpful for other purposes as well.

The following PDA for $L_{eq} = \{n_a(w) = n_b(w) \:|\: w \in (a+b)^* \}$ uses a start symbol, $S$, to know when the stack has “hit bottom” (i.e., when $S$ is at the top of the stack, it is the only symbol on the stack). Furthermore, whenever an $S$ is on the top of the stack in this machine, it means that an equal number of $a$’s and $b$’s have been encountered so far up to that point.

Compare the transitions in state $q_1$ above with those from the first figure for language $L$. The following transitions have replaced $a,\lambda\to X$ from the PDA for the language $L$:

Since $S$ is always on the bottom of the stack in this machine, we know that when it is at the top of the stack, nothing else is on the stack, so we can push an $X$ to account for the symbol $a$ just read. The transition $a,Y \to XY$ is omitted because, like before, $X$'s and $Y$'s do not appear on the stack simultaneously in this PDA. The two replacement transitions mentioned above are equivalent to $a,\lambda\to X$ in that their net effect is to add an $X$ to the stack when reading an ...