or
V
T
→
*
i.e., the left hand side should have a single variable and the right hand side
consists of any number of terminals (members of T) optionally followed by a
single variable.
2.1.4 Right-Lin ear Gram mars and NFAs
There is a simple connection between right-linear grammars and NFAs, as
shown in the following illustration.
As an example of the correspondence between an NFA and a right linear
grammar, the following automaton and grammar both recognize the set of set
of strings consisting of an even number of 0’s and an even number of 1’s.
2.1.5 Left-Lin ear Gram mar
In a left-linear grammar, all productions have one of the two forms:
V VT
→
*
or
V
T
→
*
i.e., the left hand side must consist of a single varibale, and the right-hand side
consists of an optional single variable followed by one number of terminals.
116
Theory of Automata, Formal Languages and Computation
A
B
x
A
x
y
B
z
A
B
λ
A
x
A
xB
→
A
xyzB
→
A
B
→
A
x
→
1
1
1
1
0
0
0
0
S
A
B
C
S →λ
S
B
→ 0
S
A
→ 0
A
C
→ 0
A
S
→ 1
B
S
→ 0
B
C
→ 1