Instructions:

• You are allowed - and even encouraged - to work with other students, as well as to use textbooks and resources from the Internet, to solve these problems. However, your write-up must be your own and you must understand your answers. Inability to explain what you have written may result in losing credit for the homework assignment, and is likely to also result in poor performance on the exam.

Text sections: primarily 4.1, 4.2

Note: Lc denotes the complement of L.

1. Assuming Σ = {a, b}, find a regular expression for the complement of the language L = L(aa*bb*). Hint: consider a multi-step approach: (i) construct a DFA M1 that accepts L; (ii) modify it to make M2 that accepts Lc; (iii) find the regular expression that corresponds with M2

2. Assuming Σ = {a, b}, find a regular expression for the complement of the language L = L(a*b*)*. Hint: consider a simpler approach than the hint of the previous question.

3. Show how from a DFA for L, once can construct a finite automaton that accepts (Lc)*.

4. Find an NFA (with λ-transitions) that accepts L(ab*a*) ∩ L(a*b*a). Hint: you may usea construction like we did in class while proving closure under intersection, or you may find it easier to directly determine the intersection and build an NFA for that.

5. The symmetric difference of S1?S2 is defined as {(x ∈ S1 and x ∉ S2) or (x ∈ S2and x ∉ S1)}. Prove that the regular languages are closed under symmetric difference.

6. Describe an algorithm by which we can determine

a. If for a given regular language L, is equal to Σ* (all words over an alphabet)
b. If for given regular languages L, L1, L2, L = L1 L2.