[SOLVED] CS323  Assignment 2

1 Requirements
2 Required Exercises (100 points)
1. L((a|b)*b) [10 points]
2. L(((ϵ|a)*b)*) [10 points]
3. L((a|b)*a(a|b)(a|b)) [10 points]
4. L(a*ba*ba*ba*) [10 points]
Exercise 2: Convert the following regular expressions to NFAs using the Thompson’s Construction Algorithm (Algorithm 3.23 in the dragon book). Please put down the detailed steps and DO NOT optimize the NFAs.
1. ((ϵ|a)*b)* [10 points]
2. (a|b)*a(a|b)(a|b) [10 points]
3. a*ba*ba*ba* [10 points]
Exercise 3: Convert the NFAs in Exercise 2 to DFAs using the Subset Construction Algorithm (Algorithm 3.20 in the dragon book). Please put down the detailed steps. [30 points in total; 10 points for each correct conversion]
1