Question

Let. $\mathbf{\sum }\mathbf{=}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}$Let${\mathit{C}}_{\mathbf{1}}$ be the language of all strings that contain a 1 in their middle third.

Let ${\mathit{C}}_{\mathbf{2}}$be the language of all strings that contain two 1s in their middle third. So ${\mathit{C}}_{\mathbf{1}}\mathbf{=}\mathbf{\left\{}\mathbf{x}\mathbf{y}\mathbf{z}\mathbf{|}\mathbf{x}\mathbf{,}\mathbf{z}\mathbf{\in }\mathbf{\sum }\mathbf{*}\mathbf{\text{andy}}\mathbf{\in }\mathbf{\sum }\mathbf{\text{*1}}\mathbf{\sum }\mathbf{\text{*,where}}\mathbf{\left|}\mathbf{x}\mathbf{\right|}\mathbf{=}\mathbf{\left|}\mathbf{z}\mathbf{\right|}\mathbf{\ge }\mathbf{\left|}\mathbf{y}\mathbf{\right|}\mathbf{\right\}}$and ${\mathit{C}}_{\mathbf{2}}\mathbf{=}\mathbf{\left\{}\mathbf{x}\mathbf{y}\mathbf{z}\mathbf{|}\mathbf{x}\mathbf{,}\mathbf{z}\mathbf{\in }\mathbf{\sum }\mathbf{*}\mathbf{a}\mathbf{n}\mathbf{d}\mathbf{y}\mathbf{\in }\mathbf{\sum }\mathbf{*}\mathbf{1}\mathbf{\sum }\mathbf{*}\mathbf{1}\mathbf{\sum }\mathbf{*}\mathbf{,}\mathbf{w}\mathbf{h}\mathbf{e}\mathbf{r}\mathbf{e}\mathbf{\left|}\mathbf{x}\mathbf{\right|}\mathbf{=}\mathbf{\left|}\mathbf{z}\mathbf{\right|}\mathbf{\ge }\mathbf{\left|}\mathbf{y}\mathbf{\right|}\mathbf{\right\}}$.

a.Show that ${\mathit{C}}_{\mathbf{1}}$is a CFL.

b. Show that${\mathit{C}}_{\mathbf{2}}$ is not a CFL

Short answer

a.It can be shown that $C_1$is a CFL.

b. It can be shown that $C_2$is not a CFL

Step-by-step solution

Explain Context-free language

Context-free grammar generates context-free grammar. The regular languages are the subset of the context-free languages that are an identical set of languages accepted by pushdown automata.

Step 2:Show that C1is a CFL.

a.

Consider the given,$C_1=\left\{xyz|x,z\in \sum *\text{andy}\in \sum \text{*1}\sum \text{*,where}\left|x\right|=\left|z\right|\ge \left|y\right|\right\}$where $\sum =\{0,1\}$.

Construct the pushdown automata p to determine the language $C_1$. The p can be defined as$(Q,\sum ,\Gamma ,\delta ,q_0,F)$, where .$Q=\{q_0,q_1,q_2\},\sum =\{0,1\},\Gamma =\left\{x\right\},F=\left\{q_2\right\}$

The PDA is as follows,

Thus, the PDA accepts the given language $C_1$.

Therefore, $C_1$is a Context-free Language and it has been proved.

Step 3:Show that C2 is not a CFL.

b.

Consider the given language$C_2$, $C_2=\left\{xyz|x,z\in \sum *andy\in \sum *1\sum *1\sum *,where\left|x\right|=\left|z\right|\ge \left|y\right|\right\}$accepts all the string that has two 1’s in the middle of the string.

Consider the pumping lemma to show that $C_2$is not a context-free language. Assume that $C_2$is a CFL and prove its contradiction by the pumping lemma l.Consider the string ,S that is divided into pieces as$S=abcde$.

• For each $i\ge 0$,$a{b}^{i}c{d}^{i}e\in C_2$
• $\left|bd\right|>0$
  
• $\left|bcd\right|\le l$
  

Where, $a=0^{l+2},b=1,c=0^l,d=1,e=0^{l+2}$. Let $i=1$, after pumping $S=0^{l+2}{10}^2{10}^{l+2}$. The new string $\left|{10}^{l}1\right|\le l$fails, and thus it is not a CFL.

Therefore, the language$C_2$ is not a Context-free language.