Is the language $L_1 = \{w_1cw_2 ~|~ w_1,w_2 \in \{a,b\}^{\ast} \text{ and } w_1 \neq w_2\}$ a context-free language?

It certainly isn't regular, but is it context free?

I'm having trouble creating a grammar that creates terminal symbols from the outside-in; Is there anything to look for explicitly that tells me it is/isn't CF?

And if it was in fact context-free, how would I go about proving that?

  • 1
    $\begingroup$ Here is a closely related question, find a pushdown automaton for { x#y ∣ x ≠ y } $\endgroup$
    – John L.
    Commented May 26, 2019 at 6:56
  • $\begingroup$ @Apass.Jack Don't you think it is a duplicate? The change of alphabet is not relevant to the question. $\endgroup$ Commented May 26, 2019 at 9:41
  • $\begingroup$ @HendrikJan The other question explicitly asks for a PDA, this one does not, which means another type of proof can be given (which this answer did) $\endgroup$
    – Discrete lizard
    Commented May 26, 2019 at 10:24

2 Answers 2


The idea is that $w_1 \neq w_2$ if and only if either (1) $|w_1| \neq |w_2|$ or (2) the $i$th letters of $w_1,w_2$ are different. This leads to the following partition of $L_1$: $$ \begin{align*} L_1 &= (a+b)^+(a+b)^nc(a+b)^n \\ &\cup (a+b)^nc(a+b)^n(a+b)^+ \\ &\cup (a+b)^na(a+b)^*c(a+b)^nb(a+b)^* \\ &\cup (a+b)^nb(a+b)^*c(a+b)^na(a+b)^* \end{align*} $$ Each of the summands is clearly context-free, hence so is their union.

  • $\begingroup$ I'm having trouble understanding how you partitioned the language. What do the 4 seperate cases represent? Would you be able to make it into a CFG if it isn't too much trouble? $\endgroup$
    – Humdrum
    Commented May 26, 2019 at 6:21
  • 1
    $\begingroup$ It would be too much trouble. It’s your exercise. $\endgroup$ Commented May 26, 2019 at 6:38

Grammar for this language based on @Yuval Filmus's answer:

$S \rightarrow X_{1}$| $X_{2}$|$X_{3}b \Sigma^{*}$|$X_{4}a \Sigma^{*}$

$X_{1} \rightarrow \Sigma X_{1} \Sigma$|$\Sigma^{+} c$

$X_{2} \rightarrow \Sigma X_{2} \Sigma$|$c \Sigma^{+}$

$X_{3} \rightarrow \Sigma X_{3} \Sigma$|$a \Sigma^{*} c$

$X_{4} \rightarrow \Sigma X_{4} \Sigma$|$b \Sigma^{*} c$

$\Sigma^{+} \rightarrow \Sigma \Sigma^{*}$

$\Sigma^{*} \rightarrow a \Sigma^{*}$|$b \Sigma^{*}$|$\epsilon$

$\Sigma \rightarrow a$|$b$


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.