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
Grand Prix

... with ...

 
 
 
This page was created in 36.9 ms