bisimilar automata

Let $M=(S_{M},\Sigma,\delta_{M},I_{M},F_{M})$ and $N=(S_{N},\Sigma,\delta_{N},I_{N},F_{N})$ be two NDFA’s (non-deterministic finite automata). Let $\approx\subseteq S_{M}\times S_{N}$ be a binary relation between the states of the automata $M$ and $N$. We may extend $\approx$ to a binary relation between subsets of the states of the automata, as follows: for any $P\subseteq S_{M}$ and $Q\subseteq S_{N}$, set

 $C(P):=\{q\in S_{N}\mid p\approx q\mbox{ for some }p\in P\}\mbox{ and }C(Q):=\{% p\in S_{M}\mid p\approx q\mbox{ for some }q\in Q\}.$

Then, using the same notation, define $\approx\subseteq P(S_{M})\times P(S_{N})$ by

 $P\approx Q\mbox{ iff }P\subseteq C(Q)\mbox{ and }Q\subseteq C(P).$

Definition. We say that $M$ is bisimilar to $N$ if there is a binary relation $\approx\subseteq S_{M}\times S_{N}$ such that

1. 1.

$I_{M}\approx I_{N}$,

2. 2.

if $p\approx q$, then $\delta_{M}(p,a)\approx\delta_{N}(q,a)$ for any $a\in\Sigma$,

3. 3.

if $p\approx q$, then $p\in F_{M}$ iff $q\in F_{N}$.

In other words, $M$ is bisimilar to $N$ as automata precisely when $M$ is bisimilar to $N$ as LTS, and satisfy conditions $1$ and $3$ above.

Any NDFA $M=(S,\Sigma,\delta,I,F)$ is bisimilar to itself, for the identity relation is clearly a bisimulation. Next, if $M$ is bisimilar to $N$ with bisimulation $\approx$, $N$ is bisimilar to $M$ with the converse relation $\approx^{-1}$. Finally, if $M$ is bisimilar to $N$ with bisimulation $\approx_{1}$ and $N$ is bisimilar to $P$ with bisimulation $\approx_{2}$, $M$ is bisimilar to $N$ with bisimulation $\approx_{1}\circ\approx_{2}$. Therefore, bisimilarity is an equivalence relation on the class of NDFA’s.

Another property of bisimulations on NDFA’s is that the they are preserved by taking unions: an arbitrary non-empty union of bisimulations is again a bisimulation. From this property, it is not hard to show that if $A\approx B$, then $\delta(A,x)\approx\delta(B,x)$ for any word over $\Sigma$. As a result, bismilar NDFA’s accept the same set of words.

By taking the union of all bisimulations on a given NDFA $M=(S,\Sigma,\delta,I,F)$, we get a bisimulation that is also an equivalence relation on the set of states of $M$. For each $p\in S$, let $[p]$ be the equivalence class containing $p$, and for any subset $A\subseteq S$, let $[A]:=\{[p]\mid p\in A\}$. Then we get an NDFA $[M]:=([S],\Sigma,[\Delta],[I],[F])$, with

 $[\Delta]([p],a):=[\delta(p,a)]$

for any $a\in\Sigma$. It can be shown that $[M]$ is minimal in the sense that $[[M]]$ is isomorphic to $[M]$, and that $M$ is bisimilar to $[M]$. In addition, if $M$ has no inaccessible states, then $M$ is bisimilar to a unique minimal automaton, in the sense that, if $N$ is any minimal automaton bisimlar to $M$, then $N$ is isomorphic to $[M]$.

Title bisimilar automata BisimilarAutomata 2013-03-22 19:23:17 2013-03-22 19:23:17 CWoo (3771) CWoo (3771) 14 CWoo (3771) Definition msc 68Q85 msc 68Q10 strongly bisimilar automata