3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Here is a closely related question, find a pushdown automaton for { x#y ∣ x ≠ y } $\endgroup$ – Apass.Jack May 26 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$ – Hendrik Jan May 26 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 at 10:24
4
$\begingroup$

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.

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