PDA for Palindrome Strings

Question

I am studying Automaton Theory for first time and I am having problems to see if I do well some exercises and if I really finish them. For example, one exercises asks to give a PDA for all palindrome strings on $\{a, b\}^*$ and I have thought the following. Every palindrom has in it middle three posibilities:

1. $\varepsilon$ (the empty string) and therefore the palindrome has even long.
2. $a$
3. $b$

The last two possibilities cover odd long palindromes.

Then, by intuition I thought that the following PDA should work, but I am not really sure how to justify it and if I am doing well, so every possible correction or advise would be appreciated. (In my college we denote by bottom symbol of the stack by $z_0$)

Answer 1

The idea is as follows: you keep on pushing stack elements until you reach the middle point. After that, you start popping out the matching elements from the stack and end up with an empty stack. At the same time, the input string also exhausts. Now the main challenge is to figure out the middle position. Here, we take advantage of the power of nondeterminism (in NPDA).

So basically, you have three states $Q = \{q_0, q_1, q_f\}$. Start pushing items into the stack (irrespective of whatever is on top) in state $q_0$, and you remain in the same state. While in $q_1$, you pop matching items from the stack until either the empty stack symbol appears or the end of input string happens. If both of them occur simultaneously, you go to the final state (and accept); otherwise, you are stuck in $q_1$ (and reject). Now we make a transition from $q_0$ to $q_1$ nondeterministically, either consuming null (in the case of even palindromes) or an input alphabet (for odd plaindromes).

Now it is evident that if your input is indeed a palindrome, a sequence of transitions always exists that leads to its acceptance. The power of nondeterminism guides you to make the correct transition from $q_0$ to $q_1$. Whereas if the input is not a palindrome, there is no transition path that misleads to an acceptance (wrongly). This is because of the condition that both end of string and stack emptyness must occur simultaneously.