Pushdown Automata for Palindrones

Question

So I've found this PDA to accept palindromes in the language {0,1}*.

However, I'm failing to understand how it could could accept '1' or '0'.

In B it can read a 1 or 0 and push the same symbol to the stack and then go to C. However once it's in C, it has nowhere to go as to reach $ in the stack another symbol needs to be read.

Can someone explain how it works?

I'm thinking that in order to accept a single symbol, we would need a transition from B to D => 1,$->ε | 0,$->ε.

Would I be correct?

Thanks :)

Answer 1

You're right. This PDA will not accept 0 or 1 (or, more generally, any odd-length palindrome - do you see why?)

To fix this, I'd recommend adding these transitions from B to C:

0, ε → ε

1, ε → ε

These transitions essentially let you consume a character "for free." If you pick the middle character and the string is a palindrome, great! Then you'll accept. If you pick the wrong character or the string isn't a palindrome, you'll never make it through states C and D without the automaton dying.