[Solved]: PDA for all non-palindromic strings of even length

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