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$
$\endgroup$
6
-
$\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$– DenisDec 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 AmiriDec 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. ♦Dec 9, 2013 at 18:34
-
$\begingroup$ I thought that with simple observation we can determine which class this language belong. $\endgroup$– Hadi AmiriDec 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. ♦Dec 10, 2013 at 7:20
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
0
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 ;)
