You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
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.
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) |
In a DFA, for each state and input symbol, there is exactly one transition. The machine always knows exactly which state to move to.
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.