bisimilar automata

Let M=(SM,Σ,δM,IM,FM) and N=(SN,Σ,δN,IN,FN) be two NDFA’s (non-deterministic finite automata). Let SM×SN be a binary relationMathworldPlanetmath between the states of the automata M and N. We may extend to a binary relation between subsets of the states of the automata, as follows: for any PSM and QSN, set

C(P):={qSNpq for some pP} and C(Q):={pSMpq for some qQ}.

Then, using the same notation, define P(SM)×P(SN) by

PQ iff PC(Q) and QC(P).

Definition. We say that M is bisimilar to N if there is a binary relation SM×SN such that

  1. 1.


  2. 2.

    if pq, then δM(p,a)δN(q,a) for any aΣ,

  3. 3.

    if pq, then pFM iff qFN.

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,Σ,δ,I,F) is bisimilar to itself, for the identity relation is clearly a bisimulation. Next, if M is bisimilar to N with bisimulation , N is bisimilar to M with the converse relation -1. Finally, if M is bisimilar to N with bisimulation 1 and N is bisimilar to P with bisimulation 2, M is bisimilar to N with bisimulation 12. Therefore, bisimilarity is an equivalence relationMathworldPlanetmath 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 AB, then δ(A,x)δ(B,x) for any word over Σ. 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,Σ,δ,I,F), we get a bisimulation that is also an equivalence relation on the set of states of M. For each pS, let [p] be the equivalence classMathworldPlanetmath containing p, and for any subset AS, let [A]:={[p]pA}. Then we get an NDFA [M]:=([S],Σ,[Δ],[I],[F]), with


for any aΣ. It can be shown that [M] is minimalPlanetmathPlanetmath in the sense that [[M]] is isomorphic to [M], and that M is bisimilar to [M]. In additionPlanetmathPlanetmath, 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