CS 390 Solutions to Unit 15 Exercises
p. 164
4.38 (a):
j = 0
| p |
r(p, 1, 0) |
r(p, 2, 0) |
r(p, 3, 0) |
| 1 |
 |
b |
a |
| 2 |
a |
|
b |
| 3 |
b |
a |
|
j = 1
| p |
r(p, 1, 1) |
r(p, 2, 1) |
r(p, 3, 1) |
| 1 |
|
b |
a |
| 2 |
a |
+ ab |
b + aa |
| 3 |
b |
a + bb |
+ ba |
j = 2
| p |
r(p, 1, 2) |
r(p, 2, 2) |
r(p, 3, 2) |
| 1 |
+ b(ab)*a |
b(ab)* |
a + b(ab)*(b + aa) |
| 2 |
(ab)*a |
(ab)* |
(ab)*(b + aa) |
| 3 |
b + (a + bb)(ab)*a |
(a + bb)(ab)* |
+ ba + (a + bb)(ab)*(b + aa) |
Complement of DFA of Figure 4.27 (a): Simply switch accepting and non-accepting states, that is,
make 3 a non-accepting state and 1 and 2 accepting states.