CS341 Automata Theory (Summer 2008)Homework Assignment ♯3Due Date: June 19, 2008 (At the beginning of class)Do not forget to write your name and EID.1. For the following languages, give a regular expression that represents the language.(a) {w ∈ {0, 1}∗| w begins with a 1 and ends with a 0}(b) {w ∈ {0, 1}∗| w contains at least 3 1s}(c) {w ∈ {0, 1}∗| w starts with 0 and has odd length, or w starts with 1 a nd has evenlength}(d) {w ∈ {0, 1}∗| w contains at least two 0s and at most one 1}(e) {w ∈ {0, 1}∗| every odd position of w is a 1}2. Use the algorithm given in class to convert the following regular expressions to a finiteautomaton.(a) (a ∪ b)∗ab(abb ∪ a∗)∗bb∗(b) a(aa ∪ b)∗(a∗b ∪ b)∗ab3. Use the algorithm given in class to convert the NFA to a DFA.1a, bababab1 234 5Figure for 3a1234 5 6babbabbb aFigure for 3b(a)(b)4. Prove that the following languages over {a, b} are not regular.(a) L = {anba3n|n 6= 0}(b) L = {anbnan|n 6= 0}(c) L = {aibn|i, n 6= 0, i = n or i = 2n}5. Assume that L1, L2are languages over some alphabet Σ, where |Σ| = 2. For each ofthe following statements, tell whether the statement is true or false, and prove youranswer.(a) If L1is nonregular and L1⊆ L2, then L2is nonregular.(b) If L1⊆ L2and L2is nonregular, then L1is nonregular.(c) If L1is nonregular, then its complement Lc1is nonregular.(d) If L1is regular, then L1∪ L2is regular for any language L2.(e) If L1and L2are nonregular, then L1∩ L2is nonregular.26. For each of the f ollowing languages, state whether it is regular or not, and prove youranswer.(a) L = {w ∈ {0, 1}∗|♯0w 6= ♯1w}.(b) L = {xy| x, y ∈ {a, b}∗, |x| = |y|, ♯ax ≥ ♯ay}.(c) The complement of {0n1n|n ≥ 0}.(d) {w|w ∈ {0, 1}∗is not a palindrome }(e) L = {an!| n ≥ 0}.(f) L = {x♯y| x, y ∈ {0, 1}∗, |x| · |y| is divisible by 5}.7. Using the algorithm we discussed in class, convert the DFA in 1.21b, p. 86 of Sipser,to a regular
View Full Document
Unlocking...