Is $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^* , w_1 \neq w_2 \}$ a CFL?

In my opinion it is not since if we want to know the inequality of $w_1$ and $w_2$ we must be aware of their equality and that is not a $CFG$.

  • $\begingroup$ @G.Bach: I don't agree, you cannot check two words for equality with a DFA. Hadi_Amiri: be careful, CFG are not closed under complement $\endgroup$
    – Denis
    Commented Dec 9, 2013 at 13:55
  • $\begingroup$ as far as I know for $ww$, turing machine is the only accpter, but for this case I'm confused, anyway can anyone write a argument ? $\endgroup$
    – Hadi Amiri
    Commented Dec 9, 2013 at 14:14
  • $\begingroup$ What have you tried? We expect you to make a serious effort before asking and to show us what you've tried in the question. $\endgroup$
    – D.W.
    Commented Dec 9, 2013 at 18:34
  • $\begingroup$ I thought that with simple observation we can determine which class this language belong. $\endgroup$
    – Hadi Amiri
    Commented Dec 9, 2013 at 19:16
  • $\begingroup$ @HadiAmiri, No, we expect you to make a serious effort on your own, and to show in the question what you've tried. $\endgroup$
    – D.W.
    Commented Dec 10, 2013 at 7:20

1 Answer 1


This is a CFL, but the complement (with equality) is not. Notice that both the language and the complement become CFL when you mirror one of the two words.

To show that this is a CFL, you can design a PDA that guesses the letter at position $i$ that will be different in $w_1$ and $w_2$. It start by reading the first $i$ letters of $w_1$ and pushing $i$ symbols to the stack up to this letter, and remembers the letter $a$ in $w_1$ at position $i$. Then, it waits to read $c$, and pops the $i$ symbols off the stack. It accepts if the current letter (at position $i$ in $w_2$) is not $a$.

You have to also treat the case of different lengths, but it's not hard, I leave it as exercise ;)


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.