LARA

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