Formal languages / regular grammars

Convert a Left-Linear to a Right-Linear Grammar

A left-linear grammar becomes a right-linear one by reading it as an NFA whose edges run against the direction of derivation, then writing that NFA out as right-linear rules. Mirroring each rule does not work, because it produces the reversed language.

Published
ScopeRegular grammars
States in the example3
Rules left and right3 and 4
Languageab·a*

From left-linear to right-linear: rule, automaton, rule

  1. S → Sa | Ab, A → a has 3 rules, each nonterminal at the left end.

    The left-linear grammar has start symbol S and 3 rules: S → Sa, S → Ab and A → a. A nonterminal, where a rule has one, stands at the left end. The grammar generates strings that begin with ab and continue with any number of a, such as ab, aba, abaa. In short notation the language is ab·a*.

  2. The automaton gets 3 states: a fresh start q₀, plus A and S.

    Every nonterminal becomes a state, so A and S each get one. A fresh state q₀ is added as the start of the automaton. It stands for the moment before any symbol is read, which is where a rule without a nonterminal begins. The automaton has 3 states and no edges yet.

  3. A → a has no nonterminal, so it gives the edge q₀ –a→ A.

    A rule without a nonterminal on the right is where a derivation ends, and it is where the automaton begins. The rule A → a therefore gives an edge from the fresh state: q₀ –a→ A. Reading that edge later as a right-linear rule produces q₀ → aA. The edge runs against the direction of the derivation.

  4. S → Ab gives A –b→ S, and S → Sa gives S –a→ S.

    A rule X → Yw says that X is reached after Y and then w, so the edge goes from Y to X on w. The rule S → Ab gives A –b→ S, and S → Sa gives the loop S –a→ S. Written from left to right, these edges produce A → bS and S → aS.

  5. The start symbol S becomes the accepting state of the automaton.

    A derivation of the left-linear grammar begins at the start symbol S, and the automaton runs the same derivation backwards. So its run has to finish at S, which makes S the accepting state. An accepting state allows the run to stop there, and in a right-linear grammar that is the rule S → ε.

  6. Read as rules, the automaton gives q₀ → aA, A → bS, S → aS, S → ε.

    Each edge p –x→ r is written as the rule p → xr, and the accepting state adds S → ε. The new grammar starts at q₀ and has 4 rules: q₀ → aA, A → bS, S → aS, S → ε. The nonterminal now stands on the right. It generates ab, aba, abaa, and so on, like the original grammar.

  7. Mirrored rules generate a*·ba instead of ab·a*, so ab is lost.

    Moving each nonterminal to the other side gives S → aS | bA, A → a. These rules generate ba, aba, aaba, which is a*·ba and the reversal of the original language, not the language itself. The two lists share only aba. A listing shows the error; it cannot prove equivalence, which rests on the construction.

Left-linear rules

  • S → Sa
  • S → Ab
  • A → a
Automaton
start a b a q₀ A S

Right-linear rules

  • q₀ → aA
  • A → bS
  • S → aS
  • S → ε

Mirrored rules

    Strings each grammar generates, by length
    Length Left-linear Right-linear Mirrored
    2
    3
    4
    5

    Left-linear grammar

    S → Sa | Ab, A → a has 3 rules, each nonterminal at the left end.

      Sources: Wikipedia, Regular grammar, Wikipedia, Linear grammar, Tel Aviv University, Regular languages, grammars and automata, Aoyama Gakuin University, Compilers, Lecture 4, Virginia Tech, OpenDSA, Regular Grammars, finger-bone, personal notes on left-linear grammars. No source gives this worked example; it was constructed here and checked by listing.

      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.

      GrammarRule shapesExample
      Left-linearA → Bw, A → wS → Sa | Ab, A → a
      Right-linearA → wB, A → wS → 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.

      1. Create one state for each nonterminal and add a fresh state q0, which becomes the start state.
      2. Declare the start symbol of the grammar the only accepting state.
      3. For each rule A → w with only terminals, add an edge from q0 to A labeled w.
      4. For each rule A → Bw, add an edge from B to A labeled w.
      5. 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
      1. 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*.
      2. The states are q0, A and S.
      3. The rule A → a gives the edge q0 –a→ A.
      4. The rule S → Ab gives A –b→ S, and the rule S → Sa gives S –a→ S.
      5. S is the start symbol, so S is the accepting state.
      6. 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.

      FAQ

      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.