Deterministic Finite Automata (DFAs)

We prove that any DFA recognizing L = {w | w ends with ab} requires at least 3 states.

Suppose, for contradiction, that there exists a DFA M with fewer than 3 states that recognizes L. Since M has at most 2 states, by the pigeonhole principle, when processing a string of length ≥ 2, some state must be visited more than once.

Consider the strings ε, a, and ab.

Let q0 be the start state. Let q1 = δ̂(q0, a) be the state after reading a. Since M has at most 2 states, either q1 = q0 or M has exactly 2 states.

Case 1: If q1 = q0, then δ̂(q0, a) = δ̂(q0, aa) = δ̂(q0, aaa) = ..., meaning that the DFA cannot distinguish between strings ending in a and strings ending in ab.

Case 2: If M has exactly 2 states, q0 and q1, then consider q2 = δ̂(q1, b). By our assumption, q2 must be either q0 or q1.

If q2 = q0, then ab and ε end in the same state, which contradicts the language definition since ab ∈ L but ε ∉ L.

If q2 = q1, then a and ab end in the same state, which contradicts the language definition since ab ∈ L but a ∉ L.

Therefore, a DFA for L requires at least 3 states.

We prove that the table-filling algorithm correctly identifies all and only the pairs of distinguishable states.

Two states p, q ∈ Q are distinguishable if there exists a string w ∈ Σ* such that either δ̂(p, w) ∈ F and δ̂(q, w) ∉ F, or δ̂(p, w) ∉ F and δ̂(q, w) ∈ F.

Claim 1: If states p, q are distinguishable, the algorithm will mark them.

Proof by induction on the length of the distinguishing string:

Base case: If p, q are distinguished by ε, then one is accepting and the other is not. The algorithm marks these pairs in the initialization step.

Inductive step: Assume all pairs distinguishable by strings of length ≤ k are marked. Consider states p, q distinguishable by a string w = ax of length k+1, where a ∈ Σ and |x| = k.

Let p' = δ(p, a) and q' = δ(q, a). Since w = ax distinguishes p and q, the string x must distinguish p' and q'. By the induction hypothesis, (p', q') is marked. Therefore, in the iterative step, when considering (p, q) and symbol a, the algorithm will mark (p, q) because (δ(p, a), δ(q, a)) is marked.

Claim 2: If the algorithm marks a pair of states, they are distinguishable.

Proof by induction on the iteration number:

Base case: In the initialization step, we mark pairs where one state is accepting and the other is not. These are distinguished by the empty string ε.

Inductive step: Assume all pairs marked in iterations ≤ k are distinguishable. Consider a pair (p, q) marked in iteration k+1. This occurs because there exists a symbol a ∈ Σ such that (δ(p, a), δ(q, a)) was marked in a previous iteration. By the induction hypothesis, δ(p, a) and δ(q, a) are distinguishable by some string x. Therefore, p and q are distinguishable by the string ax.

Thus, the algorithm correctly identifies all distinguishable state pairs, and the resulting DFA after merging indistinguishable states is minimal and language-equivalent to the original.

For every n ≥ 1, consider the language Ln = {w ∈ {0,1}* | |w| mod n = 0} of all strings whose length is a multiple of n.

To recognize Ln, a DFA needs to count modulo n. We can construct an n-state DFA Mn = (Q, Σ, δ, q0, F) where:

• Q = {0, 1, 2, ..., n-1}
• Σ = {0, 1}
• q0 = 0
• F = {0}
• δ(i, a) = (i + 1) mod n for all i ∈ Q, a ∈ Σ

The state i represents the fact that the length of the string read so far is congruent to i modulo n. Thus, Mn accepts exactly the strings whose length is a multiple of n.

Now we prove that n states are necessary. Consider the strings ε, 0, 00, ..., 0n-1. These strings have lengths 0, 1, 2, ..., n-1. For any two distinct strings 0i and 0j with 0 ≤ i < j < n, the string 0n-j+i distinguishes them because 0i · 0n-j+i = 0n+i-j has length n+i-j, which is congruent to i-j mod n and is not a multiple of n (since 0 < j-i < n), while 0j · 0n-j+i = 0n+i has length n+i, which is congruent to i mod n.

Since there are n distinguishable states in any DFA for Ln, at least n states are necessary.

We prove that the emptiness problem for DFAs is decidable in linear time.

Given a DFA M = (Q, Σ, δ, q0, F), L(M) = ∅ if and only if no accepting state is reachable from the start state.

Algorithm:

1. Perform a breadth-first search (BFS) or depth-first search (DFS) starting from q0.
2. If any accepting state is reached during the search, return "L(M) is not empty."
3. If the search completes without reaching any accepting state, return "L(M) is empty."

Correctness: The search explores all states reachable from q0. If an accepting state is reachable, there exists a string that leads from q0 to that accepting state, which means L(M) is not empty. Conversely, if no accepting state is reachable, then no string can lead from q0 to an accepting state, so L(M) is empty.

Time Complexity: BFS or DFS has time complexity O(|Q| + |δ|) = O(|Q| + |Q|·|Σ|) = O(|Q|·|Σ|), which is linear in the size of the DFA representation.

Given DFAs M1 = (Q1, Σ, δ1, q1, F1) and M2 = (Q2, Σ, δ2, q2, F2), we construct a DFA M = (Q, Σ, δ, q0, F) for L(M1) ∪ L(M2):

