Right- and Left-Linear CFGs: A right-linear CFG is one where every production rule has exactly one non-terminal and that it also appears rightmost. For example, the following grammar is right-linear:
S -> 0 A | 1 B | e
A -> 1 C | 0
B -> 0 C | 1
C -> 1 | 0 C.
Recall that S -> 0 A | 1 B | e is actually three different production rules S -> 0 A, S -> 1 B, and S -> e, where each rule is right-linear. This grammar can easily be represented by the following NFA obtained almost directly from the grammar:
IS - 0 -> A
IS - 1 -> B
IS - e -> F1
A - 1 -> C
A - 0 -> F2
B - 0 -> C
B - 1 -> F3
C - 0 -> C
C - 1 -> F4.
A left-linear grammar is defined similar to a right-linear one. An example is as follows:
S -> A 0 | B 1 | e
A -> C 1 | 0
B -> C 1 | 1
C -> 1 | C 0.
A purely left-linear or a purely right-linear CFG denotes a regular language. However, the converse is not true; that is, if a language is regular, it does not mean that it has to be generated by a purely leftlinear or purely right-linear CFG. Even non-linear CFGs are perfectly capable of sometimes generating regular sets, as in
S -> T T | e
T -> 0 T | 0.
It also must be borne in mind that we cannot “mix up” left- and rightlinear productions and expect to obtain a regular language. Consider the productions
S -> 0 T | e
T -> S 1.
In this grammar, the productions are linear - left or right. However, since we use left- and right-linear rules, the net effect is as if we defined the grammar
S -> 0 S 1 | e
which generates the non-regular context-free language
{0n1n | n ≥ 0}.
Conversion of purely left-linear grammars to NFA: Converting a left-linear grammar to an NFA is less straightforward. We first reverse the language it represents by reversing the grammar. Grammar reversal is approached as follows: given a production rule
S → R1R2 . . .Rn,
we obtain a production rule for the reverse of the language represented by S by reversing the production rule to:
Sr → RrnRrn−1 . . .Rr1 .
Applying this to the grammar at hand, we obtain
Sr -> 0 Ar | 1 Br | e
Ar -> 1 Cr | 0
Br -> 1 Cr | 1
Cr -> 1 | 0 Cr.
Once an NFA for this right-linear grammar is built, it can be reversed to obtain the desired NFA.
