Discrete Mathematics

-------------------------------------------------------------·AUTOMATA

281

9.3

FINITE

AUTOMATA

AND

REGULAR SETS

9.3.1

States

and

Transitions

Intuitively, a state

of

a system is an instantaneous description

of

that system, a snapshot

of

reality frozen in

time. A state gives all relevant information necessary to determine how the system can evolve from that point

on. Transitions are changes

of

state; they can happen spontaneously

or

in response to external inputs.

We assume that state transitions are instantaneous. This is a mathematical abstraction. In reality, tran-

sitions usually take time. Clock cycles in digital computers enforce this ...