Context Free Grammar: at least 2 1's, at most 2 0's

Question

Been having some trouble trying to come up with a CFG for this language: all binary strings that contain least 2 1's and at most 2 0's

So far, I've come up with this:

S --> T | 0T | T0 | T0T | 00TT | TT00 | 0T0T | T0T0 | 0TT0 | T00T

T--> 1T | V

V--> 11Z | 1Z1 | Z11

Z--> 1Z | epsilon

I realize this is mostly likely incorrect/redundant, so any feedback would be extremely helpful. Thank you!

Answer 1

Hint

If $L_{i j}$ is the language with at least $i$ $1$s and at most $j$ $0$s

$$\begin{align} L_{2 2} &= 1 \, L_{1 2} \, | \,?\\ ... \\ L_{0 0} &= \,? \end{align}$$

---

Edited to answer the correct question.

Answer 2

Your language is regular, for example it is described by the regular expression $$ 111^* + 111^*01^* + 1^*011^* + 101 + \\ 111^*01^*01^* + 1^*0111^*01^* + 1^*01^*0111^* + 1010 + 1001 + 0101. $$ You can convert this regular expression, or (better) a finite state automaton (deterministic or non-deterministic) accepting the language, into a context-free grammar.

Answer 3

I'll write down some simple productions, and on the right hand side I note the conditions for each non-terminal symbol. For example "A = ≥ 2, ≤ 1" means "A must produce a sequence containing ≥ 2 ones, and ≤ 1 zeroes".

S -> 0A | 1B       A = ≥ 2, ≤ 1. B = ≥ 1, ≤ 2
A -> 0C | 1D       C = ≥ 2, 0. D = ≥ 1, ≤ 1
B -> 0D | 1E       E = ≥ 0, ≤ 2
C -> 1F            F = ≥ 1, 0
D -> 0F | 1G       G = ≥ 0, ≤ 1
E -> 0G | 1E
F -> 1H            H = ≥ 0, 0
G -> 0H | 1G
H -> 1H | eps

We can take some shortcuts for non-terminals that have only one production or are only used once:

S -> 0011H | 01D | 10D | 11E
D -> 01H | 1G
E -> 0G | 1E
G -> 0H | 1G
H -> 1H | eps

Another advantage is that both grammars are unambiguous. For parsing, the first version is in LL(1), which is about the easiest kind of grammar for parsing.