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?


1 Answer 1


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.)

  • $\begingroup$ Thanks for the clarification about complement closure. However, I'm not sure I understand how the linked question is related to this one. $\endgroup$ Nov 6, 2013 at 14:57
  • $\begingroup$ But Im interested as to how this can be represented with a PDA. I was reading the formal proof (www2.hawaii.edu/~ztomasze/ics641/ztomaszeA2.pdf) and it said "when generating an even-length string, it is impossible to have the form ww if at least one symbol in the first w substring differs at the same position in the second w substring". Could we put ww into the stack and then compare those two symbols (they are w distance apart)? $\endgroup$ Nov 8, 2013 at 21:45
  • $\begingroup$ @EllieG: Hint: You need non-determinism. $\endgroup$
    – Raphael
    Nov 9, 2013 at 15:03

Your Answer

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

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