\begin{definition}[Definition:Finite State Machine]
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)$.
Category:Definitions/Mathematical Logic
\end{definition}