Scribd
Upload
53 views2 pages

DFA Construction via Subset Method

The document explains the subset construction method for converting a Non-deterministic Finite Automaton (NFA) into a Deterministic Finite Automaton (DFA). It outlines the formal construction process, including the states, start state, final states, and transition function of the DFA. The algorithm details the step-by-step procedure to ensure the resulting DFA accepts the same language as the original NFA, while noting that the number of states in the DFA can be up to 2^n, where n is the number of states in the NFA.

Uploaded by

udayaveeramani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
53 views2 pages

DFA Construction via Subset Method

The document explains the subset construction method for converting a Non-deterministic Finite Automaton (NFA) into a Deterministic Finite Automaton (DFA). It outlines the formal construction process, including the states, start state, final states, and transition function of the DFA. The algorithm details the step-by-step procedure to ensure the resulting DFA accepts the same language as the original NFA, while noting that the number of states in the DFA can be up to 2^n, where n is the number of states in the NFA.

Uploaded by

udayaveeramani
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Subset Construction Method (Powerset

Construction)

Introduction
NFA → DFA conversion is done using the subset construction method. The main idea is that a DFA
must simulate all possible moves of the NFA by tracking sets of NFA states at each step. The
resulting DFA accepts exactly the same language as the NFA.

Formal Construction
Let N = (Q, Σ, δ, q■, F) be an NFA (without ε-moves). We construct an equivalent DFA D = (Q■, Σ,
δ■, q■■, F■) as follows:
1 States of DFA: Q■ = P(Q) (the power set of Q, i.e., all subsets of Q).
2 Start state: q■■ = {q■}.
3 Final states: F■ = { S ⊆ Q | S ∩ F ≠ ∅ } (any subset that contains at least one final state of
NFA).
4 Transition function: For each subset S = {q■, q■, …, q■} ⊆ Q and input symbol a ∈ Σ:
δ■(S, a) = δ(q■, a) ∪ δ(q■, a) ∪ … ∪ δ(q■, a).

Algorithm (Step-by-Step)
1 Start with DFA start state = {q■}.
2 For each unprocessed DFA state (subset of NFA states):
3 - For each input symbol a ∈ Σ:
4 - Compute union of δ(q, a) for all q in the subset.
5 - This gives the next DFA state (another subset of Q).
6 Repeat until no new subsets appear.
7 Mark any DFA subset containing an NFA final state as a DFA final state.

Important Points
1 Number of states in DFA can be up to 2■ if NFA has n states.
2 In practice, many subsets may be unreachable, so the actual DFA usually has fewer
states.
3 Subset construction guarantees equivalence: L(N) = L(D).

Example
NFA:
- States = {q0, q1}, Alphabet = {a}
- Start = q0, Final = {q1}
- δ(q0, a) = {q0, q1}, δ(q1, a) = ∅
DFA by subset construction:
- DFA States: ∅, {q0}, {q1}, {q0, q1}
- Start = {q0}
- Final = {q1}, {q0, q1}
- Transitions:
- {q0} -a→ {q0, q1}
- {q0, q1} -a→ {q0, q1}
- {q1} -a→ ∅
- ∅ -a→ ∅

You might also like