JavaFSM

by Karola Krönert and Ulrich Dallmann

ENGLISH translation by Holger Rehmeier
IPCT, PUCRS, BRASIL  (more tools)

What is a FSM?

A FSM (FiniteStateMachine) is a formal model, with which many problems of the computer science can be described. In this program, finite state machines are used for the modelling of control mechanisms.

That machine describes a system, that exists of a final number of internal configurations - so called states. The state of the system includes the information, that has emerged from the previous inputs and those, that required, in order to decide the reaction of the system on the still following inputs [HU93]. One of these conditions is defined as start-state. The system can now change the state under certain conditions. The states are graphically displayed as circles and transitions as arrows, signed with the transition-conditions (see illustration).

Formally, a machine (A) exists of a finite quantity of conditions (Q), an input-alphabet (I), a transition-function (d), a start-state (q0) and a quantity of final-states (F).

With the modelling of networks, the quantity of the finalstates is cancaled, as it is not about accepting words but about the calculation of output-values and transition-conditions. The input-alphabet is (0,1)n, as n is the number of the inputs.
 

Example:

 Q={Zustand 1, Zustand 2, Zustand 3} 

q0=Zustand 1

I=(0,1) (values for a) 

d(q,z)->(q ')

for example: d(Zustand 1, !a)->(Zustand 2)

In principle, there are determining and non-determining machines. The transitions are always defined unequivocally with determining machines, while there can be several possible transitions with non-determining machines, of which the machine must guess "the right one". For the design of  networks, only determining machines are used, thats why they form the basic this program.

In JavaFSM there is not, as in the formal model, only one single transition-function declared. Instead, for every transition one  transition-condition is defined.  Because it is a determining machine, exactly one of the transitions is activated in each case.

In chip design, final state machines are used for the design of clocked control mechanisms, because they simplify the transposition of many electronic functions, especially sequence-controls. In order to avoid designing with unwieldy and error-susceptible logic-tables, new hardware-description-languages often offer a direct syntax for final state machines.


JavaFSMTECHUlrich DallmannKarola Krönert