Finite Automata & Regular Languages

What is Theory of Computation?

TOC answers a fundamental question: What can computers compute, and what can they NOT?

We study increasingly powerful "machines" — DFA, PDA, Turing Machine — each more capable than the last. Regular languages are what the simplest machine (DFA) can handle.

DFA — The Simplest Machine

Analogy: A vending machine. It has a fixed set of states (idle, selected, paid, dispensing). Given an input (button press, coin), it transitions to the next state. No memory beyond its current state.

DFA = (Q, Σ, δ, q₀, F)

Q   = finite set of states (the machine's possible "moods")
Σ   = input alphabet (allowed symbols)
δ   = transition function  δ: Q × Σ → Q  (one destination per input)
q₀  = start state (initial mood)
F   = set of accepting states (the "happy" endings)

The DFA ACCEPTS a string w iff after reading all of w, it ends in a state in F.

Example DFA: Language L = {strings over {0,1} that end in 1}

States: q0 (even end or start), q1 (last symbol was 1)

     0       1
q0 ──→ q0   q0 ──→ [q1]   ← accepting state (in brackets)
q1 ──→ q0   q1 ──→ [q1]

String "101":
  q0 →(1)→ q1 →(0)→ q0 →(1)→ q1 ← in F: ACCEPT
String "100":
  q0 →(1)→ q1 →(0)→ q0 →(0)→ q0 ← not in F: REJECT

NFA — Multiple Paths, Accept If Any Succeeds

Analogy: A choose-your-own-adventure book. At some points you can go in multiple directions simultaneously. If ANY path leads to a happy ending, you win.

NFA = (Q, Σ, δ, q₀, F)
δ: Q × Σ → 2^Q  (transition to a SET of states, possibly empty!)

NFA accepts string w iff at LEAST ONE computation path leads to an accepting state.
Empty transition set = dead end for that path.

Key fact: DFA and NFA recognise EXACTLY the same languages! NFA is NOT more powerful.

NFA to DFA — Subset Construction

Convert NFA with n states → DFA with at most 2^n states

Algorithm:
1. Start state of DFA = ε-closure({q₀_NFA})
2. For each DFA state S (a SET of NFA states) and each symbol a:
   next_state = ε-closure( union of δ_NFA(s, a) for all s in S )
3. DFA state is ACCEPTING iff it contains any NFA accepting state

Example NFA to DFA:

NFA over {a,b}: accepts strings ending in "ab"
States: q0(start), q1, q2(accept)
δ: q0→a→{q0,q1}, q0→b→{q0}, q1→b→{q2}

DFA states (subsets):
{q0}: a→{q0,q1}, b→{q0}
{q0,q1}: a→{q0,q1}, b→{q0,q2} ← accepting (contains q2)
{q0,q2}: a→{q0,q1}, b→{q0} ← accepting (contains q2)

Regular Expressions — The Pattern Language

a      = matches symbol a
ε      = matches empty string
∅      = matches nothing
R|S    = matches R or S (union)
RS     = matches R followed by S (concatenation)
R*     = matches R zero or more times (Kleene star)

Examples:
  (0|1)*1     = all binary strings ending in 1
  a*b*        = zero or more a's followed by zero or more b's
  (ab)*       = even-length strings alternating a,b: "", ab, abab...

Kleene's Theorem: Regular expressions and DFAs describe the SAME class of languages (regular languages).

Pumping Lemma — Proving a Language is NOT Regular

Intuition: A DFA has finite memory (finite states). If you give it a VERY long string, it must revisit a state — creating a "loop." That loop can be repeated any number of times without breaking acceptance.

Formal statement:

If L is regular, then ∃ pumping length p such that:
Every string w ∈ L with |w| ≥ p can be split as w = xyz where:
  1. |xy| ≤ p        (loop is in the first p characters)
  2. |y| ≥ 1         (y is non-empty — this is the "loop")
  3. ∀ i ≥ 0: xyⁱz ∈ L  (pumping y any number of times stays in L)

How to use it to prove NON-regularity:

1. Assume L is regular (for contradiction)
2. Let p be the pumping length
3. Choose a specific string w ∈ L with |w| ≥ p  (choose cleverly!)
4. Show that NO MATTER HOW the adversary splits w = xyz (obeying rules 1,2),
   pumping (xy²z or xy⁰z) gives a string NOT in L
5. Contradiction → L is not regular

Classic Example: L = {aⁿbⁿ | n ≥ 0} is NOT regular.

Choose w = aᵖbᵖ (length 2p ≥ p) ✓
Since |xy| ≤ p: xy must be entirely within the first p a's
So y = aʲ for some j ≥ 1

Pump up: xy²z = aᵖ⁺ʲbᵖ
  Number of a's (p+j) ≠ number of b's (p) → NOT in L!
Contradiction. L is not regular. □

DFA Minimisation — Merge Identical States

Two states p, q are DISTINGUISHABLE if there exists some string w such that
  δ*(p, w) ∈ F XOR δ*(q, w) ∈ F
  (one leads to acceptance, the other to rejection)

Table-filling algorithm:
  Step 1: Mark all pairs (accepting, non-accepting) as distinguishable
  Step 2: If δ(p,a) and δ(q,a) are distinguishable → mark (p,q) as distinguishable
  Step 3: Repeat step 2 until no new marks
  Step 4: Merge all UNMARKED pairs (they behave identically)

Closure Properties

Regular languages are closed under ALL these operations:

Union (R ∪ S), Intersection (R ∩ S), Complement (R̄),
Concatenation (RS), Kleene star (R*), Reversal,
Homomorphism, Inverse homomorphism

Not closed: Infinite union or intersection of regular languages may not be regular.

Quick Check

Q1. DFA accepts language {w | w has even number of 1s}. How many states needed?

Two states: q_even (accept), q_odd
q_even →1→ q_odd →1→ q_even
q_even →0→ q_even,  q_odd →0→ q_odd
Minimum = 2 states

Q2. NFA has 3 states. DFA built by subset construction has at most how many states? Answer: 2^3 = 8 states (worst case). Usually fewer in practice.

Q3. Is L = {ww | w ∈ {0,1}} regular? Use pumping lemma. Answer: Not regular. Choose w = 0ᵖ0ᵖ. Since |xy| ≤ p, y = 0ʲ within first p zeros. xy²z = 0^(p+j)0^p which is NOT of the form ww unless j=0, but |y|≥1. Contradiction.*

Key Points