4. (1+4+2+2+8) Construct a DFA for the NFA in Q1. Fill in the ??? in the fol- lowing. When you are making the set of states, you may either give all possible states, and just not use the states that are never visited; or you may start con- structing the DFA and list only the states that you are actually using. (a) Alphabet: ??? (b) Set of states: ??? (c) Start state: ??? (d) Set of Accepting states: 7 (e) transition table: rows are the set of states you gave; columns are the alpha- bet; entries are from the set of states you gave 1. (10 points) Let M be the NFA with alphabet, set of states and start state as given above. The transition table of Mis: al So (S0, S1} So So Si S2 S2 S3 S3 S: S3 S3 . cata S4 SS SC S7 S8 S, Accepting states A = {S3} For each of the following strings, give the trace (this is the sequence in which each element of the (a) {So} -(50) (b) abc (Sol 9 (50,5,1 (S0, S2] (50,53] (c) aabcc (50) $ 150,51] $150,51] (50,52] $(50,53] $ (50,53) (d) "abcabc (So) $ 150,51] (50,$2} $(50,53] % (S0,S1,33) (S0,S2,S3) (S0, S3) (e) aabbcc (So) $($0,511 9 (S0, S1) $ 150,52] $ 150,52] $150,13]${50,53) The formal definition of a NFA specifies the following: 1. Alphabet 2. the set of states Q 3. the start state SEO 4. the accepting states ASQ 5. the transition table 8: a function from Q x to power(Q). 6. reject state: this is usually unspecified, but understood to be included; similar to a return statement at the end of a function. For every problem in this assignment, 1. S = {a,b,c) 2. Q = (S0, S1,S2,S3,S4,S5,S6, S7, S8, S9) 3. Start state = So If I am giving the NFA, I will give the accepting states A, and the transition table. If you are asked to give the DFA, you need to give A and the transition table. For this assignment, give this as a table instead of a diagram. I will give an example in Q1. NOTE: it is important that you draw and work with diagrams - just translate them when you submit. diagrams give you an insight into the machine that tables do not