Examples of PDA

Let’s look at a few examples of pushdown automata that accept the following languages:

• $L = \{wcw^R\;|\;w \in (a+b)^*\}$
• $M = \{ww^R\;|\;w \in (a+b)^*\}$
• $N = \{ a^m b^n \:|\: m <= n <= 2m \}$
• $P = \{n_a(w) = n_b(w) \:|\: w \in (a+b)^* \}$
• $Q = \{n_b(w) = 2n_a(w)\:|\: w \in (a+b)^* \}$
• $R = \{ a^i b^j c^k \:|\: i=j \vee i=k \}$
• $S = \{ a^ib^j \;|\; i \neq j \}$

PDA for palindromes

The following PDA accepts the language $L = \{wcw^R\;|\;w \in (a+b)^*\}$, i.e., odd-length palindromes of $a$'s and $b$'s with a $c$ in the middle.

We push distinct symbols for $a$'s and $b$'s. Once the $c$ is consumed, we expect to find the reversal of the first half of the string in terms of $X$'s and $Y$'s. The minimal string $c$ is accepted, since it does not modify the stack (leaving it empty), and ends in an accepting state.

All the examples so far have been deterministic PDAs—there is no ambiguity as to which transition applies for each input symbol. It is not possible, however, to construct a deterministic PDA (a DPDA) for the language of even-length palindromes, i.e., $M$ ...