Recently, I am studying grammar in automata. And, I have few information about this subject.

I have a grammar with rules $\{S\to ASA, A\to aA, A\to \epsilon\}$.

Is it true if I say that $S\to aASA$ by rules $S\to ASA, A\to aA$?

  • 2
    $\begingroup$ Please, update your question specifying: 1. what is confusing you, 2. what have you tried, 3. that grammar is not regular, perhaps, remove the regular-languages label. $\endgroup$
    – Chaos
    Oct 23 at 8:57
  • $\begingroup$ Although the generated language is regular... $\endgroup$
    – Steven
    Oct 23 at 9:47

1 Answer 1


You are close, but not precise.

Usually one distinguishes between the arrow notation for the rules $A \to aA$ and the notation for derivation in the grammar, that is the application of the rules in strings $ASA\Rightarrow aASA$.

In your example two consecutive rules are applied, and we write $S\Rightarrow ASA \Rightarrow aASA$, or combining steps $S\Rightarrow^* aASA$.

Observe that your grammar will generate the empty language. There are no productions that remove the initial variable $S$.


Your Answer

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

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