$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 2


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.