Interactive Notes on Finite-State Machine

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);
      }
    }
  }
}