Encyclopedia > Regular grammar

  Article Content

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

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
East Marion, New York

... 22.2% have children under the age of 18 living with them, 55.9% are married couples living together, 8.2% have a female householder with no husband present, and 32.5% are ...

This page was created in 27.5 ms