Finite State Automaton

A Finite State Automaton (also called Finite State Machine, FSA) is a theoretical model of computation which is characterised by some finite number of states, which the automaton can switch between (transition to) with some given conditions.

The keyword automaton (self-running) means once the transitions are defined, the FSA can run without any extra intervention.

A finite state automata is a model of computation which has the specifications:

• All inputs are in the form of formula, which are sequences of symbols belonging to an alphabet.
  • The FSA process the string symbol-by-symbol.
• The output is a yes/no question, represented as a single bit, $0/1$
• It can only solve decision computational problems.
• It cannot allocate new memory. Later, this property is given a mathematical definition, known as the memorylessness lemma.

A finite automaton, can be either deterministic or non-deterministic.

Deterministic §

See Deterministic Finite Automaton

Non-Deterministic §

See Non-Deterministic Finite Automaton

Definitions §

#todo generalise for all state-based automata

Acceptance §

FSA Acceptance (String) ^definition-accept-string

A string is sequence of symbols from the alphabet $\Sigma$. It can be ‘fed into’ a FSA, which changes states based on the characters it encounters.

A string, $w$ is accepted by the FSA $M$ iff the associated computation path resulting from feeding $w$ to $M$ ends in an accept state $\in F$, i.e. $M$ eventually reaches an accept state when given $w$ We say $M$ recognises $w$.

FSA Recognition (Language) ^definition-accept-language

Let $L$ be a language (i.e. a set of strings/formulae). Then, let $M$ be a FSA. We say that $M$ accepts or recognises $L$ iff:

$$\text{M accepts w}⟺w\in L$$

That is, $M$ accepts every word, $w$, in $L$ and rejects every word not in $L$. Often notated as:

$$L(M)=L$$

(where $L(x)$ is the language recognised by FSA $x$)

Equivalence §

FSA Equivalence ^definition-equivalence

Let $M,N$ be two finite state automata (FSA). Then:

$$M\sim N⟺L(M)=L(N)$$

That is, $M$ and $N$ are equivalent if they both accept the same language. In other words, their set of accepted strings are the same.

Two different DFAs, $M$ and $N$ can be checked for equivalence by minimalising them and checking if they are equal. That is:

$$M\sim N⟺M_{min}=N_{min}$$

State Transition Table/Matrix §

A state transition table is a table used to represent the state transition function, $\delta$. The first column represents the current state ($q_{prev}$), and the remaining columns represent the character that could be encountered. Thus, an entry on row $i$ and column $j$ is given by $\delta (i,j)$.

A state transition table will then have $|Q|$ rows, i.e. rows equal to the number of states, and $|\Sigma |$ columns, i.e. columns equal to the number of symbols.

Current State	Flip	Null
$\top$	$\perp$	$\top$
$\perp$	$\top$	$\perp$
The above state transition table represents a machine that can flip a truth value, or leave it unchanged:

• The set of states are $Q=\{\top ,\perp \}$
• The input alphabet are $\Sigma =\{\text{flip},\text{ null}\}$
• The initial state and accepting states are irrelevant.
• The state transition function is defined as:

$\delta :\{(\top ,\text{flip})\mapsto \perp ,(\top ,\text{null})\mapsto \top ,(\perp ,\text{flip})\mapsto \top ,(\perp ,\text{null})\mapsto \perp \}$

State Diagram §

A state diagram weighted, directed graph where:

• Each node represents a state
• Each directed edge represents a transition between two states
• The ‘weight’ represents the symbol required to make the transition

In most cases, the state diagram is a multigraph

For example, the flip/null machine previously mentioned has the state diagram:

%%🖋 Edit in Excalidraw, and the dark exported image%%

The accept and initial states are usually notated as:

%%🖋 Edit in Excalidraw, and the dark exported image%%

Computation Path §

A computation path is a walk (in the graph theory sense) of the state diagram, that is, it involves a sequence of nodes (where nodes can be repeated).

For example, a computation path for the flip/null machine is $\perp \to \perp \to \top$, which would arise from doing the operations (in order): $\text{null, null, flip}$.

%%🖋 Edit in Excalidraw, and the dark exported image%%

Single-State FSA §

A FSA with only one state is known as the single-state FSA. Either this state can be an accept state, in which case the FSA accepts anything, or it is a non-accept state, in which case the FSA accepts nothing.

%%🖋 Edit in Excalidraw, and the dark exported image%%

Limitations §

See Non-Regular Languages for a set of strings that cannot properly be recognised by a FSA.

Applications §

• Knuth-Morris-Pratt Algorithm

Examples §

Example: Tally Counter

A tally counter is a simple device used for counting.

• It has two operations, increment and reset
• Usually 2-digit (0 to 99) or 3-digit (0 to 999), but we will considered the 1-digit case.

It can be represented as a DFA:

• Each number is represented as a state: $Q=\{0,1,\dots ,9\}$
• Each operation is a symbol in the alphabet: $\Sigma =\{\text{increment},\text{reset}\}$
• The initial state is $0$
• Accepting states aren’t relevant here, we could have all states being accepting, $F=Q$

The state transition table is as follows:

Current State	Increment	Reset
0	1	0
1	2	0
2	3	0
3	4	0
4	5	0
5	6	0
6	7	0
7	8	0
8	9	0
9	0	0

The state diagram is given by: %%🖋 Edit in Excalidraw, and the dark exported image%%

Example: Printer Manager

Suppose some software is required to run a printer management system, which is capable of taking in print requests by two users: User A & User B. It should be able to queue these requests, then print them accordingly. A (rough) state diagram for such a system would be given by:
%%🖋 Edit in Excalidraw, and the dark exported image%% Constraints:

• Every $P_i$ succeeds $R_i$, i.e. a print by a user is done only after the request has been queued by that user
• Every $R_i$ is eventually followed by a $P_i$: Every request is eventually printed