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,\Sigma,\delta)$. The transition function $\delta$ is a function from $S\times\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\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\Sigma$. Note that $\delta^{\prime}(\varnothing,a)=\varnothing$. What we have just done is turning a semiautomaton $(S,\Sigma,\delta)$ into a deterministic semiautomaton $(S^{\prime},\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,\Sigma,\delta,I,F)$, we turn it into a DFA $A^{\prime}:=(S^{\prime},\Sigma,\delta^{\prime},I^{\prime},F^{\prime})$ as follows:

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

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

• $F^{\prime}=\{T\subseteq S\mid T\cap F\neq\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\neq\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 $\epsilon$-transitions (http://planetmath.org/EpsilonTransition)? Suppose $p\lx@stackrel{{\scriptstyle\epsilon}}{{\rightarrow}}q$ is an $\epsilon$-transition, and $p\neq q$. Then $\delta^{\prime}(\{p\},\epsilon)=\{q\}\neq\{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 $\epsilon$-closure $C_{\epsilon}(T)$ of $T$ as the set

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

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

Now, let NDFA $A$ be an $\epsilon$-automaton (http://planetmath.org/EpsilonAutomaton), define $A^{\prime\prime}:=(S^{\prime},\Sigma,\delta^{\prime\prime},I^{\prime\prime},F^% {\prime\prime})$ as follows:

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

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

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

• $F^{\prime\prime}=\{T\subseteq S\mid C_{\epsilon}(T)\cap F\neq\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 SubsetConstruction 2013-03-22 19:02:00 2013-03-22 19:02:00 CWoo (3771) CWoo (3771) 7 CWoo (3771) Definition msc 68Q05 msc 03D10 msc 68Q42 powerset construction DeterministicFiniteAutomaton $\epsilon$-closure