Regular grammar

In computer science a regular grammar is a formal grammar (N, Σ, P, S) such that all the production rules in P are of one of the following forms:

1. A -> a where A a non-terminal in N and a a terminal in Σ
2. A -> aB where A and B in N and a in Σ
3. A -> ε where A in N.

The second form may also be replaced with A -> Ba.

An example of a regular grammar G with N = {S, A}, Σ = {a, b, c}, P consists 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*.

The regular grammars describe exactly all regular languages and are in that sense equivalent with finite state automata and regular expressions.

Regular grammars are a subclass of context-free grammars

See also: Chomsky hierarchy