Properties of Regular Languages

Let M₁ = (Q₁, Σ, δ₁, q₀₁, F₁) andM₂ = (Q₂, Σ, δ₂, q₀₂, F₂) be DFAs that recognize L₁ and L₂ respectively.

We construct a new NFA M = (Q, Σ, δ, q₀, F) that recognizes L₁ ∪ L₂:

• Q = {q₀} ∪ Q₁ ∪ Q₂ (where q₀ is a new state)
• δ(q₀, ε) = {q₀₁, q₀₂}
• For all q ∈ Q₁, a ∈ Σ: δ(q, a) = δ₁(q, a)
• For all q ∈ Q₂, a ∈ Σ: δ(q, a) = δ₂(q, a)
• F = F₁ ∪ F₂

This NFA accepts any string that is accepted by either M₁ or M₂. Since NFAs recognize exactly the regular languages, L₁ ∪ L₂ is regular.

Let M₁ = (Q₁, Σ, δ₁, q₀₁, F₁) andM₂ = (Q₂, Σ, δ₂, q₀₂, F₂) be DFAs that recognize L₁ and L₂ respectively.

We construct a new DFA M = (Q, Σ, δ, q₀, F) that recognizes L₁ ∩ L₂:

• Q = Q₁ × Q₂ (the Cartesian product of states)
• q₀ = (q₀₁, q₀₂)
• δ((q₁, q₂), a) = (δ₁(q₁, a), δ₂(q₂, a))
• F = F₁ × F₂ = {(q₁, q₂) | q₁ ∈ F₁ and q₂ ∈ F₂}

This DFA simulates M₁ and M₂ in parallel, and accepts a string if and only if both original DFAs accept it. Since DFAs recognize exactly the regular languages, L₁ ∩ L₂ is regular.

Let M = (Q, Σ, δ, q₀, F) be a DFA that recognizes L.

We construct a new DFA M' = (Q, Σ, δ, q₀, Q-F) that recognizes L̄.

The only difference is in the set of accepting states: M' accepts exactly when M rejects, and vice versa. Since DFAs recognize exactly the regular languages, L̄ is regular.

Let M₁ = (Q₁, Σ, δ₁, q₀₁, F₁) andM₂ = (Q₂, Σ, δ₂, q₀₂, F₂) be NFAs recognizing L₁ and L₂ respectively.

We construct a new NFA M = (Q, Σ, δ, q₀, F) for L₁·L₂:

• Q = Q₁ ∪ Q₂
• q₀ = q₀₁
• For all q ∈ Q₁, a ∈ Σ: δ(q, a) = δ₁(q, a)
• For all q ∈ F₁: δ(q, ε) = {q₀₂} ∪ δ₁(q, ε)
• For all q ∈ Q₂, a ∈ Σ: δ(q, a) = δ₂(q, a)
• F = F₂

This NFA simulates M₁ until it reaches an accepting state, at which point it can either continue in M₁ or transition to M₂'s start state. The NFA accepts if it finishes in an accepting state of M₂. Since NFAs recognize exactly the regular languages, L₁·L₂ is regular.

Let M = (Q, Σ, δ, q₀, F) be an NFA recognizing L.

We construct a new NFA M' = (Q', Σ, δ', q₀', F') for L*:

• Q' = Q ∪ {q₀'}
• q₀' is a new start state
• δ'(q₀', ε) = {q₀} (ε-transition to original start state)
• For all q ∈ Q, a ∈ Σ: δ'(q, a) = δ(q, a)
• For all qf ∈ F: δ'(qf, ε) = {q₀} (ε-transition from accepting states back to start)
• F' = F ∪ {q₀'} (new start state is also accepting)

This NFA can match the empty string (by accepting immediately from q₀'), single iterations of L (by following the original NFA), or multiple iterations (by going back to the start state after each accepted string). Since NFAs recognize exactly the regular languages, L* is regular.

Let M = (Q, Σ, δ, q₀, F) be an NFA recognizing L.

We construct a new NFA M' = (Q, Σ, δ', F', {q₀}) for Lᴿ as follows:

• Use the same set of states Q
• Make the original start state q₀ the only accepting state in M'
• Make the original accepting states F the set of start states in M' (we can simulate this with a new start state and ε-transitions)
• Reverse all transitions: for each transition δ(q, a) = p in M, add a transition δ'(p, a) = q in M'

This NFA processes strings in reverse, starting from what were the accepting states and accepting if it reaches what was the start state. Since NFAs recognize exactly the regular languages, Lᴿ is regular.

Let L be a regular language, and let M = (Q, Σ, δ, q₀, F) be a DFA that recognizes L. Set p = |Q| (the number of states in M).

Consider any string w ∈ L with |w| ≥ p. When M processes w, it goes through a sequence of |w|+1 states: r₀, r₁, ..., r|w|, where r₀ = q₀and r|w| ∈ F.

Since |w| ≥ p = |Q|, by the Pigeonhole Principle, there must be at least one state that appears more than once in the first p+1 states of this sequence. Let rᵢ = rⱼfor some 0 ≤ i < j ≤ p.

We can decompose w as follows:
x = first i symbols of w (which take M from r₀ to rᵢ)
y = symbols from positions i+1 to j (which take M from rᵢ back to rᵢ = rⱼ)
z = remaining symbols (which take M from rⱼ to an accepting state)

This decomposition satisfies all three conditions:
1. |y| = j-i > 0 (since i < j)
2. |xy| = j ≤ p
3. For any i ≥ 0, xyᶦz ∈ L, because:
  - x takes M from r₀ to rᵢ
  - Each repetition of y takes M from rᵢ back to rᵢ
  - z takes M from rᵢ to an accepting state

(⇒) If L is regular, then RL has finitely many equivalence classes:

Let M = (Q, Σ, δ, q₀, F) be a DFA for L. For each state q ∈ Q, define Sq to be the set of all strings that lead from q₀ to q in M. That is, Sq = {w ∈ Σ* | δ̂(q₀, w) = q}.

We can show that if x, y ∈ Sq for the same q, then x RL y. This is because for any suffix z, both xz and yz will end up in the same state after processing z, starting from q. Thus, either both are accepted or both are rejected.

Since M has finitely many states, there are finitely many sets Sq, and therefore finitely many equivalence classes under RL.

(⇐) If RL has finitely many equivalence classes, then L is regular:

Let the equivalence classes of RL be [x₁], [x₂], ..., [xₙ]. We construct a DFA M = (Q, Σ, δ, q₀, F) as follows:

• Q = {[x₁], [x₂], ..., [xₙ]} (the set of equivalence classes)
• q₀ = [ε] (the equivalence class of the empty string)
• F = {[x] | x ∈ L} (the equivalence classes containing strings in L)
• δ([x], a) = [xa] for all [x] ∈ Q and a ∈ Σ

The transition function is well-defined: if x RL y, then xa RL ya for any a ∈ Σ.

We can then prove that L(M) = L by showing that for any string w, δ̂(q₀, w) = [w], and w ∈ L if and only if [w] ∈ F.

Thus, L is recognized by a DFA and is therefore regular.

Minimality: The constructed DFA is minimal because if we were to merge any two states [x] and [y] where x and y are not equivalent under RL, there would exist some string z such that xz ∈ L but yz ∉ L (or vice versa), meaning the merged DFA would not correctly recognize L.