3.) Minimizing work: NON-ACCEPTING ACCEPTING 1,3,5 0,2,4 a) / \ / 5 1,3 0,2,4 b) | | | \ 5 1,3 0 2,4 a) | \ | / 5 1,3 0 2,4 b) | | | \ 5 1,3 0 2,4 [See graphic for final minimized DFA.] 4.) a[ac]*b[ac]*b[ac]*cc Note: (a|c)* is equivalent to [ac]* 5.) S -> aBcc B -> XbXbX X -> Xa | Xc | [epsilon] Note: Other permutations of the grammar are possible, such as: S -> aJbJbJcc J -> JJ | a | c | [epsilon] 6.) With the given parsing machine, the correct parse is actually until step 14 (marked with * below.). At this point, you fail to make to the "st_l -> st" reduction at q8, since there is no statement_list transition out of q9. This failure means the sentence is not acceptable to the parsing machine/grammar. However, the error is actually in the parsing machine. At q8, the reduction should actually read: "statement_list -> statement_list statement". After this correction, you should get the following parse. T/R STATE SYMBOL INPUT --- ----------------- ---------------------- -------------------------- 0 if c a_st if c a_st e e | T 0 1 if c a_st if c a_st e e | T 0 1 6 if c a_st if c a_st e e | T 0 1 6 2 if c a_st if c a_st e e | R 0 1 6 4 if c st if c a_st e e | R 0 1 6 9 if c st_l if c a_st e e | T 0 1 6 9 1 if c st_l if c a_st e e | T 0 1 6 9 1 6 if c st_l if c a_st e e | T 0 1 6 9 1 6 2 if c st_l if a_st e e | R 0 1 6 9 1 6 4 if c st_l if st e e | R 0 1 6 9 1 6 9 if c st_l if st_l e e | T 0 1 6 9 1 6 9 10 if c st_l if st_l e e | R 0 1 6 9 5 if c st_l if_st e | *R 0 1 6 9 8 if c st_l st e | R 0 1 6 9 if c st_l e | T 0 1 6 9 10 if c st_l e | R 0 5 if_st | R 0 4 st | R 0 3 st_l | T 0 3 7 st_l | = ACCEPT The Transition/Reduction column is optional. On an exam, you should show each step, state, and symbol. For input, you could write out the complete input on the first line, and then show only the first character for each later line, like this: INPUT -------------------------- if c a_st if c a_st e e | c ... a_st ... if ... if ... [lines omitted] e ... e | [lines omitted] e | |