CS341 Automata Theory (Fall 2003)Homework Assignment ]3Due Date: Friday, October 3, 2003 (At the beginning of class)Do not forget to write your name, identification number and class time at the top of thefirst page of your solution set. No collaboration is allowed; all solutions submitted must beyour own work.1. For each of the following languages over {0, 1}∗, give a regular expression that repre-sents it.(a) All strings that contain exactly one 1.(b) All strings that contain exactly two 1’s.(c) All strings that contain at least two 1’s.(d) All strings that begin with 11.(e) All strings that begin with 11 and end with 00.(f) All strings that do not begin with 11.(g) All strings that contains the substring 111 or the substring 000.(h) All strings that contain the substring 111 and the substring 000.(i) All strings in which every occurrence of 0 is followed immediately by a 1.2. Using the algorithm presented in class, convert the following regular expressions intoa finite automaton that accepts the language of the regular expression.(a) (ab ∪ b)(b ∪ aaa)b∗(b) ((b ∪ ab)∗b)∗(ba∗)b3. Using the algorithm presented in class, convert the following FAs into regular expres-sions.(a)ababaabb(b) Exercise 1.16b in Sipser4. Exercise 1.17 in Sipser15. For the following languages, state whether it is regular or not, and prove your answer.(a) L = {w ∈ {0, 1}∗|#0(w) 6= #1(w)}(b) L = {xy|x, y ∈ {a, b}∗, |x| = |y|, #a(x) ≥ #a(y)}(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}6. Assume that L1and L2are languages over alphabet Σ, where |Σ| = 2. Indicatewhether each of the following statements is true or false. Justify your answers, andgive examples of L1and L2when appropriate.(a) IF L1is not regular and L1⊆ L2, then L2is not regular.(b) IF L1⊆ L2and L2is not regular, then L1is not regular.(c) If L1is regular, then L1∪ L2is regular for any language L2.(d) If L1and L2are not regular, then L1∩ L2is not regular.7. For the following finite automaton, give the equivalence classes of states and an equiv-alent minimal state machine.0110010101s
View Full Document
Unlocking...