[Math] For $\Sigma = \{ 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.

automatacontext-free-grammar

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 ?

Best Answer

18 April 2022: The answer given for $A$ was absurd, and I’ve deleted it.

9 May 2022: I’ve now added a correct answer in the blockquote below.

Consider the context-free grammar with initial symbol $S$ and the following productions:

$$\begin{align*} S&\to XLX\mid XRX\\ L&\to XLXX\mid C\mid 1\\ R&\to XXRX\mid C\mid 1\\ C&\to XCX\mid 1\\ X&\to 0\mid 1 \end{align*}$$

  • Show that the derivations that begin with the production $S\to XLX$ generate $$\{u1v\in\Sigma^*:|u|\le|v|<2|u|\}\,,\tag{1}$$ and those that begin with the production $S\to XRX$ generate $$\{u1v\in\Sigma^*:|v|\le|v|<2|v|\}\,.\tag{2}$$

  • Show that $(1)$ is the set of strings $w=u1v\in\Sigma^*$ such that the indicated $1$ is in the middle third of $w$, and $|u|\le|v|$, and $(2)$ is the set of strings $w=u1v\in\Sigma^*$ such that the indicated $1$ is in the middle third of $w$, and $|v|\le|u|$. Clearly $A$ is the union of these two sets.

To show that $B$ is not context-free, use the pumping lemma with the word $s=0^{p+2}10^p10^{p+2}$, where $p$ is the pumping length. You’ll have $s=uvwxy$, where $|vwx|\le p$, $|vx|\ge 1$, and $uv^kwx^ky\in B$ for all $k\ge 0$, and you’ll have to consider several cases according to the possible decompositions of $s$. Note that since $|vwx|\le p$, at most two of the strings of $0$s can be pumped.

Related Question