CS 390 Solutions to Unit 8 Exercises --- 3.17 (a)(e)

p. 115

3.17 (e)

I : (ab + ba)*
For at state I there are two cycles: ab and ba. You can take this cycle any number of times and in any order.

II : (ab + ba)*a
For if you read one a at I, you come to II.

III : (ab + ba)*b
For if you read one b at I, you come to III.

IV : (ab + ba)*(aa + bb)(a+b)*
For if you read one a at II or one b at III, then you come to IV. At IV tyou can read any string of a's and b's without leaving IV.