1. Show that the DFA in Figure 29 is minimal.

0 0 1 0 1 10 100 1 0 0 1 1 0 1 11 101 0 1 0 111 110 0 Figure 2-9: A DFA that accepts strings with a 1 in the third-to-last position 2. Minimize the DFA defined by the transition function below. The accepting states are {93, 94, 98, 99}. = = 8(qo, a) = (1,8(qo, b) = 49 8(q, a) = 48, 8(91,b) = 42 8(92, a) = 43,8(42,b) = 42 8(93, a) = = 42,8(93,0) = 24 8(94, a) = 95, 8(94, b) = 98 8(95, a) = = 44, 8(95, b) =95 8(q6, a) = 97,8(96, b) = 45 8(97, a) = 26,8(97,b) = 45 8(98, a) = 91,8(98, b) = 93 8(q9, a) = 97,8(99, b) = 48 = = 3. Find a minimal DFA for the following NFA. 0 1 0,1 0.1 90 91 92