A regular grammar is a context-free grammar in which all rules have no more than two symbols on the right hand side, and nonterminals, if they occur, either always occur as the first symbol, or always as the last. For instance,

  A -> aY
  B -> Zb
  C -> aBB
  D -> bDc

the rules for A and B can occur in regular grammars, but not together; the rules for C and D cannot occur at all.

In a left regular grammar, terminals occur on the left; in a right regular one, they occur on the right.

Regular grammars correspond so closely to finite automata that they can be regarded as a convenient notation for them.

Regular grammars are not as expressive as arbitrary context-free grammars, since they can only express regular languages.

Log in or register to write something here or to contact authors.