# Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones

$$L=\{ w \in \{ 0,1 \} \}$$ where $$w$$ contains at least three ones

Here is one solution for the productions:

$$S \to A1A1A1A$$

$$A \to 1A | 0A | \epsilon$$

However, now I have a question. Could I modify the second rule to be as follows:

$$A \to A1 | A0 | \epsilon$$

What I did was just switch the places of the non-terminals and terminals in the second rule. For most of the words I tried, this grammar also works well. What is the difference between writing $$1A$$ and $$A1$$?

## 2 Answers

Yes, you can safely modify the rules for $$A$$. In this particular case, the order ($$A1$$ vs. $$1A$$) makes no difference in the language generated by your grammar.

The difference is in the way how words are generated (derived) using your grammar.

When the rules for $$A$$ are the former ($$A \to 1A \mid 0A \mid \varepsilon$$, the derivation can be (for example) $$S \Rightarrow A1A1A1A \Rightarrow 0A1A1A1A \Rightarrow 01A1A1A \Rightarrow 011A1A1A \Rightarrow 0111A1A \dots$$.

While in the latter form, the derivation can look like $$S \Rightarrow A1A1A1A \Rightarrow A01A1A1A \Rightarrow 01A1A1A \dots$$

I suggest you need to understand very carefully Chomsky Hierarchy for $$Type-0,Type-1,Type-2,Type-3$$ grammar. Then you perceive all the grammar and production rules, restrictions for respective $$Type.$$

Alone the grammar $$A \rightarrow 1A|0A|\epsilon$$ is under $$Type-3$$ grammar which is known as Right-Linear-Grammar. If you are writing production which is $$Type-3$$ then you could use only one production which either Right-Linear or Left-Linear at a time not the both at same time.

But your written grammar in the question is the grammar which is under $$Type-2$$ that's why it has less restrictions than $$Type-3$$, it's allowed both Right-Linear or Left-Linear at a time or combination of both are allowed.