 Home Computer Science Real-Time and Distributed Real-Time Systems: Theory and Applications

# Finite State Machines: Timed and Hybrid Automata

## Finite State Machines

A finite state machine (FSM) can be used as a formal representation of an even-driven (reactive) system. An FSM has a finite set of states S = [s0,s1, ... , sN], an input alphabet I, an output alphabet O, and a state transition function d:S x I ^ S. At any time, the FSM is in exactly one state, s. Initially, the FSM is in the start state, s0. A subset of the states can be defined as accepting states. The transition function, d, determines the next state s. for a given state st e S and a given input k e I. The notation d(si,k) = s. means if the FSM is in state st and reads input k, then it will move to state s.

A state machine is deterministic, if the transition function specifies exactly one next state for every pair of current state and input. If there are pairs of current state and input for which the transition function specifies two or more next states or no next state at all, the state machine is nondeterministic.* A nondeterministic FSM can be transformed into an equivalent deterministic FSM.

Depending on the purpose of their use, different classes of FSMs are distinguished: acceptors and recognizers, and transducers.

 Related topics