
44 An Introduction to Compiler Construction in a Java World
• We then put them together using rule 3 to produce an NFA recognizing a|b.
• The NFA recognizing (a|b) is the same as that recognizing a|b, by rule 6. An NFA
recognizing the second instance of a is simple enough, by rule 1 again.
• The NFA recognizing a∗ can be constructed from that recognizing a, by applying rule
4.
• We then apply rule 2 to construct an NFA recognizing the concatenation (a|b)a∗.