# Let = {0,1}. Let C1 be the language of all strings that

Chapter , Problem 2.48

(choose chapter or problem)

QUESTION:

Let $$\Sigma=\{0,1\}$$. Let $$C_{1}$$ be the language of all strings that contain a 1 in their
middle third. Let $$C_{2}$$ be the language of all strings that contain two 1s in their
middle third. So $$C_{1}=\left\{x y z \mid x, z \in \Sigma^{*} \text { and } y \in \Sigma^{*} 1 \Sigma^{*}\right.$$, where $$|x|=|z| \geq|y|\}$$ and $$C_{2}=\left\{x y z \mid x, z \in \Sigma^{*}\right.$$ and $$y \in \Sigma^{*} 1 \Sigma^{*} 1 \Sigma^{*}$$, where $$|x|=|z| \geq|y|\}$$.

a. Show that $$C_1$$ is a CFL.
b. Show that $$C_2$$ is not a CFL.

QUESTION:

Let $$\Sigma=\{0,1\}$$. Let $$C_{1}$$ be the language of all strings that contain a 1 in their
middle third. Let $$C_{2}$$ be the language of all strings that contain two 1s in their
middle third. So $$C_{1}=\left\{x y z \mid x, z \in \Sigma^{*} \text { and } y \in \Sigma^{*} 1 \Sigma^{*}\right.$$, where $$|x|=|z| \geq|y|\}$$ and $$C_{2}=\left\{x y z \mid x, z \in \Sigma^{*}\right.$$ and $$y \in \Sigma^{*} 1 \Sigma^{*} 1 \Sigma^{*}$$, where $$|x|=|z| \geq|y|\}$$.

a. Show that $$C_1$$ is a CFL.
b. Show that $$C_2$$ is not a CFL.

Let = {0,1}. Let C1 be the language of all strings that contain a 1 in their middle third. Let C2 be the la