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.

enter image description here

  • 1
    $\begingroup$ 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! $\endgroup$ – D.W. Apr 13 '16 at 16:56
  • $\begingroup$ I'll keep that in mind next time thanks! @D.W. $\endgroup$ – Pants Apr 14 '16 at 3:21
  • $\begingroup$ 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. $\endgroup$ – D.W. Apr 14 '16 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.

  • $\begingroup$ I did not expect it to be that simple... Ah lol. $\endgroup$ – Pants Apr 13 '16 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.