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.
    May 26 '19 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$ May 26 '19 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
    May 26 '19 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.

  • $\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
    May 26 '19 at 6:21
  • 1
    $\begingroup$ It would be too much trouble. It’s your exercise. $\endgroup$ May 26 '19 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.