Finite State Machines (FSMs)

A Finite State Machine (FSM) is a mathematical model of computation that has a finite number of states. At any given time, the machine is in exactly one state. It transitions from one state to another in response to inputs, following a set of transition rules. FSMs are one of the most fundamental concepts in the theory of computation.

---

Formal Definition

An FSM is defined as a 5-tuple (Q, Σ, δ, q₀, F):

Symbol	Meaning
Q	A finite set of states
Σ (sigma)	A finite set of input symbols (the alphabet)
δ (delta)	A transition function: δ(state, input) → next state
q₀	The start state (q₀ ∈ Q)
F	A set of accepting (final) states (F ⊆ Q)

---

Types of FSM

1. Deterministic Finite Automaton (DFA)

In a DFA, for each state and input symbol, there is exactly one transition. The machine always knows exactly which state to move to.

2. Non-Deterministic Finite Automaton (NFA)

In an NFA, for a given state and input, there may be zero, one, or more possible transitions. The machine can be thought of as exploring all possible paths simultaneously.

Key theorem: Every NFA can be converted to an equivalent DFA. They recognise exactly the same set of languages (regular languages).

---

State Transition Diagrams

FSMs are commonly represented as state transition diagrams:

• States are shown as circles
• Transitions are arrows labelled with the input symbol
• The start state has an arrow pointing to it from nowhere
• Accepting states are shown as double circles

Example: Accepts strings ending in "01" over the alphabet {0, 1}

States: {S0, S1, S2}
Start: S0
Accepting: {S2}

Transitions:
  S0 --0--> S1
  S0 --1--> S0
  S1 --0--> S1
  S1 --1--> S2
  S2 --0--> S1
  S2 --1--> S0

Trace Table

Processing the input "1001":

Step	Current State	Input	Next State
1	S0	1	S0
2	S0	0	S1
3	S1	0	S1
4	S1	1	S2

Final state: S2 (accepting). The string "1001" is accepted.

Processing "1010":

Step	Current State	Input	Next State
1	S0	1	S0
2	S0	0	S1
3	S1	1	S2
4	S2	0	S1

Final state: S1 (not accepting). The string "1010" is rejected.

---

State Transition Tables

An alternative representation is a transition table:

Current State	Input 0	Input 1
→ S0	S1	S0
S1	S1	S2
*S2	S1	S0

→ indicates start state, * indicates accepting state.

---