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:
- A -> a where A a non-terminal in N and a a terminal in Σ
- A -> aB where A and B in N and a in Σ
- 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