Is $\left ( 0+1 \right )^{\ast }-\left \{ www : w \in \left \{ 0,1 \right \}^{\ast } \right \}$ context-free?

If it is what is a grammar generating it?

  • $\begingroup$ I doubt it. Context-free languages are not closed under difference. Moreover $\{www \mid w \in \{0,1\}^*\}$ is not a regular language (If $L$ is context-free and $D$ is regular than $L \setminus D$ is context-free). You should try to use the pumping lemma to prove it isn't context-free though. $\endgroup$
    – Bakuriu
    Nov 16, 2015 at 21:07
  • 2
    $\begingroup$ @Bakuriu Context-free languages aren't closed under difference but (1) that doesn't tell you whether the difference of any two specific context-free languages is context-free and (2) $\{www\mid w\in\{0,1\}^*\}$ isn't even context-free. $\endgroup$ Nov 16, 2015 at 22:31
  • 2
    $\begingroup$ Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out our reference questions, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ Nov 16, 2015 at 22:31
  • 2
    $\begingroup$ IIRC, this works just like the complement of ww. See here, here and here. $\endgroup$
    – Raphael
    Nov 17, 2015 at 8:02
  • $\begingroup$ @DavidRicherby 1)I posted a comment, not an answer 2) That was a small bit of reasoning to conclude that maybe that language isn't cf. and so searching for a grammar may be a waste of time 3) I never stated that that language is context-free, I only stated that it isn't regular and if it were indeed regular than the difference would be cf by closure properties of cf languages, but that's not the case. 4) I stated a possible way to prove that it isn't cf, i.e. trying to apply the pumping lemma. $\endgroup$
    – Bakuriu
    Nov 17, 2015 at 8:34

2 Answers 2


Here is an idea for you to elaborate on. [Edited after Hendrik's comment:] But maybe the idea does not work so well.

Call your language $L$ and consider $L'=L\cap 0^*10^*10^*10^*$. When does a word $w$ of the form $0^a10^b10^c10^d$ belong to $L'$? When $2a\not=b\lor b\not= c\lor c\not=2d$. It seems difficult for a pushdown automaton to read $w$, compare $2a$ with $b$ and then remember enough of $b$ to compare it with $c$. What should one conclude ?!

When trying to show that a language is not context-free, intersecting with a regular language is a reduction that often permits simpler ways of showing what is not context-free in the language at hand. Without such reductions using the pumping lemma can be unnecessarily painful.

  • 1
    $\begingroup$ Ehrm. If your observation on the intersection is right, then that means this is context-free. We can do the union (disjunction) using nondeterminism, and each of the inequalities is easy to check. $\endgroup$ Nov 17, 2015 at 0:55
  • $\begingroup$ @Hendrik: well it seems I confused disjunction and conjunction here :-( $\endgroup$
    – phs
    Nov 17, 2015 at 6:35

What @Raphael says and the following diagram, with $a\neq b$.

But let me be more precise. A string is not of the form $www$ if either its length is not divisible by three or, when it is of length $3n$, then there are two positions exactly $n$ apart that have different letters. Hence the following diagram.

$\underbrace{\dots a}_k \; \underbrace{\dots\dots\dots b}_n\; \underbrace{\dots\dots\dots\dots\dots}_{2n-k}$

To get a language like this we have to do two things: get the lengths of the three segments right, and synchronize the $a\neq b$. As a first step towards a grammar I would consider the segment lengths, and study a related language: $K= \{ a^k b^n c^m \mid m+k=2n \}$. That is, for each $b$ write two $a$'s or two $c$'s, or if these numbers are odd, add one each.

  • $\begingroup$ Is that really an answer.. ^^ $\endgroup$
    – Danny
    Nov 19, 2015 at 9:12
  • $\begingroup$ Perhaps its an invitation to read the comment by Raphael, and to consider how not-$ww$ can be adapted to not-$www$. This is the diagram I drew to convince myself. $\endgroup$ Nov 19, 2015 at 11:11

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.