PDA Palindrome Checker

Visualizing how a Pushdown Automaton validates palindromes

Interactive PDA Simulator

Case-insensitive, ignores non-alphanumeric

PDA Visualization

Current State: q₀

q₀ q₁ q₂ a,ε→a b,ε→b a,a→ε b,b→ε ε,$→ε

Input Tape

↑

Stack Operations

Stack Contents

$

Operation Log

Operations will appear here...

Theory: PDA for Palindromes

Why PDAs Are Needed

Finite Automata (FA) cannot recognize palindromes because they lack memory. To verify a palindrome, we need to remember the first half of the string to compare with the second half. PDAs extend FAs with a stack, providing the necessary memory capability.

PDA Formal Definition

States (Q): {q₀, q₁, q₂}

Input alphabet (Σ): Any alphanumeric character

Stack alphabet (Γ): Σ ∪ {$} ($ = stack bottom)

Transition function (δ):

  • q₀ → q₀: a,ε→a (push a)
  • q₀ → q₁: ε,ε→ε (switch to compare)
  • q₁ → q₁: a,a→ε (pop and match)
  • q₁ → q₂: ε,$→ε (accept)

Start state: q₀

Accept state: q₂

Algorithm Steps

  1. Input Cleaning: Convert to lowercase and remove non-alphanumeric characters
  2. Push Phase (q₀): Push first half of characters onto stack
  3. Compare Phase (q₁): For odd lengths, skip middle character
  4. Pop & Match: Pop from stack and compare with second half
  5. Acceptance (q₂): If stack only contains $, accept as palindrome

Example Test Cases

Valid Palindromes

  • "racecar"
  • "A man, a plan..."
  • "abba"

Invalid

  • "hello"
  • "abc123"
  • "palindrome"