The product construction yields a DFA that accepts the union of two regular languages. Sometimes the construction gives a minimal DFA, but it often gives a DFA with more states than necessary. Show that even if we start with two minimal DFAs, the resulting DFA may not be minimal.

Explanation:

Suppose language B over alphabet Σ has a DFA

M = ( Q, Σ, δ, q1, F ).

Then, a DFA for the complementary language B is

M = ( Q, Σ, δ, q1, Q − F ).

The reason why M recognizes B is as follows. First note that M and M have the

same transition function δ. Thus, since M is deterministic, M is also deterministic.

Now consider any string w ∈ Σ∗

. Running M on input string w will result in M

ending in some state r ∈ Q. Since M is deterministic, there is only one possible state that M can end in on input w. If we run M on the same input w, then M will end in

the same state r since M and M have the same transition function. Also, since M is

deterministic, there is only one possible ending state that M can be in on input w.

Now suppose that w ∈ B. Then M will accept w, which means that the ending state

r ∈ F, i.e., r is an accept state of M. But then r 6∈ Q − F, so M does not accept w

since M has Q − F as its set of accept states. Similarly, suppose that w 6∈ B. Then

M will not accept w, which means that the ending state r 6∈ F. But then r ∈ Q − F,

so M accepts w. Therefore, M accepts string w if and only M does not accept string

w, so M recognizes language B. Hence, the class of regular languages is closed under

complement.

4. We say that a DFA M for a language A is minimal if there does not exist another

DFA M′

for A such that M′ has strictly fewer states than M. Suppose that M =

(Q, Σ, δ, q0, F) is a minimal DFA for A. Using M, we construct a DFA M for the

complement A as M = (Q, Σ, δ, q0, Q − F). Prove that M is a minimal DFA for A.

We prove this by contradiction. Suppose that M is not a minimal DFA for A. Then

there exists another DFA D for A such that D has strictly fewer states than M.

Now create another DFA D′ by swapping the accepting and non-accepting states of

D. Then D′

recognizes the complement of A. But the complement of A is just A,

so D′

recognizes A. Note that D′ has the same number of states as D, and M has

the same number of states as M. Thus, since we assumed that D has strictly fewer

states than M, then D′ has strictly fewer states than M. But since D′

recognizes A,

this contradicts our assumption that M is a minimal DFA for A. Therefore, M is a

minimal DFA for A.

5. Suppose A1 and A2 are defined over the same alphabet Σ. Suppose DFA M1 recognizes

A1, where M1 = (Q1, Σ, δ1, q1, F1). Suppose DFA M2 recognizes A2, where M2 =

(Q2, Σ, δ2, q2, F2). Define DFA M3 = (Q3, Σ, δ3, q3, F3) for A1 ∩ A2 as follows:

Set of states of M3 is

Q3 = Q1 × Q2 = { (x, y) | x ∈ Q1, y ∈ Q2 }.

The alphabet of M3 is Σ.

M3 has transition function δ3 : Q3 × Σ → Q3 such that for x ∈ Q1, y ∈ Q2,

and ℓ ∈ Σ,

δ3( (x, y), ℓ ) = ( δ1(x, ℓ), δ2(y, ℓ) ) .

The initial state of M3 is s3 = (q1, q2) ∈ Q3.

The set of accept states of M3 is

F3 = { (x, y) ∈ Q1 × Q2 | x ∈ F1 and y ∈ F2 } = F1 × F2.

Since Q3 = Q1 × Q2, the number of states in the new DFA M3 is |Q3| = |Q1| · |Q2|.

Thus, |Q3| < ∞ since |Q1| < ∞ and |Q2| < ∞.