Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?

Question

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?

Answer 1

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.

Answer 2

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$