Regular grammar
|
|
In computer science a right 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 is a non-terminal in N and a is a terminal in Σ
- A → aB - where A and B are in N and a is in Σ
- A → ε - where A is in N.
In a left regular grammar, all rules obey the forms
- A → a - where A is a non-terminal in N and a is a terminal in Σ
- A → Ba - where A and B are in N and a is in Σ
- A → ε - where A is in N.
An example of a right 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*.
A regular grammar is a left regular or right regular grammar.
The regular grammars describe exactly all regular languages and are in that sense equivalent with finite state automata and regular expressions.
Every regular grammar is a context-free grammar.
Every context-free grammar can be easily rewritten into a form in which only a combination of left regular and right regular rules is used. Therefore, such grammars can express all context-free languages. Regular grammars, which use either left-regular or right-regular rules but not both, can only express a smaller set of languages, called the regular languages. In that sense they are equivalent with finite state automata and regular expressions. (for illustration: the paradigmatic context-free language with strings of the form <math>a^ib^i<math> is generated by the grammar G with N = {S, A}, Σ = {a, b}, P with the rules
- S → aA
- A → Sb
- S → ε
and S being the start symbol. Note that this grammar has both left-regular and right-regular rules and is therefore not regular any more.)
Some textbooks and articles disallow empty production rules, and assume that the empty string is not present in languages.
See also: Chomsky hierarchy
Template:Formal languages and grammarszh:æ£è§„文法
pl:Gramatyka regularna
es:Gramática regular