Homework 2 Problem 1. (5 points) Given two NFA's M and M2, show how you will con- struct an NFA M such that L(M)=L(M) n L(M2). Problem 2. (15 points) For each of the following languages over the alphabet = {a,b}, give a DFA that recognizes that language. (a) L consists of strings that end in aba, i.e. L1 = {ww = saba where SES*}. (b) La consists of strings in which every odd position contains b Problem 3. (8 points) Show by giving an example that if M is an NFA that recognizes the language L, swapping the accept and non-accept states in M does not necessarily yield a new NFA that recognizes L, complement of L. Problem 4. (15 points) Give NFAs with the specified number of states recog- nizing each of the following languages. In all cases, the alphabet is = {a,b}. (a) L1 = {w 2* w contains at least two Os, or exactly two 1s } with six states. (b) Regular expression language b*a*b*b with three states. Problem 5. (20 points) Problem 1.17. of the text book Problem 6. (10 points) Give regular expressions that generate each of the following languages. In all cases, the alphabet is = {a,b}. (a) The language {w/w contains at least two b's, or exactly two a's } (b) The language {w/w contains exactly one double letter }. A double letter is either aa or bb. For example, baaba has exactly one double letter, but baaaba has two double letters. Problem 7. (15 points) Problem 1.21 of the text book Problem 8. (12 points) Prove that the following languages over the alphabet are not regular. (a) L1 = {b"a27b7|n>0} (b) L2 = {a" |n is a prime number }. Homework 2 Problem 1. (5 points) Given two NFA's M and M2, show how you will con- struct an NFA M such that L(M)=L(M) n L(M2). Problem 2. (15 points) For each of the following languages over the alphabet = {a,b}, give a DFA that recognizes that language. (a) L consists of strings that end in aba, i.e. L1 = {ww = saba where SES*}. (b) La consists of strings in which every odd position contains b Problem 3. (8 points) Show by giving an example that if M is an NFA that recognizes the language L, swapping the accept and non-accept states in M does not necessarily yield a new NFA that recognizes L, complement of L. Problem 4. (15 points) Give NFAs with the specified number of states recog- nizing each of the following languages. In all cases, the alphabet is = {a,b}. (a) L1 = {w 2* w contains at least two Os, or exactly two 1s } with six states. (b) Regular expression language b*a*b*b with three states. Problem 5. (20 points) Problem 1.17. of the text book Problem 6. (10 points) Give regular expressions that generate each of the following languages. In all cases, the alphabet is = {a,b}. (a) The language {w/w contains at least two b's, or exactly two a's } (b) The language {w/w contains exactly one double letter }. A double letter is either aa or bb. For example, baaba has exactly one double letter, but baaaba has two double letters. Problem 7. (15 points) Problem 1.21 of the text book Problem 8. (12 points) Prove that the following languages over the alphabet are not regular. (a) L1 = {b"a27b7|n>0} (b) L2 = {a" |n is a prime number }