Finite state machine

A finite state machine is a way of defining a language (see Strings and languages). We give a string to the machine, which examines the string one character by one, and at the end decides whether the string is the language or not.

A non-deterministic finite state machine (also called 'finite automaton') is a five-tuple $(\Sigma,Q,\Delta,q_0,F)$ where

$\Sigma$ is a finite alphabet
$Q$ is a finite set of states
$\Delta \subseteq Q \times \Sigma \times Q$ is a transition relation
$q_0 \in Q$ is the initial state of the automaton
$F \subseteq Q$ is the set of final states

We graphically represent finite state machines using a graph.

the nodes of the graph are the states $Q$ , represented using circles
the graph has an edge from $q_1 \in Q$ to $q_2 \in Q$ labelled by $a \in \Sigma$ if and only $(q_1,a,q_2) \in \Delta$
we draw a double circle around each state $q$ if and only if $q \in F$
we put a symbol $>$ in front of the initial state $q_0$

Example finite state machine:

$\begin{eqnarray*} \Sigma &=& \{b,a,r\} \\ Q &=& \{q_0,q_1,q_2,q_3\} \\ \Delta &=& \{(q_0,a,q_3), (q_0,b,q_1), (q_1,a,q_2), (q_2,r,q_0)\} \\ F &=& \{q_3\} \end{eqnarray*}$

We formalize the operation of a finite state machine as follows.

If $n \geq 0$ and $a_1,\ldots,a_n \in \Sigma$ , an execution of a finite state machine $A = (\Sigma,Q,\Delta,q_0,F)$ on $a_1,\ldots,a_n$ is a sequence

$\begin{equation*} q_1, a_1, q_2, a_2, q_3,\ \ldots,\ a_n, q_{n+1} \end{equation*}$

where $q_1,\ldots,q_n \in Q$ , such that $(q_i,a_i,q_{i+1}) \in \Delta$ for all $1 \leq i \leq n$ .

If $S \subseteq Q$ , we define $\Delta_{run}(S,a_1\ldots a_n)$ as the set of all states in which the automaton could be while processing the word $a_1 \ldots a_n$ . Formally, we define $\Delta_{run}(S,a_1 \ldots a_n)$ as the set of all states $q_{n+1}$ such that there exists an execution with given $a_1,\ldots,a_n$ , with $q_1 \in S$ , and witn some $q_2,\ldots,q_n \in Q$ .

An accepting execution is an execution where $q_1 = q_0$ and $q_{n+1} \in F$ . We say that $A$ accepts the string $a_1\ldots a_n$ iff there exists an accepting execution of $A$ on $a_1,\ldots,a_n$ . We define the language of the automaton, denoted $L(A)$ , as the set of all strings that $A$ accepts.

We then have

$\begin{equation*} L(A) = \{ s \mid \Delta_{run}(\{q_0\},s) \cap F \neq \emptyset \} \end{equation*}$

Example: the example automaton above accepts the language $L = \{a, bara, barbara, barbarbara, \ldots \}$ , which we can denote by $\{ (bar)^n a \mid n \geq 0 \}$ .

What is the automaton accepting strings of the form $p\ barbara\ q$ where $p,q$ are arbitrary strings?

A state machine is called deterministic iff for every pair $(q_1,a) \in Q \times \Sigma$ there exists exactly one $q_2 \in Q$ such that $(q_1,a,q_2) \in \Delta$ .

References