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 (nondeterministic 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 nonempty 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  20130322 19:23:17 
Last modified on  20130322 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 