1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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, 2016 at 16:56
  • $\begingroup$ I'll keep that in mind next time thanks! @D.W. $\endgroup$
    – Pants
    Apr 14, 2016 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, 2016 at 5:42

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ I did not expect it to be that simple... Ah lol. $\endgroup$
    – Pants
    Apr 13, 2016 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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