The condition that V 1 and V 2 should be disjoint is essential so that the two
nfa's are distinct.
Chapter 4
Section 4.1
2. (a) The construction is straightforward, but tedious. A dfa for L ((a +
b)a * ) is given by
with q t a trap state and final state q 1 . A dfa for L(baa * ) is given by
with final state p 2 . From this we find
etc. When we complete this construction, we see that the only final state is
(q 1 , p 2 ) and that
.
7. Notice that
The result then follows from closure under intersection and
complementation.