Right-Linear Grammar

Turkish equivalent: Sağ doğrusal dilbilgisiDomain: Software Engineering

A grammar whose productions contain at most one nonterminal on the right-hand side, placed at the end, and which generates a regular language.

A right-linear grammar commonly uses productions such as

A -> aB
A -> a
A -> ε

When a nonterminal is present on the right-hand side, it appears after the terminal part.

Right-linear grammars generate regular languages. A suitable grammar can therefore be converted into a Finite Automaton, and automaton transitions can be translated back into regular grammar productions.

The conversion procedure and its DFA/NFA context are covered in Automata Theory and Formal Languages.