[SOLVED] Design a PDA of all strings of 0's and 1's that are not of the form ww^R

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

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.

Solution

To accept ww^R, you push the symbols of w onto the stack, nondeterministically guess that you have reached the end of w, and then read w^R while popping matching symbols off the stack. The only way this can possibly accept is if your guess was right, and then it will only accept if your string is of the correct form.

To accept everything not of the form ww^R, consider the following:

First, nondeterministically guess about the parity of the input's length. If you guess that that the input has odd length, and you are right, then it is a string in the language since an odd-length string cannot be of the form ww^R. Doing this allows us to focus the other branch on the case of even-length strings not of the required form.
The defining characteristic of even-length strings not of the form ww^R is that for at least one index k from 1 to |w|, it is true that x[k] is not equal to x[2|w|-k+1]. So, we can push w onto the stack, just as a PDA for ww^R would; and we can nondeterministically guess that we have reached the end of w in the same way. However, instead of requiring the input symbols be equal to the top-of-stack symbols, we will pop a stack symbol for any input symbol, and we will further require that at least one of the input symbols does not match its corresponding top-of-stack symbol. We can do this by having two states for the popping phase: the first corresponding to not having encountered at least one mismatch, and the second corresponding to having seen one or more mismatches. Finally, we can accept if we are in the second of these states with no further input symbols and an empty stack.