## You are here

Homebisimilar automata

## Primary tabs

# 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. $I_{M}\approx I_{N}$,

2. if $p\approx q$, then $\delta_{M}(p,a)\approx\delta_{N}(q,a)$ for any $a\in\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,\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]$.

## Mathematics Subject Classification

68Q85*no label found*68Q10

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections