bisimilar automata

Let $M=(S_M,\mathrm{\Sigma },{\delta }_M,I_M,F_M)$ and $N=(S_N,\mathrm{\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\text{ for some }p\in P\}\text{ and }C(Q):=\{p\in S_M\mid p\approx q\text{ for some }q\in Q\}.$$

Then, using the same notation, define $\approx \subseteq P(S_M)\times P(S_N)$ by

$$P\approx Q\text{ iff }P\subseteq C(Q)\text{ 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. $I_M\approx I_N$,

2. if $p\approx q$, then ${\delta }_M(p,a)\approx {\delta }_N(q,a)$ for any $a\in \mathrm{\Sigma }$,

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,\mathrm{\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 $\mathrm{\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,\mathrm{\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],\mathrm{\Sigma },[\mathrm{\Delta }],[I],[F])$, with

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

for any $a\in \mathrm{\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
Canonical name	BisimilarAutomata
Date of creation	2013-03-22 19:23:17
Last modified on	2013-03-22 19:23:17
Owner	CWoo (3771)
Last modified by	CWoo (3771)
Numerical id	14
Author	CWoo (3771)
Entry type	Definition
Classification	msc 68Q85
Classification	msc 68Q10
Synonym	strongly bisimilar automata