• Q = Q1 × Q2 (Cartesian product)
• q0 = (q1, q2)
• F = {(r₁, r₂) | r₁ ∈ F₁ or r₂ ∈ F₂}
• δ((r1, r2), a) = (δ1(r1, a), δ2(r2, a))

This construction simulates both machines in parallel, accepting if either would accept.

For intersection, we use the same construction as union but with a different acceptance condition:

• F = {(r₁, r₂) | r₁ ∈ F₁ and r₂ ∈ F₂}

The rest of the construction (Q, q0, δ) remains identical to the union case.

Given a DFA M = (Q, Σ, δ, q0, F), we construct a DFA M' = (Q, Σ, δ, q0, Q-F) that recognizes Σ* - L(M):

• Use the same states, alphabet, transitions, and start state
• F' = Q - F (accept states become non-accept and vice versa)

This machine accepts precisely the strings that M rejects, and rejects the strings that M accepts.

Given DFAs M1 = (Q1, Σ, δ1, q1, F1) and M2 = (Q2, Σ, δ2, q2, F2), we construct a DFA M = (Q, Σ, δ, q0, F) for L(M1)·L(M2):

• Q = Q1 × 2Q2 (Cartesian product of Q₁ and power set of Q₂)
• q0 = (q1, S0) where S0 = {q₂} if q1 ∈ F1, otherwise S0 = ∅
• F = {(r, S) | S ∩ F₂ ≠ ∅} (accept if any state in S is accepting in M₂)
• For the transition function δ, for each (r, S) ∈ Q and a ∈ Σ:
  • r' = δ1(r, a) (next state in M₁)
  • S' = {δ₂(s, a) | s ∈ S} (next states in M₂ from all current states)
  • If r' ∈ F1, add q2 to S' (start M₂ if M₁ accepts)
  • δ((r, S), a) = (r', S')

This construction keeps track of: 1. The current state in M₁2. All possible states in M₂ that might be active 3. It adds the start state of M₂ whenever M₁ reaches an accepting state

Given a DFA M = (Q, Σ, δ, q0, F), we construct a DFA M' = (Q', Σ, δ', q0', F') for L(M)*:

• Q' = 2Q (the power set of Q)
• q0' = E({q₀}) where E(S) is the ε-closure of S (states reachable from S by ε-transitions in the NFA construction)
• F' = {S ⊆ Q | S ∩ F ≠ ∅ or S = E({q₀})} (accept if any state in S is accepting or if S is the initial state set)
• For the transition function δ', for each S ⊆ Q and a ∈ Σ:
  • δ'(S, a) = E({δ(q, a) | q ∈ S})
  • where E(T) = T ∪ {q₀ | T ∩ F ≠ ∅} (add start state if any state in T is accepting)

This construction simulates the standard NFA construction for Kleene star (which adds an ε-transition from accept states back to the start state) directly as a DFA using the subset construction.

(1 ⇒ 2): Suppose L is recognized by a DFA M = (Q, Σ, δ, q0, F) with n states.

Define f: Σ* → Q by f(x) = δ̂(q0, x). If f(x) = f(y), then for any z ∈ Σ*:

δ̂(q0, xz) = δ̂(f(x), z) = δ̂(f(y), z) = δ̂(q0, yz)

Therefore xz ∈ L ⟺ yz ∈ L, so x ≡L y. Since |Q| = n, there are at most n equivalence classes.

(2 ⇒ 1): Suppose ≡L has k equivalence classesC1, C2, ..., Ck. Construct DFA M = (Q, Σ, δ, q0, F) where:

• Q = {C₁, C₂, ..., Cₖ}
• q0 = Ci where ε ∈ Ci
• F = {Cᵢ : Cᵢ ∩ L ≠ ∅}
• δ(Ci, a) = Cj where for any x ∈ Ci, xa ∈ Cj

This construction is well-defined because if x, y ∈ Ci then x ≡L y, which implies xa ≡L ya for any a.

(3): The minimal DFA has exactly one state per equivalence class by construction, and no further reduction is possible since distinct equivalence classes are distinguishable.

We construct languages L1 and L2 whose union requires exactly mn states.

Let L1 = {w ∈ {a,b,c}* | |w|a ≡ 0 (mod m)} (number of a is divisible by m).

Let L2 = {w ∈ {a,b,c}* | |w|b ≡ 0 (mod n)} (number of b is divisible by n).

The minimal DFA for L1 has m states (counting a mod m). The minimal DFA for L2 has n states (counting b mod n).

For L1 ∪ L2, consider strings ai bj for0 ≤ i < m, 0 ≤ j < n. Each such string reaches a different state in the product construction, and all mn states are reachable and distinguishable.

To see they are distinguishable: ai bj and ai' bj'with (i,j) ≠ (i',j') can be distinguished by appendingam-i or bn-j appropriately.

To test if L(M) = Σ* for DFA M = (Q, Σ, δ, q0, F):

Algorithm: L(M) = Σ* if and only if L(M̄) = ∅, where M̄ is the complement DFA.

1. Construct M̄ = (Q, Σ, δ, q0, Q - F) (flip accept states)
2. Test if L(M̄) is empty using reachability from q0
3. Return "universal" if L(M̄) = ∅, otherwise "not universal"

Correctness: L(M) = Σ* ⟺ Σ* - L(M) = ∅ ⟺ L(M̄) = ∅

Time Complexity: O(|Q| + |δ|) for the reachability analysis.