$L_4 = \{x: \#_{1}(x) = 2 \cdot \#_{10}(x) \}$ Find CFG given hints

Question

Attempt:

$S \to A_{00}SA_{11}$

$A_{00} \to 0, 0A_{00}, 0A_{10}$

$A_{01} \to A_{00}1, A_{00}A_{11}, A_{01}1, A_{00}1$

$A_{10} \to 1A_{10}, A_{10}0, 1A_{00}$

$A_{11} \to 1, 1A_{11}, 1A_{01}$

Not sure what I'm doing. Any help is appreciated

Answer 1

It's important to remember that each production rule must produce a string in $L_4$ i.e. a string that has exactly half of its $1$'s followed by a $0$.

For $A_{00}$, we must produce every string that begins and ends with $0$ and that has exactly half of its $1$'s followed by a $0$. Clearly $0$ meets this criteria. Consider a string produced by $A_{00}$. What is it's second character? It could be $1$ or $0$. If it is $1$, then we can write the string as $0A_{10}$. If it is $0$, then we can write the string as $0A_{00}$. $$ A_{00}\longrightarrow 0, \text{ } 0A_{00}, \text{ } 0A_{10} $$

For $A_{01}$, the same logic applies based off of the second character. $$ A_{01}\longrightarrow 0A_{01}, \text{ } 0A_{11} $$

It is more complicated for $A_{10}$ and $A_{11}$.

For $A_{10}$, consider the second to last element of a string produced by $A_{10}$. If it is $0$, then our string is of the form $1...00$ which could then be rewritten $A_{10}0$. Otherwise it is of the form $1...10$. We will split this again into the case $11...10$ and $10...10$ and make arguments about each separately.

A string in our language of the form $10...10$ must be of the form $A_{11}A_{10}$. The simplest way to show this (that I can think of) is through the Intermediate Value Theorem. I can provide further proof upon request. Our other case is strings of the form $11...10$ which we will further break down into $110...10$, which can be produced by $11A_{00}$, and $111...10$ which can be produced by $11A_{11}0$. $$ A_{10}\longrightarrow A_{10}0, \text{ } 11A_{00}, \text{ } 11A_{11}0, \text{ }A_{11}A_{10} $$

For $A_{11}$, we will break down into strings of the form $11...1$ and $10...1$. Nearly the same proof for strings of the form $10...10$ shows that strings of the form $11...1$ can be produced by $A_{10}A_{11}$. We can break down $10...1$ into $10...01$, which can be represented by $1A_{00}1$, and $10...11$, which can be produced by $1A_{01}1$. $$ A_{11}\longrightarrow 1A_{00}1, \text{ } 1A_{01}1, \text{ } A_{10}A_{11} $$