[Overview] [Previous] [Next]

Right-Linear Grammars and NFAs

There is a simple connection between right-linear grammars and NFAs, as suggested by the following diagrams:
A goes to x B
A goes to x y z B
A goes to B
A goes to x

As an example of the correspondence between an nfa and a right-linear grammar, the following automaton and grammar both recognize the set of strings consisting of an even number of 0's and an even number of 1's.

S goes to empty string
S goes to 0 B
S goes to 1 A

A goes to 0 C
A goes to 1 S

B goes to 0 S
B goes to 1 C

C goes to 0 A
C goes to 1 B
Copyright © 1996 by David Matuszek
Last modified Feb 11, 1996