Regular Grammar

Regular grammar — a type-3 formal grammar in the Chomsky hierarchy; regular grammars define exactly all regular languages, and are therefore equivalent to finite automata and regular expressions. Regular grammars are a subset of context-free grammars.

Defining by a set of rules

A regular grammar can be defined by a set of rules as a left regular grammar or a right regular grammar.

Right regular grammar, or right-linear grammar, — all rules can be in one of the following forms:

1. A → a
2. A → aB
3. A → ε

left regular grammar, or left-linear grammar, — all rules can be in one of the following forms:

1. A → a
2. A → Ba
3. A → ε

where

• uppercase letters (A, B) denote nonterminals from the set N
• lowercase letters (a, b) denote terminals from the set Σ
• ε — the empty string, i.e., a string of length 0

The classes of right and left regular grammars are equivalent — each one alone is sufficient to define all regular languages. Any regular grammar can be converted from left to right form, and vice versa.

The alternative names stem from the fact that these are subclasses of the more general class of linear grammars.

Example

The right regular grammar G, defined by N = {S, A}, Σ = {a, b, c}, P consisting of the following rules:

S → aS

S → bA

A → ε

A → cA

and S is the start symbol. This grammar describes the same language as the regular expression a*bc*.

Limitation

It is essential that the rules be either only left-regular or only right-regular. A combination of the two is not allowed. For example, the context-free language of strings of the form , where is not regular, but is generated by the grammar G, where N = {S, A}, Σ = {a, b}, P consists of the rules

S → aA

A → Sb

S → ε

and S is the start symbol. This grammar contains both left-regular and right-regular rules simultaneously, and therefore is not regular.

See also

• Regular expressions — in the theory of formal languages
• Prefix grammar