Cs · Computer Science

What Are Right- and Left-Linear Grammars?

Published By the 9to5Science editorial team

At a glance

  1. 1. Find the nonterminal

    Check where the single nonterminal appears on the right-hand side of each production.

  2. 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. 3. Check the language

    A grammar that consistently follows either form generates a regular language.

Advertisement

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

A→uBorA→u,A \to uB \qquad\text{or}\qquad A \to u,

where AA and BB are nonterminals and uu 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: A→aBA\to aB or A→aA\to a. An empty right-hand side, written A→εA\to\varepsilon, may also be allowed.

A left-linear grammar instead has productions of the forms

A→BuorA→u.A \to Bu \qquad\text{or}\qquad A \to u.

Here the nonterminal, if present, is at the far left. In the one-terminal version, rules include A→BaA\to Ba and A→aA\to a.

For example, A→aBA\to aB is right-linear, while A→BaA\to Ba is left-linear. The rule A→aBbA\to aBb is neither: the nonterminal is between terminals rather than at an end. Productions with no nonterminal, such as A→abA\to ab, are permitted in both forms.

A worked example

Consider the language consisting of any number of aa’s followed by one bb:

L={anb:n≥0}.L = \{a^n b : n\ge 0\}.

A right-linear grammar for it is

S→aS∣b.S\to aS\mid b.

Each use of S→aSS\to aS adds one aa at the left, and S→bS\to b ends the derivation. For instance,

S⇒aS⇒aaS⇒aab.S\Rightarrow aS\Rightarrow aaS\Rightarrow aab.

This derives aabaab, and the same pattern derives bb, abab, aaabaaab, and so on.

A left-linear grammar for the same language is

S→Ab,A→Aa∣ε.S\to Ab,\qquad A\to Aa\mid\varepsilon.

The rule S→AbS\to Ab places the nonterminal at the left of the terminal string bb. The rule A→AaA\to Aa adds an aa before the final bb in the completed string. For example,

S⇒Ab⇒Aab⇒aab,S\Rightarrow Ab\Rightarrow Aab\Rightarrow aab,

where the last step uses A→εA\to\varepsilon. Both grammars generate exactly a∗ba^*b, 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 A→aBA\to aB becomes a transition from state AA to state BB on input aa. A terminal-only production such as A→aA\to a 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

S→aA∣ε,A→Sb.S\to aA\mid\varepsilon,\qquad A\to Sb.

The rule S→aAS\to aA is right-linear, while A→SbA\to Sb is left-linear. The grammar generates

{anbn:n≥0}.\{a^n b^n : n\ge 0\}.

Each cycle adds one aa before the recursive nonterminal and one bb 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 A→aBbA\to aBb.
  • 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

  1. 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.