Pushdown automaton for complement of { ww | ... }

Problem Detail: 

I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams).

So, I already know that $L = \{ ww \mid w \text{ in } (0,1)^*\}$ is not context free. Since CFL are not closed under complement its complement $L'$ is a CFL. I also read somewhere that any odd word is part of $L'$ (what about even length words?). So a pushdown automaton description could be: read one letter and put into stack, then read next letter and remove previous letter from stack. Do this until the end. If one letter is left in the stack at the end then word is odd length thus accept, else reject?

Asked By : redundant6939

Answered By : Hendrik Jan

You write

So, I already know that $L = \{ww \mid w \in (0,1)*\}$ is not context free. Since CFL are not closed under complement its complement $L'$ is a CFL

Indeed $L'$ is context-free, but your argumentation is ...eeuh... nonsense. Shure, CFL are not closed under complement, meaning there exist context-free languages of which the complement is not context-free. In general however the complement of a CFL can be both CFL or non-CFL. Even if the complement of every CFL would be non-CFL [which is NOT the case] it would NOT follow that the complement of every non-CFL is CFL.

The language $L'$ indeed consists of all strings of odd length (that is a regular language and can be checked without using the stack) plus the strings of even length for which both halves differ. For the latter part see here.

Phrased more explicitly, let $K = \{ xy \mid |x|=|y|, x\neq y \}$ be the language from question 307 linked above. My claim is that $L' = K \cup \{ x \mid |x| \text{ is odd } \}$, as $L$ equals $\{ xy \mid |x|=|y|, x= y \}$. (And so this explains, as you say in your question, why odd and even length strings are treated separately.)

To answer your question how to implement this using a PDA, see the problem I have linked and its answers. A little hint. To check a word is of the form $xy$ with $|x|=|y|$, but $x\neq y$ we must be able to write $x=x_1ax_2$ and $y=y_1by_2$ with $a\neq b$, and both $|x_1|=|y_1|$ and $|x_2|=|y_2|$. Unfortunately we cannot check both length requirements at the same time. We can however test whether $|x_1y_2|= |x_2y_1|$, and that is enough. Essentially we find the matching positions of $a$ and $b$ without expicitly finding the middle of the string. (This is not at all obvious, please make some drawings.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/16753