Add your answers in the space after each problem. Add lines to the document as needed to make room, but do not rearrange or renumber the problems.

For questions that require a JFLAP solution, use JFLAP to capture the image including both the machine diagram and at least 10 test case results and include that image in your answer document. For example:

1. Use JFLAP to create and test a DFA accepting the language L1 = {x | x {0, 1}* and x contains at least three 0s}. (Be sure that the machine is deterministic, i.e., has exactly one transition per state per symbol.) (10)

2. Use JFLAP to create and test a DFA accepting the language L2 = {x | x {0, 1}*, x starts with 1, and x contains at most one 0}. (10)

3. Use JFLAP to create and test an NFA that accepts (L1 L2). (See theorem 1.45 for a hint of how to do this easily) (10)

4. Use JFLAP to create a DFA from this formal definition (no tests are necessary for this problem). (10) M = ( {q1, q2, q3, q4}, {0,1}, {((q1,0),q1), ((q1,1),q2), ((q2,0),q3), ((q2,1),q4), ((q3,0),q2), ((q3,1),q1), ((q4,0),q3), ((q4,1),q4)}, q1, {q1, q4} )