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

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!

• Your language is regular, so you can come up with a regular expression or a DFA/NFA for it, and then convert it to a context-free grammar. – Yuval Filmus May 18 '17 at 4:23
• Why does V have three productions? One is enough. And T isn't needed at all. V derives "at least two 1s, no zeroes". T derives "at least two ones, no zeroes". – gnasher729 Jul 18 '17 at 0:03
• Your grammar doesn't derive anything with only one 1 in a row, like 010111111111 or 0111111101. Or two zeroes in the middle, like 10101. Start by writing down what you want to derive from each non-terminal. – gnasher729 Jul 18 '17 at 0:06

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.

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.

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.