Q5Theory of Computation
Question
4 marks
Construct a PDA for the language L = {w w^R | w ∈ {a, b}*}.
Answer
PDA using stack to match symmetry.
To recognize even palindromes : (1) Push symbols onto stack non-deterministically. (2) Guess the middle. (3) Pop and match symbols for the second half. (4) Accept on empty stack/tape.