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.

Contents

• A word on language
• Finite-state machine
  • Labeled digraph
  • Regular languages

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 by $xy$ or $x\cdot y$, 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>;

Recall that an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. Of particular importance are equivalence relations on $\Sigma^*$, specifically right-invariant ones: an equivalence relation $\equiv$ on $\Sigma^*$ is right-invariant if

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. From here on, we overload $\delta$ to mean $\delta^*$ and assume the transition function $\delta$ can take strings of arbitrary lengths as input, i.e., $\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$, denoted by $L(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);
      }
    };
  }
}

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. A very common use case for FSMs is matching and finding pattern in text. Say, we want to know if an input string is a math equation, where in our simplistic example, a math equation is a string that contains a single ”=” sign that is not at the beginning or the end of the string. Following the mechanistic interpretation above, we might solve this problem by feeding the characters of the string into an FSM, letting it run (i.e., change state), and then getting the result according to whether the last state is a final state. Then, we might design an FSM $M_E$ 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 a dangling arrow pointing to it, the final state “E” is enclosed in a double circle, and the current active state is bolded green. You can try running the FSM with your own input to see it in action.

Regular languages

A regular language is one that is accepted by some FSM. We shall denote the collection of regular languages over an alphabet $\Sigma$ by $\mcR_\Sigma$. Two trivial examples of regular languages are the empty language $\varnothing$ and the language $\Sigma$ consisting of every string.

In the example above, the set of all strings that are equations is a regular language. The set of all strings that are not equations is also a regular language. Indeed, we can construct an FSM $M_{\overline{E}}$ that accepts $\overline{E}$ from $M_E$ by changing the set of final states to its complement $\overline{F}$ (the resulting FSM has every states except “E” as a final state). This “keep everything but change one part” argument generalizes to other types of operation and can be used to show that $\mcR_\Sigma$ is closed under union, intersection, and complementation.⁴

Perhaps more interestingly, the regular languages are closed under concatenation as well. For two languages $L$ and $H$, the concatenation $LH$ is the set of all strings obtained by concatenate a string from $L$ with a string from $H$:

Proof. Let $M_L = (Q_L, \Sigma, \delta_L, q_{0L}, F_L)$ and $M_H = (Q_H, \Sigma, \delta_H, q_{0H}, F_H)$ be FSMs accepting $L$ and $H$, respectively. We construct an FSM $M_{LH}$ accepting $LH$ as follows: