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 finite1 set of characters. A string over the alphabet Σ\Sigma is a tuple x=(a1,a2,,ak)x=(a_1,a_2,\ldots,a_k) in Σk\Sigma^k in which we write simply as x=a1a2akx=a_1a_2\cdots a_k. A string xx in Σk\Sigma^k has length kk, denoted x=k|x|=k. The set of all strings of all lengths over the alphabet Σ\Sigma is the Kleene closure of Σ\Sigma and denoted Σ\Sigma^*; symbolically,

Σ=k=0Σk.\Sigma^* = \bigcup_{k = 0}^\infty \Sigma^k.

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

Given strings x=a1a2akx=a_1a_2\cdots a_k and y=b1b2bly=b_1b_2\cdots b_l over Σ\Sigma, the concatenation of xx and yy, denoted by xyxy or xyx\cdot y, is the string produced by appending yy to xx:

xy=xy=a1a2akb1b2bl.xy = x\cdot y = a_1a_2\cdots a_kb_1b_2\cdots b_l.

Note that εx=xε=x\varepsilon x = x\varepsilon = x for any string xx.

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

xyx\equiv y implies xzyzxz\equiv yz for all zΣz\in\Sigma^*.

Finite-state machine

A finite-state machine (FSM)2 MM is specified through five elements, as follows:

M=(Q,Σ,δ,q0,F)M = (Q, \Sigma, \delta, q_0, F)


Mechanistically, an FSM MM 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 MM 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Σx\in\Sigma^* and aΣa\in\Sigma, we define

δ(q,xa)=δ(δ(q,x),a).\delta^*(q, xa) = \delta(\delta(q, x), a).

The function δ\delta^* can receive as input any (nonempty) string over Σ\Sigma. We also let δ(q,ε)=q\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., δ ⁣:Q×ΣQ\delta\colon Q\times\Sigma^*\to Q.

The FSM MM is said to accept a string xx if δ(q0,x)F\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 MM accepts is the language accepted or recognized by MM, denoted by L(M)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 MM as a labeled directed graph: the vertices are the states and the edges are the state transitions. For a starting state qQq\in Q and each letter σΣ\sigma\in\Sigma, there is an edge labeled σ\sigma going from qq to δ(q,σ)\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 MEM_E as follows:3

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 RΣ\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 MEM_{\overline{E}} that accepts E\overline{E} from MEM_E by changing the set of final states to its complement F\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 RΣ\mcR_\Sigma is closed under union, intersection, and complementation.4

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

LH={xy ⁣:xL,yH}.LH = \{xy\colon x\in L, y\in H\}.

Proof. Let ML=(QL,Σ,δL,q0L,FL)M_L = (Q_L, \Sigma, \delta_L, q_{0L}, F_L) and MH=(QH,Σ,δH,q0H,FH)M_H = (Q_H, \Sigma, \delta_H, q_{0H}, F_H) be FSMs accepting LL and HH, respectively. We construct an FSM MLHM_{LH} accepting LHLH as follows:


  1. Technically, a language can be defined on an arbitrary alphabet, but for most practical purposes, finite alphabet works without problems.

  2. There are many names, such as finite automaton, for the concept with various meanings. Here, “finite-state machine” follows exactly the given definition.

  3. For a more interactive and feature-rich visualization, see this wonderful FSM Simulator by Ivan Zuzak.

  4. That makes the set of regular languages an algebra of sets!