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}\}$$

  • $\begingroup$ Both questions have already been answered on this site, perhaps separately. $\endgroup$ – Yuval Filmus Feb 22 '15 at 20:39
  • $\begingroup$ @YuvalFilmus, i see it, but i didnt understand :) maybe it's better consider together. $\endgroup$ – M. holi Feb 22 '15 at 20:40
  • 1
    $\begingroup$ @M.holi If you saw and did not understand, your question should go into that. $\endgroup$ – Raphael Feb 23 '15 at 7:44
  • $\begingroup$ Also, note that CFL is not closed against complement, so even if these two languages were complementary you'd know nothing. $\endgroup$ – Raphael Feb 23 '15 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.

  • $\begingroup$ would you please say some hint why L1 us Context free? $\endgroup$ – M. holi Feb 23 '15 at 6:09
  • $\begingroup$ my main challenge is why the L2 is Not CF, but L1 is. i severally read this link, but my challenge is maintain. $\endgroup$ – M. holi Feb 23 '15 at 6:15
  • $\begingroup$ @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.) $\endgroup$ – Raphael Feb 23 '15 at 7:46
  • $\begingroup$ @is i tais it possible to describe why L2 is not CF? $\endgroup$ – M. holi Feb 23 '15 at 11:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Luke Mathieson Feb 23 '15 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).

  • $\begingroup$ is there any proof for L2 is not CF ? any link ? $\endgroup$ – M. holi Feb 23 '15 at 14:09
  • $\begingroup$ Definitely. It is a common example of a non-CFL. The usual proof is by application of the Pumping Lemma for CFL. $\endgroup$ – Hendrik Jan Feb 23 '15 at 17:35
  • $\begingroup$ no i means there is link for w1cw2 | w1=w2 ? $\endgroup$ – M. holi Feb 23 '15 at 18:50

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.