Context-Free Grammar for {w| w contains at least as many 0's as 1's and |w| >= 2} over the alphabet {0,1}.

Question

I have first created the following CFG for the same number of 0's and 1's:

S → S0S1S | S1S0S | ε

To create more 0's than 1's, do I need to introduce a new variable such as the following?

S → SAS1S | S1SAS | 0A
A → 0A | 0

But it's not working!

Answer 1

The problem with the rule $$S \to SAS1S \mid S1SAS \mid 0A,$$ is that, as soon as a $1$ is introduced, you are automatically spawning many more zeros all around the $1$. For example, you couldn't make the string $001$ with the given rules. Instead, consider creating the rule $S \to \varepsilon$ to allow each $S$ to be replaced with no $0$s (and no $1$s).

The above adjustment means that the string no longer satisfies $|w| \ge 2$, which we now need to address. What we'll need to do is replace $S$ with a new state, and have the starting state feed into it when we're comfortable that at least two symbols will be produced. Here's my suggestion:

\begin{align*} S &\to TAT1T \mid T1TAT \mid 0A \\ T &\to TAT1T \mid T1TAT \mid \varepsilon \\ A &\to 0A \mid 0. \end{align*}