subset construction

The subset construction is a technique of turning a non-deterministic 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 well-defined 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 $ϵ$-transitions (http://planetmath.org/EpsilonTransition)? Suppose $p\stackrel{ϵ}{\to }q$ is an $ϵ$-transition, and $p\ne q$. Then ${\delta }^{\prime }(\{p\},ϵ)=\{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 $ϵ$-closure $C_{ϵ}(T)$ of $T$ as the set

$$C_{ϵ}(T):=\{t\mid t\in {\delta }^{\prime }(T,{ϵ}^k),k\ge 0\}$$(2)

For any $T\subseteq S$, ${\delta }^{\prime }(C_{ϵ}(T),a)=C_{ϵ}(T)$. If the automaton does not contain any $ϵ$-transitions, then $C_{ϵ}(T)=T$.

Now, let NDFA $A$ be an $ϵ$-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_{ϵ}(T),a)$, where ${\delta }^{\prime }$ is defined in (1) above,

• $I^{\prime \prime }=C_{ϵ}(I)$, and

• $F^{\prime \prime }=\{T\subseteq S\mid C_{ϵ}(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).