You are here
Homeequivalent automata
Primary tabs
equivalent automata
Two automata are said to be equivalent if they accept the same language. Explicitly, if $A_{1}=(S_{1},\Sigma_{1},\delta_{1},I_{1},F_{1})$ and $A_{2}=(S_{2},\Sigma_{2},\delta_{2},I_{2},F_{2})$ are two automata, then $A_{1}$ is equivalent to $A_{2}$ if $L(A_{1})=L(A_{2})$. We write $A_{1}\sim A_{2}$ when they are equivalent. It is clear that $\sim$ is an equivalence relation on the class of automata.
First, note that if $A_{1}\sim A_{2}$, then every symbol $\alpha\in\Sigma_{1}$ in a word $a\in L(A_{1})$ is a symbol $\alpha$ in $\Sigma_{2}$. In other words, every symbol in a word accepted by $A_{1}$ (or $A_{2}$) belongs to $\Sigma:=\Sigma_{1}\cap\Sigma_{2}$. As a result, $L(A_{1})=L(A_{2})\subseteq\Sigma^{*}$. If $B_{i}$ is an automaton obtained from $A_{i}$ by replacing the alphabet $\Sigma_{i}$ with $\Sigma$, where $i=1,2$, then $B_{i}\sim A_{i}$. This shows that we may, without loss of generality, assume outright, in the definition of equivalence of $A_{1}$ and $A_{2}$, that they have the same underlying alphabet.
The most striking aspect of equivalence of automata is the following:
Proposition 1.
Every nondeterministic automaton is equivalent to a deterministic one.
Proof.
Suppose $A=(S_{1},\Sigma,\delta_{1},I_{1},F_{1})$ be a nondeterministic automaton. We seek a deterministic automaton $B=(S_{1},\Sigma,\delta_{2},I_{2},F_{2})$ such that $A\sim B$. Recall that the difference between $A$ and $B$ lie in the transition functions: $\delta_{1}$ is a function from $S_{1}\times\Sigma$ to $P(S_{1})$, whereas $\delta_{2}$ is a function from $S_{2}\times\Sigma$ to $S_{2}$, and the fact that $I_{2}$ is required to be a singleton. The key to finding $B$ is to realize that $\delta_{1}$ can be converted into a function from $P(S_{1})\times\Sigma$ to $P(S_{1})$.
Now, define $S_{2}:=P(S_{1})$, $I_{2}:=I_{1}$. For $T\subseteq S_{1}$ and $\alpha\in\Sigma$, let
$\delta_{2}(T,\alpha):=\bigcup_{{s\in T}}\delta_{1}(s,\alpha).$ 
As usual, we extend $\delta_{2}$ so it is defined on all of $S_{2}\times\Sigma^{*}$. We want to show that
$\delta_{2}(\{s\},a)=\delta_{1}(s,a)$ 
for any $s\in S_{1}$ and any $a\in\Sigma^{*}$. This can be done by induction on the length of $a$:

if $a=\lambda$, then $\delta_{2}(\{s\},\lambda)=\{s\}=\delta_{1}(s,\lambda)$ by definition;

if $a\in\Sigma$, then $\delta_{2}(\{s\},a)=\bigcup_{{s\in\{s\}}}\delta_{1}(s,a)=\delta_{1}(s,a)$, again by definition;

if $a=b\alpha$, where $b\in\Sigma^{*}$ and $\alpha\in\Sigma$, then by the induction step, $\delta_{2}(\{s\},b)=\delta_{1}(s,b)$, so that $\delta_{2}(\{s\},a)=\delta_{2}(\{s\},b\alpha)=\delta_{2}(\delta_{2}(\{s\},b),% \alpha)=\delta_{2}(\delta_{1}(s,b),\alpha)=\bigcup_{{t\in\delta_{1}(s,b)}}% \delta_{1}(t,\alpha)=\delta_{1}(\delta_{1}(s,b),\alpha)=\delta_{1}(s,b\alpha)=% \delta_{1}(s,a)$.
Suppose $a$ is accepted by $A$, so that $\delta_{1}(s,a)\cap F_{1}\neq\varnothing$ for some $s\in I_{1}$. Then
$\delta_{2}(I_{2},a)=\bigcup_{{s\in I_{2}}}\delta_{1}(s,a)=\bigcup_{{s\in I_{1}% }}\delta_{1}(s,a),$  (1) 
which has nonempty intersection with $F_{1}$. So, we want $F_{2}$ to consists of every element of $S_{2}$ that has nonempty intersection with $F_{1}$. Formally, we define $F_{2}:=\{F\subseteq S_{1}\mid F\cap F_{1}\neq\varnothing\}$. So what we have just shown is that $L(A)\subseteq L(B)$.
On the other hand, if $a$ is accepted by $B$, then (1) above says that $\bigcup_{{s\in I_{1}}}\delta_{1}(s,a)\in F_{2}$, or $(\bigcup_{{s\in I_{1}}}\delta_{1}(s,a))\cap F_{1}\neq\varnothing$, or $\delta_{1}(s,a)\cap F_{1}\neq\varnothing$ for some $s\in I_{1}$, which means $a$ is accepted by $A$, proving the proposition. ∎
Mathematics Subject Classification
03D05 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections