PDA for all non-palindromic strings of even length

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.

• The title you have chosen is not very descriptive. Please take some time to improve it; we have collected some advice here. Also, there's a lot of unnecessary white space in that image; how about cropping it, so the actual content in the image can be displayed larger so it's more easily readable? Thank you!
– D.W.
Apr 13, 2016 at 16:56
• I'll keep that in mind next time thanks! @D.W. Apr 14, 2016 at 3:21
• Even better would be to fix it for this question, this time -- no need to wait for the future. You can click the "edit" link under your question to edit it to improve the question. That's the great thing about this site: it makes it easy to edit your posts to improve them so they'll be more likely to be useful to others in the future.
– D.W.
Apr 14, 2016 at 5:42

The solution is very much similar to PDA for palindromes of even length, except at atleast one place you have mismatched symbols.

• I did not expect it to be that simple... Ah lol. Apr 13, 2016 at 16:48