Problem Detail: I had a homework assignment where I had to build a PDA over the alphabet ${a,b}^*$, accepting $L = {x mid x text{ is even but not a palindrome}}$. I already turned it in, but I know I had it wrong and it’s driving me insane that I can’t figure out this construction. I tried a Cartesian product construction of the following languages and then deselected the accepting states of $L_2$, but I obviously did it wrong: $L_1 = {x mid x text{ is even}}$ $L_2 = {xx^R}$, where $x^R$ denotes $x$ reversed. I kept running into a problem where it would still accept because Palindromes are even and I was basically accepting all even numbers. 
Asked By : Pants
Answered By : Shreesh
The solution is very much similar to PDA for palindromes of even length, except at atleast one place you have mismatched symbols.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/55929 Ask a Question Download Related Notes/Documents
