Convert a Left-Linear to a Right-Linear Grammar

To convert a left-linear grammar to a right-linear grammar, first translate its productions into an NFA whose transition direction reflects the left-linear derivation. Then read that NFA as right-linear productions. This avoids informal symbol reversal, which can accidentally produce the reversed language.

Left-linear and right-linear productions

A simple left-linear production has the form A → B a or A → a, where uppercase symbols are nonterminals and a is a terminal. A right-linear production has the form A → a B or A → a.

Both restrictions describe regular languages when applied consistently across the grammar. The conversion can therefore pass through a deterministic or nondeterministic finite automaton.

NFA conversion method

1. Create one state for every nonterminal and add a fresh state q₀.
2. Make q₀ the NFA start state.
3. Make the original grammar start symbol the accepting state.
4. For each production A → B a, add transition B —a→ A.
5. For each production A → a, add transition q₀ —a→ A.
6. Translate every NFA transition P —a→ Q into right-linear production P → a Q.
7. Add S → ε for each accepting state S.

Productions containing longer terminal strings can be normalized by inserting intermediate states. Nullable nonterminals and epsilon productions require the corresponding epsilon-closure or accepting-state adjustments.

Worked conversion example

Consider this left-linear grammar with start symbol S:

S → A b | a
A → B a | b
B → a

Create states q₀, S, A and B. The accepting state is S. The productions produce these NFA transitions:

A —b→ S
q₀ —a→ S
B —a→ A
q₀ —b→ A
q₀ —a→ B

Reading those transitions as a right-linear grammar gives:

q₀ → a S | b A | a B
A  → b S
B  → a A
S  → ε

The new grammar starts at q₀. Each derivation follows an NFA path and terminates when it reaches the accepting state S.

Verify language equivalence

List strings up to a small length from both grammars and compare the sets. This catches swapped transition direction, an incorrect accepting state and omitted terminal-only productions. For a proof-oriented check, minimize or compare the finite automata derived from both grammars.

Do not simply move a nonterminal from the left side of the terminal string to the right. Grammar derivations are directional, and that shortcut generally does not preserve the language.