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 non-deterministic automaton is equivalent to a deterministic one.

Proof.

Suppose $A=(S_{1},\Sigma,\delta_{1},I_{1},F_{1})$ be a non-deterministic 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 non-empty intersection with $F_{1}$. So, we want $F_{2}$ to consists of every element of $S_{2}$ that has non-empty 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. ∎

Title equivalent automata EquivalentAutomata 2013-03-22 18:03:21 2013-03-22 18:03:21 CWoo (3771) CWoo (3771) 6 CWoo (3771) Definition msc 03D05 msc 68Q45