equivalent automata
Two automata are said to be equivalent^{} if they accept the same language^{}. Explicitly, if ${A}_{1}=({S}_{1},{\mathrm{\Sigma}}_{1},{\delta}_{1},{I}_{1},{F}_{1})$ and ${A}_{2}=({S}_{2},{\mathrm{\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 {\mathrm{\Sigma}}_{1}$ in a word $a\in L({A}_{1})$ is a symbol $\alpha $ in ${\mathrm{\Sigma}}_{2}$. In other words, every symbol in a word accepted by ${A}_{1}$ (or ${A}_{2}$) belongs to $\mathrm{\Sigma}:={\mathrm{\Sigma}}_{1}\cap {\mathrm{\Sigma}}_{2}$. As a result, $L({A}_{1})=L({A}_{2})\subseteq {\mathrm{\Sigma}}^{*}$. If ${B}_{i}$ is an automaton obtained from ${A}_{i}$ by replacing the alphabet ${\mathrm{\Sigma}}_{i}$ with $\mathrm{\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},\mathrm{\Sigma},{\delta}_{1},{I}_{1},{F}_{1})$ be a nondeterministic automaton. We seek a deterministic automaton $B=({S}_{1},\mathrm{\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 \mathrm{\Sigma}$ to $P({S}_{1})$, whereas ${\delta}_{2}$ is a function from ${S}_{2}\times \mathrm{\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 \mathrm{\Sigma}$ to $P({S}_{1})$.
Now, define ${S}_{2}:=P({S}_{1})$, ${I}_{2}:={I}_{1}$. For $T\subseteq {S}_{1}$ and $\alpha \in \mathrm{\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 {\mathrm{\Sigma}}^{*}$. We want to show that
$${\delta}_{2}(\{s\},a)={\delta}_{1}(s,a)$$ 
for any $s\in {S}_{1}$ and any $a\in {\mathrm{\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 \mathrm{\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 {\mathrm{\Sigma}}^{*}$ and $\alpha \in \mathrm{\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}\ne \mathrm{\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}\ne \mathrm{\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}\ne \mathrm{\varnothing}$, or ${\delta}_{1}(s,a)\cap {F}_{1}\ne \mathrm{\varnothing}$ for some $s\in {I}_{1}$, which means $a$ is accepted by $A$, proving the proposition^{}. ∎
Title  equivalent automata 

Canonical name  EquivalentAutomata 
Date of creation  20130322 18:03:21 
Last modified on  20130322 18:03:21 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  6 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03D05 
Classification  msc 68Q45 