1. [25 points] Let M be the DFA having the state diagram 1 40 91 42 1 Answer the following questions, giving a brief explanation of your answer. (One short sentence, or perhaps even a sentence fragment, will suffice.) (a) Is(M,00 101 1001) ADFA? (b) Is (M,0010110011) e ADFA? (c) Is(M) EDFA? (d) Is(M,M) EQDFA? (e) Let R = 0"(10), 1 | 0"(10). 1(10*1).. Is R, 001011001) E ARE? Hint: Why did I choose this regular expression to be part of this problem? ED FA is a decidable language. PROOF A DFA accepts some string iff reaching an accept state from the start state by traveling along the arrows of the DFA is possible. To test this condition, we can design a TM T that uses a marking algorithm similar to that used in Example 3.23 T- "On input (A), where A is a DFA: 1. Mark the start state of A. 2. Repeat until no new states get marked: 3. Mark any state that has a transition coming into it from any state that is already marked. If no accept state is marked, accept; otherwise, reject." 4. EQDFA is a decidable language PROOF To prove this theorem, we use Theorem 4.4. We construct a new DFA C from A and B, where C accepts only those strings that are accepted by either A or B but not by both. Thus, if A and B recognize the same language, C will accept nothing. The language of C' is L(C) L(A) nL(B) ) U (L(A)n L(B) This expression is sometimes called the symmetric difference of L(A) and L(B) and is illustrated in the following figure. Here, L (A) is the complement of L (A). The symmetric difference is useful here because L(C)iff L(A)L(B). We can construct C from A and B with the constructions for proving the class of regular languages closed under complementation, union, and intersection. These constructions are algorithms that can be carried out by Turing machines. Once we have constructed C, we can use Theorem 4.4 to test whether L(C) is empty. If it is empty, L(A) and L(B) must be equal. F-"On input(A. B, where A and B are DFAs: 1. 2. Construct DFA C as described Run TM T from Theorem 4.4 on input(C). IfT accepts, accept. If T rejects, reject 1. [25 points] Let M be the DFA having the state diagram 1 40 91 42 1 Answer the following questions, giving a brief explanation of your answer. (One short sentence, or perhaps even a sentence fragment, will suffice.) (a) Is(M,00 101 1001) ADFA? (b) Is (M,0010110011) e ADFA? (c) Is(M) EDFA? (d) Is(M,M) EQDFA? (e) Let R = 0"(10), 1 | 0"(10). 1(10*1).. Is R, 001011001) E ARE? Hint: Why did I choose this regular expression to be part of this problem? ED FA is a decidable language. PROOF A DFA accepts some string iff reaching an accept state from the start state by traveling along the arrows of the DFA is possible. To test this condition, we can design a TM T that uses a marking algorithm similar to that used in Example 3.23 T- "On input (A), where A is a DFA: 1. Mark the start state of A. 2. Repeat until no new states get marked: 3. Mark any state that has a transition coming into it from any state that is already marked. If no accept state is marked, accept; otherwise, reject." 4. EQDFA is a decidable language PROOF To prove this theorem, we use Theorem 4.4. We construct a new DFA C from A and B, where C accepts only those strings that are accepted by either A or B but not by both. Thus, if A and B recognize the same language, C will accept nothing. The language of C' is L(C) L(A) nL(B) ) U (L(A)n L(B) This expression is sometimes called the symmetric difference of L(A) and L(B) and is illustrated in the following figure. Here, L (A) is the complement of L (A). The symmetric difference is useful here because L(C)iff L(A)L(B). We can construct C from A and B with the constructions for proving the class of regular languages closed under complementation, union, and intersection. These constructions are algorithms that can be carried out by Turing machines. Once we have constructed C, we can use Theorem 4.4 to test whether L(C) is empty. If it is empty, L(A) and L(B) must be equal. F-"On input(A. B, where A and B are DFAs: 1. 2. Construct DFA C as described Run TM T from Theorem 4.4 on input(C). IfT accepts, accept. If T rejects, reject
