Regular grammar

In theoretical computer science and formal language theory, a regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language.

A right regular grammar (also called right linear grammar) is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms:

In a left regular grammar (also called left linear grammar), all rules obey the forms

A regular grammar is a left or right regular grammar.

Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.

An example of a right regular grammar G with N = {S, A}, Σ = {a, b, c}, P consists of the following rules

and S is the start symbol. This grammar describes the same language as the regular expression a*bc*, viz. the set of all strings consisting of arbitrarily many "a"s, followed by a single "b", followed by arbitrarily many "c"s.

A somewhat longer but more explicit extended right regular grammar G for the same regular expression is given by N = {S, A, B, C}, Σ = {a, b, c}, where P consists of the following rules:

…where each uppercase letter corresponds to phrases starting at the next position in the regular expression.

As an example from the area of programming languages, the set of all strings denoting a floating point number can be described by a right regular grammar G with N = {S, A,B,C,D,E,F}, Σ = {0,1,2,3,4,5,6,7,8,9,+,-,.,e}, where S is the start symbol, and P consists of the following rules:

An extended right regular grammar is one in which all rules obey one of

Some authors call this type of grammar a right regular grammar (or right linear grammar) and the type above a strictly right regular grammar (or strictly right linear grammar).

An extended left regular grammar is one in which all rules obey one of

There is a direct one-to-one correspondence between the rules of a (strictly) left regular grammar and those of a nondeterministic finite automaton, such that the grammar generates exactly the language the automaton accepts. Hence, the left regular grammars generate exactly all regular languages. The right regular grammars describe the reverses of all such languages, that is, exactly the regular languages as well.

...
Wikipedia