DFA (Deterministic Finite Automaton)

A 5-tuple M = (Q, Σ, δ, q₀, F) where:

• Q — finite set of states
• Σ — finite input alphabet
• δ: Q × Σ → Q — total transition function
• q₀ ∈ Q — initial state
• F ⊆ Q — set of accepting states

NFA (Nondeterministic Finite Automaton)

A 5-tuple M = (Q, Σ, δ, q₀, F) where:

• δ: Q × (Σ ∪ {ε}) → 2^Q — transition to a set of states
• May have ε-transitions (move without consuming input)
• Multiple transitions for same (state, symbol) allowed

ε-Closure

ε-closure(q) = set of all states reachable from q via zero or more ε-transitions.

Extended to sets: ε-closure(S) = ∪{ε-closure(q) | q ∈ S}

Subset Construction (NFA → DFA)

1. Start state = ε-closure({q₀})
2. For each DFA state S and symbol a:
   δ_DFA(S, a) = ε-closure(∪{δ_NFA(q,a) | q∈S})
3. Mark S as accepting if S ∩ F ≠ ∅
4. Repeat until no new states

DFA Minimization (Table-Filling)

1. Base: Mark (p,q) if exactly one is in F
2. Inductive: Mark (p,q) if ∃a: (δ(p,a), δ(q,a)) is marked
3. Repeat until no new marks
4. Merge all unmarked pairs into equivalence classes

Myhill-Nerode Theorem

A language L is regular iff the Myhill-Nerode equivalence relation ≡_L has finitely many equivalence classes.

The number of equivalence classes equals the number of states in the minimal DFA for L.

Pumping Lemma

If L is regular, ∃ pumping length p such that every string w ∈ L with |w| ≥ p can be written as w = xyz where:

• |y| ≥ 1  (y is non-empty)
• |xy| ≤ p
• ∀i ≥ 0: xy^i z ∈ L

Closure Properties

Regular languages are closed under:

• Union: L₁ ∪ L₂
• Concatenation: L₁ · L₂
• Kleene Star: L*
• Complement: L̄
• Intersection: L₁ ∩ L₂
• Reversal: L^R