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

... in Great Britain, based on a perceived similarity to young birds vainly trying to leave the nest. While many in the United States assumed at the time that the term ...

This page was created in 32.4 ms