• Requirements
You are expected to complete all required homework exercises and encouraged to complete the optional ones. For submission, please put all your answers in a single PDF file and submit it via the assignment channel on SAKAI. The name of the file should follow the format “studentID A#” (e.g., 30003554 A2). The submission deadline is 11:55 PM, October 16, 2022. Late submissions are allowed within one week after the deadline (grace period). If you submit your assignment during the grace period, your score will be 80% of the score you could get if the submission was made in time. Assignment submitted after the grace period will not be graded, meaning that you will get a zero for the assignment.
• Required Exercises (100 points)
Exercise 1: Design NFAs to recognize each of the following regular languages. Is each of
the NFAs designed by you also a DFA? The alphabet contains only two symbols: a and b.
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 Con-struction 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 Algo-rithm (Algorithm 3.20 in the dragon book). Please put down the detailed steps. [30 points in total; 10 points for each correct conversion]
1
