the set of all strings of 0's and 1's that are not of the form ww^R

Question

I have to create a PDA(pushdown automata) that accepts strings that not of the form $ww^R$.

For example it accepts 0011, 1100, 11000 but not accepts 1001, 011110, 0110.

How can I create this PDA? I know the answer of not accepting $ww$, but can't get an insight to make this one.

I would appreciate if you let me know the answer or nice hint to make it.

Answer 1

The PDA that accepts words of the form $\omega \omega ^R$ is built like this:

You read the numbers and write them on the stack and in the middle of the word you change non deterministicly (this transition is $\epsilon \to \epsilon$ and doesn't write nothing on the stack) to a state where you read the numbers from the stack, what you do in reverse order.

To build the PDA that accpets the complementar of that language you change the accpeting state to a rejecting one and the rejecting states into an accpeting.