next up previous
Next: Concepts Up: No Title Previous: A Simple Example

State Machines: Definitions of Basic Concepts


If S is finite, then M is a finite state machine.

I is sometimes defined so that it can be an infinite subset of S (when of course S is infinite). A is sometimes called the alphabet of M. Elements in A are sometimes called events or operations. In other models A may be infinite. Sometimes tex2html_wrap_inline344 is defined to be a function, tex2html_wrap_inline346 , rather than a relation.

However, by our having tex2html_wrap_inline344 be a relation, we can more easily model nondeterminism. Recall that it's equivalent to view the type of tex2html_wrap_inline344 as tex2html_wrap_inline352 ; thus, given a state and an action, we can move to possibly more than one next state.

(Aside: the action component, a, of a triple, (s, a, s'), in tex2html_wrap_inline344 , is sometimes just viewed as the label for the state transition from s to s'. Thus, sometimes these kinds of state machines are called labeled state transition systems.)

Applying the above definition of a state machine, we have for the Car:

Car = (

Norman Papernick
Mon Mar 18 13:45:16 EST 1996