68Q05-SubsetConstruction.tex

\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{SubsetConstruction}
\pmcreated{2013-03-22 19:02:00}
\pmmodified{2013-03-22 19:02:00}
\pmowner{CWoo}{3771}
\pmmodifier{CWoo}{3771}
\pmtitle{subset construction}
\pmrecord{7}{41906}
\pmprivacy{1}
\pmauthor{CWoo}{3771}
\pmtype{Definition}
\pmcomment{trigger rebuild}
\pmclassification{msc}{68Q05}
\pmclassification{msc}{03D10}
\pmclassification{msc}{68Q42}
\pmsynonym{powerset construction}{SubsetConstruction}
\pmrelated{DeterministicFiniteAutomaton}
\pmdefines{$\epsilon$-closure}

\endmetadata

\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%%\usepackage{xypic}
\usepackage{pst-plot}

% define commands here
\newcommand*{\abs}[1]{\left\lvert #1\right\rvert}
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}}
\begin{document}
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'$ from $P(S)\times \Sigma$ to $P(S)$ by setting 
\begin{equation}
\delta'(T,a):=\bigcup \lbrace \delta(t,a)\mid t\in T\rbrace
\end{equation}
for any subset $T$ of $S$ and $a\in \Sigma$.  Note that $\delta'(\varnothing,a)=\varnothing$.  What we have just done is turning a semiautomaton $(S,\Sigma,\delta)$ into a deterministic semiautomaton $(S',\Sigma,\delta')$, where $S'=P(S)$, the powerset of $S$.

It is easy to see, by induction on the length of $u$, that $\delta'(T,u)=\bigcup \lbrace \delta(t,u)\mid t\in T\rbrace$.

Next, given an NDFA $A=(S,\Sigma,\delta,I,F)$, we turn it into a DFA $A':=(S',\Sigma,\delta',I',F')$ as follows:
\begin{itemize}
\item $(S',\Sigma,\delta')$ is derived from $(S,\Sigma,\delta)$ by the construction above,
\item $I'=I$, and
\item $F'=\lbrace T\subseteq S\mid T\cap F\ne \varnothing\rbrace$.
\end{itemize}
Since $I'$ is an element of $S'=P(S)$, and $F'\subseteq S'$, $A'$ is a well-defined DFA.

\begin{prop} $L(A)=L(A')$. \end{prop}
\begin{proof} $u\in L(A)$ iff $\delta(q,u)\cap F\ne \varnothing$ (where $q\in I$) iff $\delta'(I,u) \in F'$ iff $u\in L(A')$.
\end{proof}

What happens if the NDFA in question contains \PMlinkname{$\epsilon$-transitions}{EpsilonTransition}?  Suppose $p\stackrel{\epsilon}{\rightarrow} q$ is an $\epsilon$-transition, and $p\ne q$.  Then $\delta'(\lbrace p \rbrace,\epsilon) = \lbrace q\rbrace \ne \lbrace p\rbrace$, which is not allowed in a DFA.

To get around this difficulty, we make a small modification on $A'$.  First, define, for any $T\subseteq S$, the \emph{$\epsilon$-closure} $C_{\epsilon}(T)$ of $T$ as the set 
\begin{equation}
C_{\epsilon}(T):=\lbrace t \mid t \in \delta'(T,\epsilon^k), k\ge 0 \rbrace
\end{equation}
For any $T\subseteq S$, $\delta'(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 \PMlinkname{$\epsilon$-automaton}{EpsilonAutomaton}, define $A'':=(S',\Sigma,\delta'',I'',F'')$ as follows:
\begin{itemize}
\item $S'=P(S)$,
\item $\delta''(T,a)= \delta'(C_{\epsilon}(T),a)$, where $\delta'$ is defined in (1) above,
\item $I''=C_{\epsilon}(I)$, and
\item $F''=\lbrace T\subseteq S\mid C_{\epsilon}(T)\cap F\ne \varnothing\rbrace$.
\end{itemize}
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 \PMlinkname{here}{EveryEpsilonAutomatonIsEquivalentToAnAutomaton}.
%%%%%
%%%%%
\end{document}