MODULE 2 — REVISION NOTES

Finite Automata · NFA · DFA · NFA→DFA Conversion · DFA Minimization

Computational Theory

1. Finite Automata — Basics

1.1 What is a Finite Automaton?
A Finite Automaton (FA) is a mathematical model of computation that accepts or rejects strings. It has a
finite number of states and transitions between them based on input symbols.

Component Meaning
Q Finite set of STATES
Σ (Sigma) Input ALPHABET (set of symbols)
δ (delta) TRANSITION FUNCTION: δ(state, input) → next state(s)
q₀ START / INITIAL STATE (only one)
F Set of FINAL / ACCEPT STATES (can be multiple)

1.2 DFA vs NFA — Key Differences

Feature DFA (Deterministic) NFA (Non-Deterministic)
Full form Deterministic FA Non-deterministic FA
Transitions Exactly 1 per (state, input) 0, 1, or more per (state, input)
ε-transitions NOT allowed ALLOWED
Next state Always exactly one Set of possible states
Backtracking Not needed Uses parallel paths
Acceptance One path to final state At least one path to final state
Power Equal to NFA Equal to DFA
Complexity More states (after conversion) Fewer states (compact)

KEY FACT — Equivalence

DFA and NFA are EQUALLY POWERFUL. Every NFA can be converted to an equivalent
DFA (Subset Construction / Power Set Method). They accept the same class of languages
— Regular Languages.

1.3 NFA Formal Definition

NFA = (Q, Σ, δ, q₀, F) where δ: Q × (Σ ∪ {ε}) → 2^Q (returns a SET of states, including empty set)
• A string w is ACCEPTED by NFA if there EXISTS at least one path through the NFA that ends
in a final state.
 • A string is REJECTED only if ALL possible paths end in non-final states or get stuck.

2. NFA → DFA Conversion (Subset / Power Set Construction)

2.1 Why Convert?
DFA is easier to implement in hardware/software. Every NFA is converted to an equivalent DFA using
the Subset Construction Method. The DFA states represent SETS of NFA states.

2.2 Step-by-Step Algorithm

1. Start with the NFA's initial state as the first DFA state (as a set: {q₀}).
2. For each DFA state (set of NFA states) and each input symbol, compute the set of all reachable
NFA states.
3. Each unique set of NFA states becomes a new DFA state.
4. If a DFA state (set) contains any NFA final state → that DFA state is a FINAL STATE.
5. Mark dead/trap state as ∅ (empty set) — transitions that go nowhere.
6. Repeat until no new DFA states are created.

Important Rule
DFA state is FINAL if it contains at least one NFA final state. DFA state ∅ (dead state) is a
NON-FINAL state — transitions loop back on ∅.

2.3 ε-Closure (for NFA with ε-transitions)

ε-closure(q) = set of all states reachable from q using ε-transitions alone (including q itself).
• Always start by computing ε-closure of initial state.
• When computing transitions: δ*(S, a) = ε-closure(union of δ(q, a) for all q in S)

3. Minimization of DFA
3.1 Why Minimize?
A DFA may have redundant / equivalent states that can be merged. The Minimized DFA has the
FEWEST possible states while accepting the same language.

3.2 Table Filling Method (Myhill-Nerode)

7. Remove all UNREACHABLE states (states not reachable from initial state).
8. Create a table of all pairs of states (p, q) where p ≠ q.
9. MARK pairs where one is Final and other is Non-Final as DISTINGUISHABLE (base case).
10. For each unmarked pair (p, q) and each input symbol a: if (δ(p,a), δ(q,a)) is already marked →
mark (p, q) too.
 11. Repeat step 4 until no new pairs can be marked.
12. All UNMARKED pairs are EQUIVALENT — merge them into one state.
13. Construct the minimized DFA.

Quick Memory Aid

MARKED = Distinguishable (different behavior) → CANNOT merge UNMARKED =
Equivalent (same behavior) → CAN merge Always start: Final vs Non-Final pairs are
always marked!

3.3 Partitioning Method (Alternative — Faster)

14. Partition 1: Divide states into two groups — Final (F) and Non-Final (Q−F).
15. For each group, check if all states in the group go to the SAME group on each input.
16. If not → split that group further.
17. Repeat until no more splits are possible.
18. Each final group = one minimized state.

4. Solved Exam Questions

Q1. NFA→DFA: All binary strings ending with '01'
Language
L = all binary strings over {0,1} that end with '01' Examples: 01, 001, 101, 0001, 1101, ...
R.E. = (0+1)*01

Step 1: Construct NFA

We need 3 states: q0 (start), q1 (just read a 0), q2 (read 01 → final).
• q0 = Start state: reads any characters, stays in q0 on both 0 and 1, but also moves to q1 on 0
• q1 = Intermediate: we just read a '0' that could be the second-last bit
• q2 = Final: we just completed reading '01'

NFA Transition Table (→ = initial, * = final)

