Description
1. (5 points) Describe the 5-tuples (Q, ⌃, , q0, F) corresponding to the following DFA. (For it
suces to draw a table).
1
2. (15 points) Consider the following two DFA’s M and N.
(a) What are the languages L(M) and L(N)?
(b) Following the approach that was used in Lecture 3, design a DFA that recognizes L(M) [
L(N). (It suces to draw the state diagram).
(c) Design a smaller DFA that recognizes L(M) [ L(N).
3. (20 points) For each one of the following languages over the alphabet ⌃ = {0, 1} give a DFA
that recognizes them. (It suces to draw the state diagram).
(a) The set of all strings x such that the number of ones in x is divisible by 3 and not divisible
by 2 (for example 1011 is accepted but 10 and 111111 are not in the language).
(b) of length at least two that start and end with the same symbol (for example 00, 1011 are
accepted but 0, 011011 and 10 are not accepted).
(c) The set of all the strings that contain all of the four strings “00”, “01”, “10”, and “11” as
substrings. (for example 101100 is accepted).
(d) The set of all strings of length at least three such that every three consecutive symbols
contain at least two 1’s (for example 1101 is accepted but 1010111 is not).
4. (10 points) Let L be a language over {0, 1} consisting of a single word of length k. Describe a
DFA with k + 1 states that accepts L. Prove that no DFA with fewer than k + 1 can recognize
such a language.
5. (10 points) Let L be a finite language over {0, 1}, and let k be the length of the longest word in
L. Describe a DFA with 2k+1 states that accepts L.
6. (10 points) Give an NFA M = (Q, ⌃, , q0, F) accepting the following language over the alphabet
{a, b, c, d}: The set of all strings that contain at least two a’s with no c appearing between them
(For example bcabbdaca and aa are accepted but abccdabcb and bd are not accepted). Drawing
the state diagram suces.
2
7. Let M be a DFA accepting a language A over the alphabet {0, 1}. For each one of the following
languages design an NFA (based on M) that accepts the language.
(a) (5 points) A \ {“}.
(b) (10 points) {wR|w 2 A}, where wR is the reverse of the string w. (For example the reverse
of 01101 is 10110).
8. (15 points) Let r, s and t be regular expressions. Prove or disprove each one of the following
equalities.
(a) (rs [ r)⇤ = r(sr [ r)⇤
(b) s(rs [ s)⇤ = rr⇤s(rr⇤s)⇤
(c) (r [ s)⇤ = r⇤ [ s⇤
3