Interactive Notes on Finite-State Machine

As I am self-studying theory of computation, specifically the theory of finite automata right now, I am making some notes on the topic to better reinforce what I have learnt, with interactive demonstrations of the automata.

A word on language

Mirroring the daily meaning of the word, in formal language theory, an alphabet $\Sigma$ is a finite¹ set of characters. A string over the alphabet $\Sigma$ is a tuple $x=(a_1,a_2,\ldots,a_k)$ in $\Sigma^k$ in which we write simply as $x=a_1a_2\cdots a_k$. A string $x$ in $\Sigma^k$ has length $k$, denoted $|x|=k$. The set of all strings of all lengths over the alphabet $\Sigma$ is the Kleene closure of $\Sigma$ and denoted $\Sigma^*$; symbolically,

We define $\Sigma^0=\{\varepsilon\}$, where $\varepsilon$ is the empty string, the only string having zero length. A language over $\Sigma$ is a subset $L$ of $\Sigma^*$. As an example of a frequently-seen language, the set of all binary strings is $\{0,1\}^* = \{\varepsilon, 0, 1, 00, 01, \ldots\}$.

Given strings $x=a_1a_2\cdots a_k$ and $y=b_1b_2\cdots b_l$ over $\Sigma$, the concatenation of $x$ and $y$, denoted $x\cdot y$ or just $xy$, is the string produced by appending $y$ to $x$:

Note that $\varepsilon x = x\varepsilon = x$ for any string $x$.

type Letter = string | symbol;
type Str<L extends Letter> = Iterable<L>;

Finite-state machine

A finite-state machine (FSM)² $M$ is specified through five elements, as follows:

where

• $Q$ is the set of $M$’s states,
• $\Sigma$ is $M$’s input alphabet,
• $\delta\colon Q\times \Sigma\to Q$ is $M$’s transition function,
• $q_0\in Q$ is $M$’s initial state,
• $F\subset Q$ is the set of $M$’s final states.

Mechanistically, an FSM $M$ can be thought of as a machine that repeatedly receives a character from an alphabet $\Sigma$ and changes its internal status accordingly. Though the above specification does not mention output, we can regard $M$ as being able to output YES or NO, depending on whether its state is one of the final states.

Naturally, we can extend the transition function to accept an arbitrary string over $\Sigma$ in an inductive manner: for $x\in\Sigma^*$ and $a\in\Sigma$, we define

The function $\delta^*$ can receive as input any (nonempty) string over $\Sigma$. We also let $\delta^*(q, \varepsilon) = q$—by reading no input, the machine does not change its state. We overload $\delta$ to mean $\delta^*$ and assume the transition function $\delta$ can take arbitrary strings as input. Note that $\delta\colon Q\times\Sigma^*\to Q$.

The FSM $M$ is said to accept a string $x$ if $\delta(q_0, x) \in F$. In other words, the machine “output” YES when it accepts the input string and NO otherwise. The set of strings that $M$ accepts is the language accepted or recognized by $M$.

type State = string | symbol;
class FSM<S extends State, L extends Letter> {
  state: S;
  initialState: S;
  transition: (input: Str<L>) => void;
  finalStates: Set<S>;

  constructor(
    initialState: S,
    finalStates: Set<S>,
    t: (s: S, l: L) => S
  ) {
    this.state = initialState;
    this.initialState = initialState;
    this.finalStates = finalStates;
    this.transition = (input: Str<L>) => {
      for (const l of input) {
        this.state = t(this.state, l);
      }
    }
  }
}

FSM as labeled digraph

It is natural to visualize an FSM $M$ as a labeled directed graph: the vertices are the states and the edges are the state transitions. For a starting state $q\in Q$ and each letter $\sigma\in\Sigma$, there is an edge labeled $\sigma$ going from $q$ to $\delta(q, \sigma)$.

Let us represent a simple FSM this way. The canonical example of FSM with practical use is regular expression, which are used as pattern to match or find in a string. Say, we want to know if an input string is a math equation. Assuming the string is alphanumeric and a math equation here simply contains a single ”=” sign that is not at the beginning or the end of the string. Then, we might design an FSM as follows:³

Here, the label “not =” corresponds to any character that is not the equal sign, and the label “all” matches every character. The intial state “A” has an arrow pointing to it, and the final state “E” is enclosed in a double circle.