Let and be two NDFA’s (non-deterministic finite automata). Let be a binary relation between the states of the automata and . We may extend to a binary relation between subsets of the states of the automata, as follows: for any and , set
Then, using the same notation, define by
if , then for any ,
if , then iff .
In other words, is bisimilar to as automata precisely when is bisimilar to as LTS, and satisfy conditions and above.
Any NDFA is bisimilar to itself, for the identity relation is clearly a bisimulation. Next, if is bisimilar to with bisimulation , is bisimilar to with the converse relation . Finally, if is bisimilar to with bisimulation and is bisimilar to with bisimulation , is bisimilar to with bisimulation . 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 , then 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 , we get a bisimulation that is also an equivalence relation on the set of states of . For each , let be the equivalence class containing , and for any subset , let . Then we get an NDFA , with
for any . It can be shown that is minimal in the sense that is isomorphic to , and that is bisimilar to . In addition, if has no inaccessible states, then is bisimilar to a unique minimal automaton, in the sense that, if is any minimal automaton bisimlar to , then is isomorphic to .
|Date of creation||2013-03-22 19:23:17|
|Last modified on||2013-03-22 19:23:17|
|Last modified by||CWoo (3771)|
|Synonym||strongly bisimilar automata|