Finite State Automata - 02

Question 1

What is an abstraction of an FSA? Why do abstraction?

Answer 1

An FSA A_B is an abstraction of an FSA A_A, if SIOS_B is a superset of SIOS_A. Abstracting FSA has fewer states than the original FSA and thus is much easier to analyze. Furthermore, there is lliveness (if all IOS in SIOS_B fulfill a property, all sequences in SIOS_A fulfill this property) and safety (if no IOS in SIOS_B fulfills a property, then no IOS in SIOS_A fulfills this property).

Question 2

What is a simulation of an FSA?

Answer 2

For a simulation, not only do the outputs have to be equal, but the states also have to be within a simulation relation,
which is a set of state pairs S_AB ⊂ Z_A × Z_B. If an FSA simulates another FSA, it is also an abstraction of that FSA.

Question 3

What is bisimulation?

Answer 3

One speaks of a bisimulation if an FSA A_B simulates an FSA A_A and vice-versa. Prove that a FSA does
not simulate the other by counterexample.

Question 4

Name a difference between Mealy and Moore machines.

Answer 4

Mealy output function depends on state and input, whereas Moore depends only on state. This means Moore is conceptually simpler but may require many more states than Mealy machines.