Understanding this PDA for non-palindromes over {0,1}

Question

I found this PDA online that accepts all non-palindromes over {0,1}. However, I can't seem to understand how it would accept, say "01011", and not accept "101101". Can someone help me understand how "01011" reaches the final state, and why "101101" doesn't by running through the states with me?

Source: Source

Answer 1

You can use this Automaton Simulator which has a Debug/Trace feature to help you understand the PDA for non-palindromes. Testing the PDA with pen and paper is a bit more challenging. It is best to first understand the logic behind the PDA.

Algorithm for non-palindromes

We can use the PDA for the language of all palindromes over {a, b} to create a PDA for this language. To change the PDA accepting all palindromes into one that accepts all non-palindromes, we simply insist in the new machine that there is at least one inconsistency between the first and second half of input string n. So the new PDA can essentially be the same, except when we are popping symbols off the stack and matching them with inputs, we must make sure that there is at least one a where there should have been a b or vice versa.

We first mark the bottom of the stack with a $, push the first half of the string (excepting the middle symbol if the string has odd length) onto the stack in $q_1$, guess non-deterministically where the middle of the string is and switch to state $q_2$. If $w^R \ne w$, then at some point there will be a mismatch between what is on the stack and in the input; when this is true, the machine can take the transition from $q_2$ to $q_3$. Otherwise, any match or mismatch of inputs symbols to symbols on the stack is allowed. Finally, the machine accepts when the input is exhausted and the stack is empty.

Reference

PDA simulator for non-palindromes (does not work on mobile)

Trace table for 01011

Input	Stack	State
	[ ]	$q_0$
$\epsilon$	[\$]	$q_1$
0	[\$, 0]	$q_1$
1	[\$, 0, 1]	$q_1$
0	[\$, 0, 1]	$q_2$
1	[\$, 0]	$q_2$
1	[\$]	$q_3$
$\epsilon$	[ ]	$q_4$

PDA ends in an accept state $q_4$.

Trace table for 101101

Since PDA is non-deterministic, I will show the trace table for only 1 path. Basically, the first half of the string is pushed to stack in $q_1$ and then the rest of the inputs causes the PDA to get stuck in $q_2$.

Input	Stack	State
	[ ]	$q_0$
$\epsilon$	[\$]	$q_1$
1	[\$, 1]	$q_1$
0	[\$, 1, 0]	$q_1$
1	[\$, 1, 0, 1]	$q_1$
$\epsilon$	[\$, 1, 0, 1]	$q_2$
1	[\$, 1, 0]	$q_2$
0	[\$, 1]	$q_2$
1	[\$]	$q_2$

PDA ends in a non-accept state $q_2$.