Express $\{w\mid w \text{ contains at least two } 1\text{'s}\}$ in CFG

Question

Let $\Sigma = {0, 1}$. Write CFG that generates the following language {w | w contains at least two 1’s}

I'm not really sure how to write a CFG that generates a language, so this is my attempt...

S-> A1A1A

A->0A1|1A0|AA|$\epsilon$

I'm not sure about the start, maybe it should be

S->A1A

A->1A1|1A0|0A1|$\epsilon$

I really don't know what I'm doing, so any pointers for how I can solve this problem (and the next ones I need to solve) would be hugely helpful!

From what I can tell my answers make no sense since I don't really understand what I'm doing. Another example of what I have thought of as a possible solution is:

$S_0 \implies 0S_0 | 1S_1$

$S_1\implies0S_1|1S_2$

$S_2\implies0S_2|1S_2|\epsilon$

but I'm not sure if this works for more than two 1's or if it works at all for that matter.

Answer 1

Your start $A \to A1A1A$ looks good, in that it can only make strings having two 1's and also has room to put arbitrary strings of 0,1 (possibly empty strings) at the beginning, between the 1's, or after the two you have guaranteed. It would seem simpler here to add the rules $A \to 1A|0A|\epsilon$ which would allow the construction of the arbitrary strings at the beginning, between the initial 1's and at the end.

This method of course doesn't give unique derivations.

EDIT The above doesn't work, the A has to switch to B first. So $A\to B1B1B$ and then $B \to 0B|1B|\epsilon.$ The above way allows in other strings without the two guaranteed 1's.

Answer 2

Hint:

• The regular expression for this language is $(\Sigma^*1\Sigma^*1\Sigma^*)$.
• The grammar for the full language is $F \to 0F \mid 1F \mid \ldots \mid \varepsilon$.
• The context-free grammars can be sometimes unbelievably close to regular expressions...

I hope this helps $\ddot\smile$