PLEASE DO NOT GIVE TO ANYONE OUTSIDE THIS CLASSEECS 2001A 2021F – Test 3Instructor: Jeff Edmonds 16 + 6 + 626 + 8313 + 6 + 6 + 6 + 13 + 649 + 9Total100 Keep your answers short and clear.Do not repeat the question.Sorry. We are not going to do the 20% for blanks as you have lots of tiime and it is too much paper work.1. Regular Expressions(a) Either argue that every subset of a regular language is regularor describe three languages L1, L2, and L3 such that L1 ⊆ L2 ⊆ L3, and L1 and L3 are regularand L2 is not.(b) Compare (r ∪ s)∗ vs (r∗s)∗r∗. Explain.(c) Give a regular expression for the following DFA.dba ce2. Closure: Consider the automata:L1 = L(M1) L2 = L(M2)00,111 1000q 0 q 1 q 2(a) What are the languages L1, (L1)∗, and L2?(b) Construct an NFA for the language L1 ∩ L2. Use the technique done in class that combines theabove two machines. Do not simplify the machine produced.3. Consider the NFA M depicted below.q1q2 q 3a a,ba,ba,bq*(a) Convert this NFA into a DFA.Hint: In my answer, I was too lazy to write so many q’s so I simplified q2 to simply 2.(b) If possible, label each state with some 3 character string that reaches this state.(c) Let L0 = {aaa, aab, aba, aba, abb}Let L1 = {α = cncn-1 . . . c3c2c1 ∈ {a, b}∗ | c3 = a} = {c ∈ {a, b} | the 3rd last character is an a}.For example, bbbbabb is in the language and bbbbab is not.Let L2 = {α = c1c2c3 . . . cn-1cn ∈ {a, b}∗ | c3 = a} = {c ∈ {a, b} | the 3rd character is an a}.For example, bbabbbb is in the language and babbbb is not.Does M accept L0, L1, L2, or some other language?1(d) What does this DFA remember about the prefix of the string read so far?(e) Prove that no DFA computes L with fewer states than the one you constructed.Hint: My proof has three cases. In one of them, we compare the strings ?a? and ?b?.(f) Generalize the NFA above, replacing the path q1q2q3 with a similar path with n states. Howmany states would the DF A computing the same language need?4. Construct context-free grammars for the following languages.Explain which strings are generated by each nonterminal symbol of your grammars and what the roleof each production is.(a) L consists of those {a, b}∗ strings of odd length whose first symbol, the middle one, and the lastone are the same.(b) Lnp = {x ∈ {a, b}∗ | x 6= xR} where xR is the reverse of the string x. (So Lnp is the complementof the language of palindromes over {a, b}∗.Hint: In order for it to not be a palindrome, there must be some index i such that the ith characterand the n-ith characters are different.A ”regular” expression for it would be {a, b}ia{a, b}∗b{a, b}i ∪ {a, b}ib{a, b}∗a{a, b}i.2
