Language $A$ can also be represented as, $$A = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$

Language $B$ can also be represented as, $$B = \{ uvw \mid u,w \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^* 1 \Sigma^*\text{ and, }|u| = |w| \ge |v| \}$$

I have to prove that $A$ is CFL & $B$ is not a CFL.

To prove $A$ is CFL, I have to show that a CFG can be made. I made a CFG for this equation:

$$L = \{ uv \mid u \in \Sigma^*\text{ and, }v \in \Sigma^* 1 \Sigma^*\text{ and, }|u| \ge |v| \}$$ which is, $$ S \to XSX \mid T1 $$ $$ T \to XT \mid X $$ $$ X \to 0 \mid 1 $$

But I am not able to make a perfect CFG for $A$ after much trying although they seem both same ..

Can I prove $B$ is not a CFL maybe by using pumping lemma ?

  • $\begingroup$ There are two questions here. I suggest you check out our reference question and try for yourself. You can repost more specific questions then. (Why do you say, "have to prove"?) Hint: try representing $A$ differently so that it's easy to "see" a grammar. Then think about why the same trick does not work for $B$. $\endgroup$
    – Raphael
    Nov 22, 2014 at 10:45
  • $\begingroup$ Problem 2.48 in Sipser, Introduction to the Theory of Computation, 3rd ed. (Both parts nontrivial) $\endgroup$ Nov 22, 2014 at 11:28
  • $\begingroup$ @Raphael Correct I made it with help from someone :), suppose $A = \{ u1v \mid u,v \in \Sigma^*\text where, |u|=|v| \gt 1 \}$. where, $S \to XSX$ and $X \to 0 | 1 | 0X |1X $. Thanks for reference. $\endgroup$ Nov 23, 2014 at 2:44


Browse other questions tagged or ask your own question.