1. (10 points) Let L1 and L2 be regular languages. Construct an NFA to recognize the language L defined below Give a brief justification as to why your NFA is correct 1 = {w E {0,1). I either(w E L1 and w e La) or (w g L and w L2)) 2. (5 points) An all-NFA M s a 5-tuple (Q, , qo,F) that accepts a string z E . if every possible state that M could be in after reading input z is a state from F. Note, in contrast, that an ordinary NFA accepts a string if some state among these possible states is an accept state Given an all-NFA M (Q, ,6,go, F), show how to construct a DFA D such that that L(D) -L(M) 3. (15 points) Let A be a regular language. Show that the following language is also regular {x | there exists y such that |y| = 2 and xy E A} 4. Let A and B be two languages. Define: shuffle(A, B) {ul w = a,bi akbk, where each ai, b e ., ai ak e A and bi bk e B} = (15 points) Show that shuf fle(A, B) is regular if A and B are regular 5. (5 points) Convert the following NFA to an equivalent DFA. For each state, show its e-closure 0 1. (10 points) Let L1 and L2 be regular languages. Construct an NFA to recognize the language L defined below Give a brief justification as to why your NFA is correct 1 = {w E {0,1). I either(w E L1 and w e La) or (w g L and w L2)) 2. (5 points) An all-NFA M s a 5-tuple (Q, , qo,F) that accepts a string z E . if every possible state that M could be in after reading input z is a state from F. Note, in contrast, that an ordinary NFA accepts a string if some state among these possible states is an accept state Given an all-NFA M (Q, ,6,go, F), show how to construct a DFA D such that that L(D) -L(M) 3. (15 points) Let A be a regular language. Show that the following language is also regular {x | there exists y such that |y| = 2 and xy E A} 4. Let A and B be two languages. Define: shuffle(A, B) {ul w = a,bi akbk, where each ai, b e ., ai ak e A and bi bk e B} = (15 points) Show that shuf fle(A, B) is regular if A and B are regular 5. (5 points) Convert the following NFA to an equivalent DFA. For each state, show its e-closure 0