A left-linear grammar can be turned into an equivalent right-linear grammar by passing through a finite automaton. The grammar is read as a nondeterministic automaton, and that automaton is then written down as new rules. The route matters because both kinds of grammar belong to the world of formal languages and generate the regular languages, yet a conversion that only rearranges symbols changes the language.
What is the difference between a left-linear and a right-linear grammar?
A grammar is linear when every rule has at most one nonterminal on its right-hand side. The two grammar types differ in where that nonterminal stands. In a left-linear grammar it comes first, in rules of the form A → Bw or A → w. In a right-linear grammar it comes last, in rules of the form A → wB or A → w. Here w is a string of terminals, possibly empty, and A and B are nonterminals.
| Grammar | Rule shapes | Example |
|---|---|---|
| Left-linear | A → Bw, A → w | S → Sa | Ab, A → a |
| Right-linear | A → wB, A → w | S → aS | ε |
Names vary. The strict versions with a single terminal per rule are often called left-regular and right-regular, and the definition of a regular grammar differs from textbook to textbook, so the exact rule shapes are worth checking against the course in question.
What is a regular grammar (type 3)?
A regular grammar is a grammar that is consistently left-linear or consistently right-linear. In the right-regular version used here, the rules have the form A → a, A → aB and the empty rule A → ε, where a is a single terminal. The left-regular version mirrors the position of the nonterminal.
Regular grammars sit at type 3 of the Chomsky hierarchy, the lowest level, and they generate exactly the regular languages, which are the languages that finite automata recognize. Some course notes define type 3 with right-linear rules only. This does not lose anything, since a left-regular grammar generates the mirror images of the languages that right-regular grammars generate, and the class of regular languages is closed under reversal, so both forms describe the same class of languages.
That holds for classes of languages, not for single grammars. A left-linear grammar and its mirrored right-linear twin usually generate different languages, which is the reason for the conversion below.
How do you convert a left-linear grammar to a right-linear grammar?
The method builds an automaton whose paths run in the opposite direction to the derivations, because a left-linear derivation adds its terminals to the right of everything already produced. Reading the grammar backwards turns it into an ordinary automaton.
- Create one state for each nonterminal and add a fresh state q0, which becomes the start state.
- Declare the start symbol of the grammar the only accepting state.
- For each rule A → w with only terminals, add an edge from q0 to A labeled w.
- For each rule A → Bw, add an edge from B to A labeled w.
- Read the automaton as a right-linear grammar: an edge from P to Q labeled a becomes the rule P → aQ, and an accepting state F gets the rule F → ε. The start symbol of the new grammar is q0.
An edge label w with more than one letter is split by inserting intermediate states. A rule A → B gives an ε-edge from B to A, and a rule A → ε gives an ε-edge from q0 to A. The course pages consulted do not spell out these special cases, so the construction was checked on 400 randomly generated left-linear grammars, comparing all strings up to length 8; the language of the result matched every time. With empty and unit rules the output is an extended right-linear grammar, not the strict form.
Course material from Aoyama Gakuin University describes the opposite direction, from an automaton to a right-linear grammar, and notes that left-linear grammars correspond to reading the input backwards. The automaton produced in the steps above is a nondeterministic finite automaton, because several edges with the same label can leave one state.
Worked example: S → Sa | Ab, A → a
The left-linear grammar has start symbol S and three rules:
S → Sa | Ab
A → a - The grammar generates strings that begin with ab and continue with any number of a: ab, aba, abaa and so on. In short notation the language is ab·a*.
- The states are q0, A and S.
- The rule A → a gives the edge q0 –a→ A.
- The rule S → Ab gives A –b→ S, and the rule S → Sa gives S –a→ S.
- S is the start symbol, so S is the accepting state.
- Read as right-linear rules, the edges give:
q0 → aA
A → bS
S → aS | ε The new grammar has four rules, counting S → ε. It starts at q0, and every derivation follows one path of the automaton to the accepting state S. The derivation q0 ⇒ aA ⇒ abS ⇒ abaS ⇒ aba produces aba, as expected. Listing the strings of both grammars up to length 14 gives ab, aba, abaa and so on for both, with no difference.
Why not just mirror every production?
Moving the nonterminal from the left of the terminals to the right looks like the obvious shortcut, but it changes the language. A left-linear grammar generates the reversal of what the mirrored right-linear grammar generates, so mirroring gives the mirror language rather than the original.
The example shows the effect. Mirroring S → Sa | Ab, A → a yields S → aS | bA and A → a. This grammar generates ba, aba, aaba and so on, which is the language a*·ba. The correct conversion generates ab·a*. Both languages are regular, which is why the mistake is easy to miss, but they are different sets: ab belongs to the first and not to the second.
The relationship is exact: if GR is the grammar with every right-hand side reversed, its language is the reversal of the language of G. Mirroring is therefore correct only for languages that equal their own reversal.
Can left-linear and right-linear rules be mixed?
A grammar that uses both kinds of rule is still linear, but it need not be regular. The grammar S → aA, A → Sb, S → ε has a right-linear rule, a left-linear rule and an empty rule. It generates the strings aibi, which are ε, ab, aabb and so on, with as many b as a.
This language is not regular. A finite automaton would need to remember how many a symbols it has seen, and it cannot, a fact that the pumping lemma proves. A grammar that is consistently left-linear or consistently right-linear never leaves the regular languages, and the mix is what raises the expressive power.
How do you convert a DFA or NFA to a regular grammar?
From an automaton the way to a right-linear grammar is shorter than the conversion above. Each state becomes a nonterminal. Each transition from P to Q on the symbol a becomes the rule P → aQ. A transition into an accepting state also yields a rule that ends in a terminal, or each accepting state receives an empty rule. The start state supplies the start symbol.
The opposite direction builds the automaton from a right-linear grammar: nonterminals become states, rules A → aB become edges, and a new state F, used only for acceptance, is the target of rules that end in a terminal. A deterministic automaton works too, because every deterministic automaton is a nondeterministic one. Where a nondeterministic automaton has to be made deterministic first, the step is described under NFA to DFA.
Frequently asked questions
01What is type 3 grammar?
Type 3 is the lowest level of the Chomsky hierarchy. Its grammars are the regular grammars, whose rules have at most one nonterminal and always at the same end of the right-hand side. They generate exactly the regular languages, which finite automata recognize.
02What is a right-regular grammar?
A right-regular grammar has rules of the form A → a, A → aB and, in some definitions, A → ε, where a is one terminal and B a nonterminal. The nonterminal always stands at the right end. Such grammars generate exactly the regular languages.
03What is a linear grammar?
A linear grammar has at most one nonterminal on the right-hand side of each rule, placed anywhere among the terminals. Left-linear and right-linear grammars are special cases. A linear grammar that mixes both kinds of rule can generate languages that are not regular.
04What are formal languages?
A formal language is a set of strings over a fixed alphabet. Grammars generate such sets and automata recognize them. The overview of formal languages and the Chomsky hierarchy places regular grammars among the other grammar types.