# For $\sum = \{ 0,1 \}$, $A$ has strings which contain a $1$ in their middle third, and a $B$ which contain two $1$'s in their middle third [duplicate]

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 ?

• 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$. – Raphael Nov 22 '14 at 10:45
• Problem 2.48 in Sipser, Introduction to the Theory of Computation, 3rd ed. (Both parts nontrivial) – Hendrik Jan Nov 22 '14 at 11:28
• @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. – Harshal Carpenter Nov 23 '14 at 2:44