Context: I am trying to construct a context-free grammar (CFG) for the set of all binary strings that contain at least one $1$ and at most two $0$’s.
My solution:
$S \rightarrow A0B0B | B0A0B | B0B0A | A0B | B0A | B$
$A \rightarrow B1|1B$
$B \rightarrow B1 | 1B | \epsilon$
Explanation: $S$ is the start symbol. $A$ generates binary strings that contain only $1$'s, of length at least $1$, so $A$ guarantees that the binary string generated must contain at least one 1. $B$ generates binary strings that contain only $1$s, of length at least $1$ or generates an empty string. Thus, $S$ generates binary strings that contain at least one $1$ (i.e., strings can have more than one $1$) and at most two $0$'s (i.e., strings must have no $0$ or one $0$ or two $0$'s).
However, it seems my solution is incorrect and I am unsure why. From how I constructed the CFG, I thought I covered as many of the cases as possible. I've looked it over many times and I'm not seeing why I'm incorrect. Can someone tell me why my solution is wrong and what I can do to fix it? I tend to struggle when it comes to constructing CFGs and strings, so I've been practicing problems like these. Any feedback or suggestion would be appreciated.
Your grammar generates the empty string. But the empty string does not have at least one '0'.
In fact, the language is a regular language. For consider the set of all strings with at least 1 '1'. This is clearly regular, as we can construct a 2-state deterministic finite state automaton to decide it (with states $\{0, 1\}$, starting state $0$, transitioning from state $i$ to state $\min(1, i + j)$ upon reading a $j$, and with $1$ as the only accepting state).
And consider the set of all strings with at no more than 2 '0's. This again is regular, as we can construct a 4-state machine to decide it (with states $\{0, 1, 2, 3\}$, starting state $0$, transitioning from state $i$ to state $\min(i, i + (1 - j))$ upon reading a $j$, and with $0$ and $1$ as the only accepting states).
We can thus take the intersection of these two languages to get another language which is again regular. Using the DFA construction for the intersection and taking the minimalmachine, we get a 7-state DFA for deciding this language. The corresponding right-grammar is
$S \to A$
$S \to B$
$S \to C$
$A \to 1$
$A \to A1$
$B \to 10$
$B \to A0$
$B \to B1$
$C \to 100$
$C \to B0$
$C \to C1$