HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
w_1cw_2midfreelanguagew_2contextw_1

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#109854, answer score: 6

Revisions (0)

No revisions yet.