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

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?

• Here is a closely related question, find a pushdown automaton for { x#y ∣ x ≠ y } – Apass.Jack May 26 at 6:56
• @Apass.Jack Don't you think it is a duplicate? The change of alphabet is not relevant to the question. – Hendrik Jan May 26 at 9:41
• @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) – Discrete lizard May 26 at 10:24

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.