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

Proof.

Suppose $A=(S_1,\mathrm{\Sigma },{\delta }_1,I_1,F_1)$ be a non-deterministic 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 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\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	2013-03-22 18:03:21
Last modified on	2013-03-22 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