Contents

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.

See also: Chomsky hierarchy