# Complement and Context Free Surprising

Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free?

$$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$ $$L_{2}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$$

• Both questions have already been answered on this site, perhaps separately. Feb 22, 2015 at 20:39
• @YuvalFilmus, i see it, but i didnt understand :) maybe it's better consider together. Feb 22, 2015 at 20:40
• @M.holi If you saw and did not understand, your question should go into that. Feb 23, 2015 at 7:44
• Also, note that CFL is not closed against complement, so even if these two languages were complementary you'd know nothing. Feb 23, 2015 at 7:48

If two languages $A$, $B$ are complements of each other, then their disjoint union $A \uplus B$ must be the set of all strings $\Sigma^{\ast}$ over the given alphabet $\Sigma$. That is, every string in $\Sigma^{\ast}$ has to be in $A$ or $B$ but not both. So if we want to show that $L_{1} \neq \overline{L_{2}}$, all we have to do is find a string that is either in both or neither.

In this case it's fairly trivial. All strings in $L_{1}$ and $L_{2}$ have a $c$ in them, so pick any string that doesn't have a $c$ it in. For example $\varepsilon$, it's in neither $L_{1}$ nor $L_{2}$.

A construction for a PDA for $L_{1}$ is given here.

As for proving $L_{2}$ is not context free, everything you need is here.

• would you please say some hint why L1 us Context free? Feb 23, 2015 at 6:09
• my main challenge is why the L2 is Not CF, but L1 is. i severally read this link, but my challenge is maintain. Feb 23, 2015 at 6:15
• @M.holi Without you stating what you've tried and where you got stuck, there's no way of helping you. (Intuitively, the difference is that you can easily guess and check a position of difference, but checking equality requires you to remember the whole $w_1$, in order.) Feb 23, 2015 at 7:46
• @is i tais it possible to describe why L2 is not CF? Feb 23, 2015 at 11:18
• @M.holi As Raphael says, the intuitive version is that for $L_2$ you have to remember all of $w_1$ in order to match it against $w_2$, but a PDA only has a stack, so you can only get things in the reverse order. For the formal version, it needs to be proven, a proof using the pumping lemma for context free languages as linked is probably the simplest. If you were hoping for some easy closure property proof, then you're out of luck, $L_1\cup L_2 = \Sigma^{\ast}c\Sigma^{\ast}$ and $L_1\cap L_2 = \emptyset$ are both regular, which tells us nothing. Feb 23, 2015 at 12:13

The intuitive idea is in the quantifiers, but that is not a formal proof.

Nonequality $w_1 \neq w_2$ if there is some position in which both words differ. We can chack this position by guessing it in the first word $w_1$, storing the number on the pushdown, and checking it for $w_2$. According to this "intuition" we have to use nondeterminism, and we cannot use the position on the pushdown more than once.

For equality $w_1=w_2$ we must verify that all positions are equal. There is no good way to do that. A formal proof of this must take into account all possible strategies (not just this intuition).

• is there any proof for L2 is not CF ? any link ? Feb 23, 2015 at 14:09
• Definitely. It is a common example of a non-CFL. The usual proof is by application of the Pumping Lemma for CFL. Feb 23, 2015 at 17:35
• no i means there is link for w1cw2 | w1=w2 ? Feb 23, 2015 at 18:50