$w$ such that it contains at least 3 ones, is my approach to the CFG right?

6.6k Views Asked by At

So I was trying to solve the CFG,

$$\{w \in (0,1)^* \mid w \text{ contains at least three 1's}\}$$

My approach:

I decided that a string can begin with a $0$, end with a $0$, it may begin with a $1$, ended with a $1$, begin with a 0 end with a $1$, or begin with a $1$ and end with a $0$.

This culminates to:

$S \to 0S0 \mid 1S0 \mid 0S1 \mid 1S1 \mid 111$

1

There are 1 best solutions below

2
On BEST ANSWER

That is regular, so a grammar is simple to cook up starting from a DFA. Let $A$ stand for no 1 yet, $B$ for one 1, $C$ for two 1, and $D$ for three (or more) 1. Then: $$ \begin{align*} A &\rightarrow 0 A \mid 1 B \\ B &\rightarrow 0 B \mid 1 C \\ C &\rightarrow 0 C \mid 1 D \mid 1 \\ D &\rightarrow 0 D \mid 1 D \mid 0 \mid 1 \end{align*} $$