CS341 Automata Theory (Fall 2003)Homework Assignment ]2Due Date: Monday, Sept 22, 2003 (At the beginning of class)Do not forget to write your name, social security 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. Give formal definitions for the languages accepted by the following DFAs.(a)00110011(b)abcb,ca,ca,babca, b, ca, b, c2. Construct DFAs for the following languages. Give state diagrams for all of them, anddefine the first two formally as well.(a) {x ∈ {a, b}∗|x does not contain aba as a substring}(b) {x ∈ {a, b}∗|x is a prefix of a∗anbnb∗for some n}(c) {w ∈ {a, b}∗|#a(w)mod3 = 1}(d) {w ∈ {0, 1}∗|every 00 in w is followed immediately by a 1}13. Construct NFAs for the following languages.(a) {an|n ≥ 1} ∪ {bmak|m ≥ 0, k ≥ 0}(b) The set of all strings of 0’s and 1’s such that the 10th symbol from the right is 1.(c) {anbam|n, m ≥ 0 and n ≡5m}4. Show that if language L is accepted by a finite automaton then so isMax(L) = {w ∈ L| if x 6= ε then wx 6∈ L}5. Convert the following NFA to a DFA using the algorithm presented in class. Show allsteps.s q
View Full Document
Unlocking...