Finite State Machines

Definitions

Finite state machine is an abstract machine that is used to mathematically model computation. It is popularly knows by its acronym: FSM. A FSM is defined by a finite set of states and rules that govern the movement between the states based on inputs, referred to as transitions. More formally,

A finite state machine is a 5-tuple (Q, Σ, δ, q₀, F) where

Q denotes the finite set of states
Σ represents the alphabet that consists of input symbols
δ: Q x Σ = Q denotes the transition function the defines the transition from q_i to q_j Q for each input symbol σ ∈ Σ where q_i, q_j ∈ Q.
q₀ denotes the start state
F denotes the set of final states

Given an input sequence, the FSM reads the string of symbols, one at a time, moves between the states as defined by the transition function δ. The string is said to be accepted by the FSM, if at the end of the processing, a final state is reached.

Finite State Machines are modeled as graphs or specified as two-dimensional tables. Graphs are intuitive to humans while tables serve for easy implementation.

In the graphical notation, the start state is represented by an incoming arrow from nowhere. The final states are denoted by a nodes with two circles.

In the tabular notation, the start state is denoted by preceding "->" while the final state is denoted by *.

Types of Finite State Machines

In the automata theory, finite state machines can be categorized as deterministic or non-deterministic.

1. Deterministic FSMs, also referred to as Deterministic Finite Automata (DFA) are machines in which transitions between the states are deterministic. i.e. from each state there exists exactly one transition for each input. δ(q_i, σ) = q_j.

The following diagrams depicts the DFA that accepts all input strings ending with "abb" modeled as graphs. The alphabet Σ is defined as a set of two symbols {a, b}.

The same DFA specified in the form of a table is given below. Both representations are equivalent.

Input	a	b
-> q₀	q₁	q₀
q₁	q₁	q₂
q₂	q₁	q₃
q₃^*	-	-

Example 1: Consider the string: abababb. Note that this ends with abb. The DFA can be used to establish this fact by running the string over the DFA. This is shown as follows.

δ(q₀, abababb) = δ(q₁, bababb)
= δ(q₂, ababb)
= δ(q₁, babb)
= δ(q₂, abb)
= δ(q₁, bb)
= δ(q₂, b)
= δ(q₃, ε)
= q₃ [ACCEPT]

Since, at the end of processing the string, the final state q₃, is reached, this string is accepted by the DFA.

Example 2: Consider the string: abababa. Note that this does not end with abb. The DFA can be used to establish this fact by running the string over the DFA. This is shown as follows.

δ(q₀, abababa) = δ(q₁, bababa)
= δ(q₂, ababa)
= δ(q₁, baba)
= δ(q₂, aba)
= δ(q₁, ba)
= δ(q₂, a)
= δ(q₁, ε)
= q₁ [REJECT]

Since, at the end of processing the string, the final state q₃, is NOT reached, this string is rejected by the DFA.

2. Non-deterministic FSMs, also referred to as Non-deterministic Finite Automata (NFA) are machines in which transtions between states are not deterministic. i.e. from each state there exists more than one transition for the same input. δ(q_i, σ) = {q_j1, ..., q_jK}.

The following diagram depicts the NFA that accepts all input strings ending with "abb". Σ = {a, b}.

The same NFA specified in the form of a table is given below. Both representations are equivalent.

Input	a	b
-> q₀	{q₀, q₁}	{q₀}
q₁	{q₁}	{q₂}
q₂	{q₁}	{q₃}
q₃^*	φ	φ

Notice that a transition in an NFA leads to a set of states instead of one state.

In practice, NFAs are easier to construct compared to DFAs due to the extra degree of freedom in defining transitions. However, this doesn't mean NFAs are any more powerful machines than DFAs. An NFA can be converted into a DFA in a mechanical fashion.