This question is based on Turing machine and Computation Theory.

Problem 1 Consider the following languages over { = {0,1}. Ll is the language described by (0+1)* L2 is the language of all strings that do not contain the pattern 00. L3 is the language of the DFA given by the following transition table: 0 1 **90 91 90 *q1 92 q1 *q2 q3 92 q3 q3 93 L4 is the language described by & +0+1+8 +0+1) (8 +0+1) * ( +0+1). L5 is the language of all strings that have at most two Os. L6 is the language of the NFA given by the following transition table: 0 {qo, ql} {q2} 1 {q0} **00 *q1 *92 L7 is the language described by 1*(011*)* +1*(011*)*0. Which of these languages are the same and which are different? To show two languages are the same give a short proof, and to show two languages are different give a string that is in one but not by the other. (You must provide an explanation to get credit.)