Answer:
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.
Answer:
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| < ∞.
