subset construction
The subset construction is a technique of turning a nondeterministic automaton into a deterministic^{} one, while keeping the accepting language^{} 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,\mathrm{\Sigma},\delta )$. The transition function $\delta $ is a function from $S\times \mathrm{\Sigma}$ to $P(S)$, which maps a pair $(s,a)$ to a subset $\delta (s,a)$ of $S$. Observe that $\delta $ can be extended to a function ${\delta}^{\prime}$ from $P(S)\times \mathrm{\Sigma}$ to $P(S)$ by setting
$${\delta}^{\prime}(T,a):=\bigcup \{\delta (t,a)\mid t\in T\}$$  (1) 
for any subset $T$ of $S$ and $a\in \mathrm{\Sigma}$. Note that ${\delta}^{\prime}(\mathrm{\varnothing},a)=\mathrm{\varnothing}$. What we have just done is turning a semiautomaton $(S,\mathrm{\Sigma},\delta )$ into a deterministic semiautomaton $({S}^{\prime},\mathrm{\Sigma},{\delta}^{\prime})$, where ${S}^{\prime}=P(S)$, the powerset of $S$.
It is easy to see, by induction^{} on the length of $u$, that ${\delta}^{\prime}(T,u)=\bigcup \{\delta (t,u)\mid t\in T\}$.
Next, given an NDFA $A=(S,\mathrm{\Sigma},\delta ,I,F)$, we turn it into a DFA ${A}^{\prime}:=({S}^{\prime},\mathrm{\Sigma},{\delta}^{\prime},{I}^{\prime},{F}^{\prime})$ as follows:

•
$({S}^{\prime},\mathrm{\Sigma},{\delta}^{\prime})$ is derived from $(S,\mathrm{\Sigma},\delta )$ by the construction above,

•
${I}^{\prime}=I$, and

•
${F}^{\prime}=\{T\subseteq S\mid T\cap F\ne \mathrm{\varnothing}\}$.
Since ${I}^{\prime}$ is an element of ${S}^{\prime}=P(S)$, and ${F}^{\prime}\subseteq {S}^{\prime}$, ${A}^{\prime}$ is a welldefined DFA.
Proposition 1.
$L(A)=L({A}^{\prime})$.
Proof.
$u\in L(A)$ iff $\delta (q,u)\cap F\ne \mathrm{\varnothing}$ (where $q\in I$) iff ${\delta}^{\prime}(I,u)\in {F}^{\prime}$ iff $u\in L({A}^{\prime})$. ∎
What happens if the NDFA in question contains $\u03f5$transitions (http://planetmath.org/EpsilonTransition)? Suppose $p\stackrel{\u03f5}{\to}q$ is an $\u03f5$transition, and $p\ne q$. Then ${\delta}^{\prime}(\{p\},\u03f5)=\{q\}\ne \{p\}$, which is not allowed in a DFA.
To get around this difficulty, we make a small modification on ${A}^{\prime}$. First, define, for any $T\subseteq S$, the $\u03f5$closure ${C}_{\u03f5}(T)$ of $T$ as the set
$${C}_{\u03f5}(T):=\{t\mid t\in {\delta}^{\prime}(T,{\u03f5}^{k}),k\ge 0\}$$  (2) 
For any $T\subseteq S$, ${\delta}^{\prime}({C}_{\u03f5}(T),a)={C}_{\u03f5}(T)$. If the automaton does not contain any $\u03f5$transitions, then ${C}_{\u03f5}(T)=T$.
Now, let NDFA $A$ be an $\u03f5$automaton (http://planetmath.org/EpsilonAutomaton), define ${A}^{\prime \prime}:=({S}^{\prime},\mathrm{\Sigma},{\delta}^{\prime \prime},{I}^{\prime \prime},{F}^{\prime \prime})$ as follows:

•
${S}^{\prime}=P(S)$,

•
${\delta}^{\prime \prime}(T,a)={\delta}^{\prime}({C}_{\u03f5}(T),a)$, where ${\delta}^{\prime}$ is defined in (1) above,

•
${I}^{\prime \prime}={C}_{\u03f5}(I)$, and

•
${F}^{\prime \prime}=\{T\subseteq S\mid {C}_{\u03f5}(T)\cap F\ne \mathrm{\varnothing}\}$.
By definition, ${A}^{\prime \prime}$ is a DFA, and it can be shown that $L({A}^{\prime \prime})=L(A)$. The proof is very similar to the one given here (http://planetmath.org/EveryEpsilonAutomatonIsEquivalentToAnAutomaton).
Title  subset construction 

Canonical name  SubsetConstruction 
Date of creation  20130322 19:02:00 
Last modified on  20130322 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  $\u03f5$closure 