Description
1. [2×10 points]For each of the languages, L1, L2 below, construct a DFA that computes that languages.
Represent your DFA’s as tuples, M = (Σ, Q, q0, δ, F), with a transition table for δ, and draw the
transition diagram (graph representation) of M. Provide a brief justification of your construction.
(a) L1 = {x ∈ {a, b, c}
∗
: ab is not a substring of x}.
(b) L2 = {x ∈ {a, b}
∗
: na(x)is even, ornb(x)is even}, (where, for a letter σ ∈ Σ, and a word w ∈ Σ
∗
,
nσ(w) = the number of occurrences of σ in w.
2. (a) [10 points] Let M = (Σ, Q, q0, δ, F) be a DFA with a single accepting state (that is, |F| = 1).
Prove that for every x, y, ∈ L(M),
{z ∈ Σ
∗
: xz ∈ L(M)} = {z ∈ Σ
∗
: yz ∈ L(M)}
(b) [15 points] Find a regular language, L, (describe it either as L(A) for some DFA, A, or as L(r)
for some regular expression r) that can not be computes by any DFA that has a single accepting
state. Prove your claims.
(c) [10 points] Prove that for every DFA, M, there exist a finite number of DFA’s, A1, . . . , Ak, each
having a single accepting state, such that L(M) = Sk
i=1 L(Ai).
3. [15 points] Convert the following NFA into a DFA. That is, construct a DFA that computes the same
language computed by the NFA described by the transition diagram below. Explain the steps you took
in that transformation.
4. We discussed in class how do construct NFA’s for keyword searches. Let us elaborate about that
construction. Given any finite set of words {w1, . . . wk} over the alphabet {a, b}, let |w1| . . . |wk|,
denote their lengths (respectively),
(a) [15 points] Construct an NFA, N(w1,…wk) that has 1 + Pk
i=1 |wi
| states that accepts a word w if
and only if it contains at least one of these k words as a substring (namely, for some u, v ∈ {a, b}
∗
and some i ≤ k, w = uwiv).
1
(b) [15 points] Construct a DFA, Aw1
that has 1 + |w1| states that accepts a word w if and only if
it contains w1 as a substring (namely, w = uw1v, for some u, v ∈ {a, b}
∗
).
(c) [Bonus 10 points] Construct a DFA, A(w1,…wk) that has at most 1 + Pk
i=1 |wi
| states that
accepts the language L(N(w1,…wk)) .
2