subset construction

The subset construction is a technique of turning a non-deterministic automaton into a deterministicMathworldPlanetmath one, while keeping the accepting languagePlanetmathPlanetmath the same. This technique shows that an NDFA is no more powerful in terms of word acceptance than a DFA.

We begin by looking at a semiautomaton (S,Σ,δ). The transition function δ is a function from S×Σ to P(S), which maps a pair (s,a) to a subset δ(s,a) of S. Observe that δ can be extended to a function δ from P(S)×Σ to P(S) by setting

δ(T,a):={δ(t,a)tT} (1)

for any subset T of S and aΣ. Note that δ(,a)=. What we have just done is turning a semiautomaton (S,Σ,δ) into a deterministic semiautomaton (S,Σ,δ), where S=P(S), the powerset of S.

It is easy to see, by inductionMathworldPlanetmath on the length of u, that δ(T,u)={δ(t,u)tT}.

Next, given an NDFA A=(S,Σ,δ,I,F), we turn it into a DFA A:=(S,Σ,δ,I,F) as follows:

  • (S,Σ,δ) is derived from (S,Σ,δ) by the construction above,

  • I=I, and

  • F={TSTF}.

Since I is an element of S=P(S), and FS, A is a well-defined DFA.

Proposition 1.



uL(A) iff δ(q,u)F (where qI) iff δ(I,u)F iff uL(A). ∎

What happens if the NDFA in question contains ϵ-transitions ( Suppose pϵq is an ϵ-transition, and pq. Then δ({p},ϵ)={q}{p}, which is not allowed in a DFA.

To get around this difficulty, we make a small modification on A. First, define, for any TS, the ϵ-closure Cϵ(T) of T as the set

Cϵ(T):={ttδ(T,ϵk),k0} (2)

For any TS, δ(Cϵ(T),a)=Cϵ(T). If the automaton does not contain any ϵ-transitions, then Cϵ(T)=T.

Now, let NDFA A be an ϵ-automaton (, define A′′:=(S,Σ,δ′′,I′′,F′′) as follows:

  • S=P(S),

  • δ′′(T,a)=δ(Cϵ(T),a), where δ is defined in (1) above,

  • I′′=Cϵ(I), and

  • F′′={TSCϵ(T)F}.

By definition, A′′ is a DFA, and it can be shown that L(A′′)=L(A). The proof is very similar to the one given here (

Title subset construction
Canonical name SubsetConstruction
Date of creation 2013-03-22 19:02:00
Last modified on 2013-03-22 19:02:00
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 68Q05
Classification msc 03D10
Classification msc 68Q42
Synonym powerset construction
Related topic DeterministicFiniteAutomaton
Defines ϵ-closure