State 0 1
→ q0 {q0, q1} {q0}
q1 ∅ {q2}
* q2 ∅ ∅

NFA Description:
• From q0: on '0' → go to {q0, q1} (stay looping OR start tracking potential '01')
• From q0: on '1' → go to {q0} only (stay looping, '1' cannot start '01')
 • From q1: on '1' → go to {q2} (we complete '01'!)
• From q1: on '0' → ∅ (another 0 means the first 0 wasn't the right one — but q0 handles this)
• q2 is the final state — string accepted.

Step 2: NFA → DFA Conversion (Subset Construction)

Each DFA state = a SET of NFA states. Start with {q0}.

Computing DFA transitions:

• DFA state {q0}: on 0 → δ(q0,0) = {q0,q1} | on 1 → δ(q0,1) = {q0}
• DFA state {q0,q1}: on 0 → δ(q0,0)∪δ(q1,0) = {q0,q1}∪∅ = {q0,q1} | on 1 → δ(q0,1) ∪δ(q1,1) =
{q0}∪{q2} = {q0,q2}
• DFA state {q0,q2}: on 0 → δ(q0,0)∪δ(q2,0) = {q0,q1}∪∅ = {q0,q1} | on 1 → δ(q0,1) ∪δ(q2,1) =
{q0}∪∅ = {q0}
• No new states! We have: {q0}, {q0,q1}, {q0,q2}

Rename for simplicity: A = {q0}, B = {q0,q1}, C = {q0,q2}

C contains q2 (NFA final state) → C is DFA FINAL STATE

DFA Transition Table (→ = initial, * = final)

DFA State NFA States On 0 On 1
→ A {q0} B A
B {q0,q1} B C
* C {q0,q2} B A

DFA Description
→ A (start): on 0 → B, on 1 → A B: on 0 → B, on 1 → C ★ C (final): on 0 → B, on 1 → A
Verify: '01' → A→B→C ✓ (accepted) Verify: '101' → A→A→B→C ✓ (accepted) Verify: '10'
→ A→A→B (not final) ✗ (rejected)
Q2. NFA→DFA: All binary strings where second last bit is 1
Language
L = all binary strings over {0,1} where the second-to-last bit is 1 Examples: 10, 11, 010, 011,
110, 111, 0010, ... R.E. = (0+1)*1(0+1)

Step 1: Construct NFA

3 states: q0 (start/loop), q1 (just read the '1' that is second-last), q2 (final — read the last bit).
• q0 = Start, loops on 0 and 1 (could keep reading), also goes to q1 on '1'
• q1 = We just read a '1' that might be the second-last bit
• q2 = Final: we read the last bit after q1

NFA Transition Table

State 0 1
→ q0 {q0} {q0, q1}
q1 {q2} {q2}
* q2 ∅ ∅

• From q0: on '0' → {q0} (loop); on '1' → {q0, q1} (loop AND start tracking)
• From q1: on '0' or '1' → {q2} (we read the last bit — done!)
• q2 is final — the second-last bit was '1'

Step 2: NFA → DFA Conversion

Start with {q0}:
• {q0}: on 0 → {q0}, on 1 → {q0,q1}
• {q0,q1}: on 0 → δ(q0,0)∪δ(q1,0) = {q0}∪{q2} = {q0,q2} | on 1 → δ(q0,1) ∪δ(q1,1) =
{q0,q1}∪{q2} = {q0,q1,q2}
• {q0,q2}: on 0 → δ(q0,0)∪δ(q2,0) = {q0}∪∅ = {q0} | on 1 → δ(q0,1) ∪δ(q2,1) = {q0,q1} ∪∅ =
{q0,q1}
• {q0,q1,q2}: on 0 → {q0}∪{q2}∪∅ = {q0,q2} | on 1 → {q0,q1} ∪{q2} ∪∅ = {q0,q1,q2}

Rename: A={q0}, B={q0,q1}, C={q0,q2}, D={q0,q1,q2}

C contains q2 → FINAL. D contains q2 → FINAL.

DFA Transition Table

DFA State NFA States On 0 On 1
→ A {q0} A B
B {q0,q1} C D
 * C {q0,q2} A B
* D {q0,q1,q2} C D

DFA Description
→ A (start): on 0 → A, on 1 → B B: on 0 → C, on 1 → D ★ C (final): on 0 → A, on 1 → B
★ D (final): on 0 → C, on 1 → D Verify: '10' → A→B→C ✓ (accepted, 2nd last = 1) Verify:
'11' → A→B→D ✓ (accepted) Verify: '00' → A→A→A ✗ (rejected) Verify: '110' →
A→B→D→C ✓ (accepted)
Q3. Minimize the DFA (5 states: A→E, final=E)
Given DFA
Initial state: A | Final state: E Alphabet: {0, 1}

Given Transition Table

State 0 1
→ A B C
B B D
C B C
D B E
* E B C

Step 1: Check for Unreachable States

From A: on 0→B, on 1→C. From B: on 1→D. From D: on 1→E.
All states A, B, C, D, E are reachable. None to remove.

Step 2: Initial Partition

• Group 1 (Final states): {E}
• Group 2 (Non-Final states): {A, B, C, D}

Step 3: Refine Partitions

Check if {A, B, C, D} can be split by looking at where they go on each input:

State On 0 (group) On 1 (group)

A B (G2) C (G2)
B B (G2) D (G2)
C B (G2) C (G2)
D B (G2) E (G1)

D goes to E (Group 1) on '1', while A, B, C go to Group 2 on '1' → D is DIFFERENT!

• Split: Group 2a = {A, B, C}, Group 2b = {D}

Now check {A, B, C} again:

State On 0 (group) On 1 (group)

A B (G2a) C (G2a)
 B B (G2a) D (G2b)
C B (G2a) C (G2a)

B goes to D (Group 2b) on '1', while A and C go to Group 2a on '1' → B is DIFFERENT!

• Split: Group 2a1 = {A, C}, Group 2a2 = {B}

Now check {A, C}:

State On 0 (group) On 1 (group)

A B (G2a2) C (G2a1)
C B (G2a2) C (G2a1)

A and C have IDENTICAL transitions (same groups)! → A and C are EQUIVALENT → merge!

Final Partitions:
• {A, C} → merge into one state (call it AC)
• {B} → stays as B
• {D} → stays as D
• {E} → stays as E (final)

Minimized DFA Transition Table

Let AC = merged state of A and C (use A's transitions since A is initial):

State 0 1
→ AC (=A=C) B AC
B B D
D B E
* E B AC

Result
Original DFA had 5 states: A, B, C, D, E Minimized DFA has 4 states: AC, B, D, E States A
and C were equivalent (identical transitions) and were merged!
Q4. Minimize the DFA (6 states: A→F, final=C,D,E)
Given DFA
Initial state: A | Final states: C, D, E Alphabet: {0, 1}

Given Transition Table

State 0 1
→ A B C
B A D
* C E F
* D E F
* E E F
F F F

Step 1: Check Unreachable States

From A: 0→B, 1→C. From B: 0→A, 1→D. From C: 0→E, 1→F. From D: 0→E, 1→F. All reachable.

Step 2: Initial Partition

• Group F (Final): {C, D, E}
• Group NF (Non-Final): {A, B, F}

Step 3: Refine {C, D, E}

State On 0 → (group) On 1 → (group)
C E (F) F (NF)
D E (F) F (NF)
E E (F) F (NF)

C, D, E all go to same groups on all inputs → C ≡ D ≡ E → All EQUIVALENT! Merge into {C,D,E}.

Step 4: Refine {A, B, F}

State On 0 → (group) On 1 → (group)
A B (NF) C (F)
B A (NF) D (F)
F F (NF) F (NF)

F goes to F (NF) on '1' while A and B go to C/D (F) on '1' → F is DIFFERENT!

 • Split: {A, B} and {F}

Check {A, B}:

State On 0 → (group) On 1 → (group)

A B ({A,B}) C ({C,D,E})
B A ({A,B}) D ({C,D,E})

A and B both go within {A,B} on '0' and to {C,D,E} on '1' → A ≡ B → EQUIVALENT! Merge into {A,B}.

Final Partitions:
• {A, B} → merge into AB (A is initial, so AB is initial state)
• {C, D, E} → merge into CDE (FINAL state)
• {F} → stays as F (non-final, dead/trap state)

Minimized DFA Transition Table

State 0 1
→ AB AB CDE
* CDE CDE F
F F F

Result
Original DFA had 6 states: A, B, C, D, E, F Minimized DFA has only 3 states: AB, CDE, F
Merged: A ≡ B (into AB) | C ≡ D ≡ E (into CDE) F remains as the dead/trap state. Verify:
'01' → AB→AB→CDE ✓ (accepted — C was final) Verify: '1' → AB→CDE ✓ (accepted)
Verify: '11' → AB→CDE→F ✗ (rejected — F is not final)

5. Quick Reference Summary

Topic Key Rule Remember
NFA transition δ: Q×Σ → 2^Q (set of states) Can return ∅ or multiple states
DFA transition δ: Q×Σ → Q (exactly one state) Always exactly one next state
NFA accepts ≥1 path reaches final state Any one valid path = accept
Subset construction DFA state = set of NFA states New DFA state per unique NFA
set
DFA final state Set contains any NFA final state Even one final state → mark it
Dead state (∅) Trap state — non-final Loop on all inputs
Min: base case Final vs Non-Final → MARKED Always mark these first
Min: propagate If δ(p,a),δ(q,a) marked → mark Repeat until no change
(p,q)
Min: merge Unmarked pairs → equivalent Build new minimized DFA
Equivalent DFA DFA and NFA accept same Regular Languages only
languages

Good luck! 🎯 — Module 2 Revision Notes | NFA · DFA · Minimization