Finding CFG Example 2

For Language $L_2=\{x\in {\Sigma }^{\ast }:{\#}_{11}(x)={\#}_{00}(x)\}$ Define:

• $A_{00}=\{x\in L:\text{ x starts with 0, ends with 0}\}$
• $A_{01}=\{x\in L:\text{ x starts with 0, ends with 1}\}$
• $A_{10}=\{x\in L:\text{ x starts with 1, ends with 0}\}$
• $A_{11}=\{x\in L:\text{ x starts with 1, ends with 1}\}$ Design: We can construct

$$\begin{array}{r}S\to ϵ,A_{00},A_{01},A_{10},A_{11}\end{array}$$

Now for $A_{00}$: There are three cases:

• $A_{00}$ has no second bit
• $A_{00}$ has a second bit as $1$
• $A_{00}$ has a second bit as 0 For these cases:

$$\begin{array}{rl}{A}_{00}\to 0& \text{for A00 has no second bit}\\ A_{00}\to 0A_{10}& \text{ for A00 has second bit as 0}\\ A_{00}\to 0A_{01}{A}_{10}& \text{ for A00 has second bit as 1}\end{array}$$

Now for $A_{01}$: There are three cases:

• $A_{01}$ has a second bit as 1
• $A_{01}$ has a second bit as $0$

$$\begin{array}{rl}{A}_{01}\to 0A_{11}& \text{ for A00 has second bit 1}\\ A_{01}\to 0A_{01}{A}_{11}& \text{ for A00 has second bit 0}\end{array}$$

So on so forth