Intheoretical computer science andformal language theory, aregular grammar is agrammar that isright-regular orleft-regular.While their exact definition varies from textbook to textbook, they all require that
Every regular grammar describes aregular language.
Aright-regular grammar (also calledright-linear grammar) is a formal grammar (N, Σ,P,S) in which all production rules inP are of one of the following forms:
whereA,B,S ∈N are non-terminal symbols,a ∈ Σ is a terminal symbol, and ε denotes theempty string, i.e. the string of length 0.S is called the start symbol.
In aleft-regular grammar, (also calledleft-linear grammar), all rules obey the forms
The language described by a given grammar is the set of all strings that contain only terminal symbols and can be derived from the start symbol by repeated application of production rules. Two grammars are calledweakly equivalent if they describe the same language.
Rules of both kinds must not be mixed; for example, the grammar with rule set {S→aT,T→Sb, S→ε } is not regular, and describes the language, which is not regular, either.
Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.
Anextended right-regular grammar is one in which all rules obey one of
Some authors call this type of grammar aright-regular grammar (orright-linear grammar)[1] and the type above astrictly right-regular grammar (orstrictly right-linear grammar).[2]
Anextended left-regular grammar is one in which all rules obey one of
An example of a right-regular grammarG withN = {S, A}, Σ = {a, b, c},P consists of the following rules
and S is the start symbol. This grammar describes the same language as theregular 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 grammarG for the same regular expression is given byN = {S, A, B, C}, Σ = {a, b, c}, whereP 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 grammarG withN = {S,A,B,C,D,E,F}, Σ = {0,1,2,3,4,5,6,7,8,9,+,−,.,e}, where S is the start symbol, andP consists of the following rules:
| S → +A | A → 0A | B → 0C | C → 0C | D → +E | E → 0F | F → 0F |
| S → −A | A → 1A | B → 1C | C → 1C | D → −E | E → 1F | F → 1F |
| S → A | A → 2A | B → 2C | C → 2C | D → E | E → 2F | F → 2F |
| A → 3A | B → 3C | C → 3C | E → 3F | F → 3F | ||
| A → 4A | B → 4C | C → 4C | E → 4F | F → 4F | ||
| A → 5A | B → 5C | C → 5C | E → 5F | F → 5F | ||
| A → 6A | B → 6C | C → 6C | E → 6F | F → 6F | ||
| A → 7A | B → 7C | C → 7C | E → 7F | F → 7F | ||
| A → 8A | B → 8C | C → 8C | E → 8F | F → 8F | ||
| A → 9A | B → 9C | C → 9C | E → 9F | F → 9F | ||
| A → .B | C → eD | F → ε | ||||
| A → B | C → ε |
There is a direct one-to-one correspondence between the rules of a (strictly) right-regular grammar and those of anondeterministic finite automaton, such that the grammar generates exactly the language the automaton accepts.[3] Hence, the right-regular grammars generate exactly allregular languages. The left-regular grammars describe the reverses of all such languages, that is, exactly the regular languages as well.
Every strict right-regular grammar is extended right-regular, while every extended right-regular grammar can be made strict by inserting new non-terminals, such that the result generates the same language; hence, extended right-regular grammars generate the regular languages as well. Analogously, so do the extended left-regular grammars.
If empty productions are disallowed, only all regular languages that do not include the empty string can be generated.[4]
While regular grammars can only describe regular languages, theconverse is not true: regular languages can also be described by non-regular grammars.
If mixing of left-regular and right-regular rules is allowed, we still have alinear grammar, but not necessarily a regular one.What is more, such a grammar need not generate a regular language: all linear grammars can be easily brought into this form, and hence, such grammars can generate exactly alllinear languages, including non-regular ones.
For instance, the grammarG withN = {S, A}, Σ = {a, b},P with start symbolS and rules
generates, the paradigmatic non-regular linear language.