PDA Example 1: Hopcroft & Ullman's PDA for {ww^R : w in (a + b)*} FINAL STATE // Final State or Empty Stack, this line is not case-sensitive a b // Input Alphabet: alphabet is CASE-SENSITIVE a b Z // Stack Alphabet: alphabet is CASE-SENSITIVE Z // Stack Start Symbol q0 q1 q2 // Machine states (strings): note: alphabet and states are CASE-SENSITIVE q0 // Start State q2 // Set of Final States--can be empty, in which case language is empty or machine accepts by Empty Stack. q0 \ Z q2 Z // transitions: input state, tape symbol, stack symbol, output state, stack output q0 a Z q0 aZ q0 b Z q0 bZ q0 a a q1 \ q0 a a q0 aa q0 a b q0 ab q0 b a q0 ba q0 b b q0 bb q0 b b q1 \ q1 b b q1 \ q1 a a q1 \ q1 \ Z q2 Z end // required, this line is not case-sensitive