### Solution Found!

# 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.

### Questions & Answers

**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.

**ANSWER:**

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