CS341 Automata Theory (Summer 2008)Homework Assignment ♯2Due Date: June 13, 2008 (At the beginning of class)Do not forget to write your name and EID.1. Construct DFAs for the following languag es.(a) The set of all binary strings having a substring 00 and ending with 01.(b) The set of all binary strings having a substring 00 but not ending with 01 .(c) The set of all binary strings with 3 consecutive zeros.(d) The set of all binary strings beginning with a 1 which, interpreted as the binaryrepresentation of an integer, is congruent to 0 modulo 5.(e) The set of all strings over alphabet {a, b} of length up to 3.(f) The set of all strings of length 3n, n = 0, 1, 2, ....2. Construct NFAs for the following languages.(a) {anbam| n, m ≥ 0, n ≡5m}.(b) The set of all strings of 0’s and 1’s such that 10 th symbol from the right end is a1.3. (a) Describe infor mally the language accepted by the finite automaton.1aabbaaba, bbFA for #3abbaba aFigure for #3b(b) Describe the language accepted by this finite automaton:4. Let L, L′⊆ Σ∗. Define the following languages.• P ref(L) = {w ∈ Σ∗: x = wy for some x ∈ L, y ∈ Σ∗} (the set of prefixes ofL).• Suf(L) = {w ∈ Σ∗: x = yw for some x ∈ L, y ∈ Σ∗} (the set of suffixes o f L).• Subseq(L) = {w1w2· · · wk: k ∈ N, wi∈ Σ∗for i = 1, . . . , k, andthere is a string x = x0w1x1w2x2· · · wkxk∈ L} (the set of subsequences of L).• Max(L) = {w ∈ L : if x 6= ε then wx /∈ L}.Show that if L is accepted by some finite automato n, then so is each of the following.(a) P ref(L).(b) Suf(L).2(c) Subseq(L).(d) Max(L).5. Find the ε-closure of each of the states of the following NFA, and convert it into anequivalent DFA.q0 q1 q2q3 q4
View Full Document
Unlocking...