Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 59 ยท Pushdown Automata

PDAs for Palindromes and Reversal Languages

Construct pushdown automata for even palindromes w w^R, odd palindromes, all palindromes and the marked version w c w^R. Includes runnable Python checks.

Palindromes are the showcase example for pushdown automata. A stack reverses whatever you push on it: if you push a, b, b you pop b, b, a. A palindrome reads the same in both directions, so the plan writes itself: push the first half, then pop while reading the second half. The catch is that the machine does not know where the middle is, so it must guess, which is exactly where nondeterminism earns its keep.

Reverse with a stack

Push the first half Every symbol goes on the stack.
Guess the middle An epsilon move switches phase.
Pop and compare Each popped symbol must equal the input.

Accept when only the bottom marker is left.

1 / 2

Even-length palindromes: w w^R

Over {a, b}, L = { w w^R } contains ฮต, aa, abba, baab, and so on. The machine has two phases:

  • Phase 1 (q0): read a symbol x and push it. Whenever it likes, take the ฮต-move into phase 2.
  • Phase 2 (q1): read a symbol x and pop x from the stack; if the top does not equal the input, the branch dies.
  • Accept when the input is finished and $ is on top.
flowchart LR
    P(["q0: push"]) -->|"x, any / xยทany"| P
    P -->|"ฮต, any / any"| Q(("q1: pop"))
    Q -->|"x, x / ฮต"| Q
    Q -->|"ฮต, $ / $"| F((("qf")))

x stands for a or b. The ฮต-edge from q0 to q1 is the guess about where the middle is.

Odd-length palindromes and all palindromes

An odd palindrome has a middle symbol with no partner: aba, abbba. Add a second way to leave phase 1: read a symbol and go to phase 2 without pushing it. Allowing both exits gives the language of all palindromes over {a, b}:

Exit from phase 1 Meaning Rule
ฮต-move even length, middle is between two symbols ฮต, t / t
read x, no push odd length, x is the middle symbol x, t / t
Python Even, odd and all palindromes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every list of mistakes is empty: for all 2047 strings over {a, b} up to length 10, each machine agrees with the Python check. The empty string is an even palindrome (the ฮต-exit fires at once, then ฮต, $ / $ accepts); a single symbol a is an odd palindrome (the read-without-push exit).

Why the machine must be nondeterministic

Imagine reading abba. After ab, are we at the middle of abba or at the quarter point of abbaabba? No finite amount of lookahead can decide it, so the machine launches both guesses and lets the wrong one die when the comparison fails. No deterministic PDA accepts w w^R (see DPDA vs NPDA).

Give the machine a marker and the problem disappears: the language { w c w^R } has a unique middle, the symbol c, so the switch is triggered by input rather than by a guess. The machine below is deterministic and uses acceptance by empty stack, so there is no final state at all.

Python The marked palindrome w c w^R, accepted by empty stack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The stack's start symbol S is replaced by the first letter, so the stack never becomes empty during the first phase. The marker c pops the stack's S only when nothing has been pushed (the string c itself, the empty w).

Variations you may meet

  • Palindromes over a larger alphabet ({0, 1, 2}): loop over more symbols in the rule generator.
  • Palindromes of a given kind: { w w^R : w โˆˆ {a,b}* } is even palindromes; { w x w^R } with one free middle symbol is odd.
  • Reversal languages such as { u v : v = u^R } are the same machine.
  • Non-palindromes are also context-free (a PDA can guess a position where the symbol and its mirror differ), but the complement is not obtained by simply swapping accept states.
  • Squares { w w } are not context-free: a stack gives the wrong order. You need a Turing machine.

Do not confuse w w^R with w w. The first nests (last in, first out) and is context-free. The second crosses: the first letter of the first copy matches the first letter of the second, which needs first-in, first-out access.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does a PDA for w w^R need nondeterminism?

    Nothing in the input marks the middle, so the machine tries every possible switch point in parallel.
  2. 2. What must be added to accept odd-length palindromes as well?

    The middle symbol of an odd palindrome has no partner, so it is read but not pushed.
  3. 3. Why is the language { w c w^R } easier for a PDA than { w w^R }?

    With a unique middle marker, the machine becomes deterministic.
  4. 4. Which language is not context-free?

    w w requires comparing symbols in the same order (first with first), which a stack, being last-in first-out, cannot do.

Summary

  • Push the first half, guess the middle with an ฮต-move, pop while comparing, accept at $.
  • Odd palindromes add an exit that reads the middle symbol without pushing it.
  • A middle marker (w c w^R) removes the guess and gives a deterministic PDA.
  • w w is not context-free: copies are matched in the same order, not the reverse.
  • You will see w w again when we build Turing machines.

Next: Context-sensitive grammars