# 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 } Commented May 26, 2019 at 6:56
• @Apass.Jack Don't you think it is a duplicate? The change of alphabet is not relevant to the question. Commented May 26, 2019 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) Commented May 26, 2019 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.

• 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? Commented May 26, 2019 at 6:21
• It would be too much trouble. It’s your exercise. 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$$