[Math] Express $\{w\mid w \text{ contains at least two } 1\text{‘s}\}$ in CFG

context-free-grammar

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.

Best Answer

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$

Related Question