Definition:Finite State Machine

Definition

A finite state machine is an ordered tuple:

$F = \left({ S, A, I, \Sigma, T }\right)$

where:

$S$ is the (finite) set of states

$A \subseteq S$ is the set of accepting states

$I \in S$ is the initial state

$\Sigma$ is the alphabet of symbols that can be fed into the machine

$T : \left({ S \times \Sigma }\right) \rightarrow S$ is the transition function.

A finite state machine operates as follows:

$(1): \quad$ At the beginning, the current state $s$ of the finite state machine is $I$.

$(2): \quad$ One by one, the input (a sequence of symbols from $\Sigma$) is fed into the machine.

$(3): \quad$ After each input symbol $\sigma$, the current state $s$ is set to the result of $T\left({s, \sigma}\right)$.

If, at the end of processing an input word $w$, $s \in A$, the finite state machine is said to accept $w$, otherwise to reject it.

The set of words $w$ accepted by the machine $F$ is called the accepted language $L\left({F}\right)$.