From the definition I know that regular grammar should be Left/Right Linear (ie it should have variable on Left/Right side of each production rules)

But, my question is why it is mandatory? Can't we have "Grammar which has DFA(Determistic Finite Automata) or NFA be called Regular Grammar"?

S --> SaS | e (e is epsilon/null/lambda) ; This is not a regular grammar as per its original definition, but the above grammar is generating only regular language.

The above grammar can also be written as, S --> aS | e ; which is basically the same.

So why is there such rule for regular grammar?


1 Answer 1


The boring answer is: The phrase "regular grammar" means what it means, because we have decided that it means that. Had we decided it should mean something else, it would mean something else.

That aside, it is of course legitimate to ask whether

Definition A: "A regular grammar is a grammar that is either right-linear or left-linear."

is a better definition than

Definition B: "A regular grammar is a grammar that describes a regular language (which we've already defined, eg via automata."

A very nice aspect of Definition A is we can very easily check whether a given grammar satisfies it or not. We just look at it, and we know. This goes horribly wrong if we were to adopt Definition B. There is no algorithm that takes in a general grammar and tells us whether or not it defines a regular language. The reason for this is that we can translate Turing machines into general grammars, and thus eg produce a grammar that defines a finite language if the given Turing machine halts only for finitely many inputs, and some definitely-not-regular language otherwise.

We also wouldn't get any of the other benefits that right-linear/left-linear grammars give us, such as easy parsing.

  • $\begingroup$ Thanks for the Answer. They could have made Definition A as properties of regular grammar, why make it a definition. $\endgroup$ Dec 11, 2022 at 11:10

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.