What Are Right- and Left-Linear Grammars?
At a glance
- 1. Find the nonterminal
Check where the single nonterminal appears on the right-hand side of each production.
- 2. Classify the rules
A nonterminal at the right end gives a right-linear rule; one at the left end gives a left-linear rule.
- 3. Check the language
A grammar that consistently follows either form generates a regular language.
Right- and left-linear grammars are restricted forms of context-free grammars. The difference is the position of the nonterminal in each production. This restriction matters because grammars that consistently use either form generate exactly regular languages, while mixing the forms can produce more powerful grammars.
The two forms
A right-linear grammar has productions of the forms
where and are nonterminals and is a string of terminals. The nonterminal, when present, is at the far right. A common special case allows only one terminal at a time: or . An empty right-hand side, written , may also be allowed.
A left-linear grammar instead has productions of the forms
Here the nonterminal, if present, is at the far left. In the one-terminal version, rules include and .
For example, is right-linear, while is left-linear. The rule is neither: the nonterminal is between terminals rather than at an end. Productions with no nonterminal, such as , are permitted in both forms.
A worked example
Consider the language consisting of any number of ’s followed by one :
A right-linear grammar for it is
Each use of adds one at the left, and ends the derivation. For instance,
This derives , and the same pattern derives , , , and so on.
A left-linear grammar for the same language is
The rule places the nonterminal at the left of the terminal string . The rule adds an before the final in the completed string. For example,
where the last step uses . Both grammars generate exactly , though their derivation steps build the string in different ways.
Why both forms generate regular languages
A right-linear grammar can be represented by a finite automaton. Treat each nonterminal as a state. A production such as becomes a transition from state to state on input . A terminal-only production such as can be represented by a transition to a final state; an epsilon production makes the corresponding state final. If a rule emits a string of several terminals, replace it with a chain of transitions through extra states.
The resulting machine has finitely many states and accepts exactly the strings generated by the grammar. Therefore the language is regular. Left-linear grammars also generate regular languages: reversing the direction of the productions gives an equivalent finite-state description (or, equivalently, the reverse of a regular language is regular).
Conversely, every regular language can be described by a right-linear grammar, and also by a left-linear grammar. Thus, with the usual definitions, each grammar form describes precisely the regular languages—not all context-free languages.
Why mixing the forms is different
A grammar with some right-linear rules and some left-linear rules is not necessarily right-linear or left-linear. It can generate a nonregular language. For example, consider
The rule is right-linear, while is left-linear. The grammar generates
Each cycle adds one before the recursive nonterminal and one after it. This language is not regular, so the fact that every individual rule has at most one nonterminal is not enough to make a grammar linear in the right- or left-linear sense. The nonterminal must consistently occur at the same end.
Common mistakes
- Checking only the number of nonterminals: A rule can contain just one nonterminal and still be neither right- nor left-linear, as in .
- Confusing “linear” with “regular”: A linear grammar has at most one nonterminal per production, but it may place that nonterminal between terminals. Linear grammars can generate nonregular context-free languages.
- Assuming the derivation direction determines the type: What matters is where the nonterminal appears on the production’s right-hand side, not whether your derivation seems to build a word from left to right.
- Forgetting epsilon conventions: Some definitions allow epsilon productions freely; others restrict them, especially for the start symbol. This convention does not change the central distinction, but check the definition used in your course or text.
References
- Introduction to Automata Theory, Languages, and Computation — John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman
Spotted an error? Send a correction. Read how we write and check articles in our editorial policy.