Interactive Notes on FiniteState Machine
· 4 min read
As I am selfstudying 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^{1} 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 frequentlyseen 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>;
Finitestate machine
A finitestate machine (FSM)^{2} $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:^{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 an arrow pointing to it, and the final state “E” is enclosed in a double circle.
Footnotes

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

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

For a more interactive visualization, see FSM Simulator by Ivan Zuzak. ↩