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 ...