Regular grammar

Two grammars are called weakly equivalent if they describe the same language.

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 an extended 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: There is a direct one-to-one correspondence between the rules of a (strictly) right-regular grammar and those of a nondeterministic finite automaton, such that the grammar generates exactly the language the automaton accepts.

[3] Hence, the right-regular grammars generate exactly all regular languages.

If mixing of left-regular and right-regular rules is allowed, we still have a linear grammar, but not necessarily a regular one.

For instance, the grammar G with N = {S, A}, Σ = {a, b}, P with start symbol S and rules generates