What is a finite state machine?
A finite state machine (FSM), also called a finite automaton, is a simple model of a computer with no memory except the state it is in. It has:
- a finite set of states (circles)
- an input alphabet Σ: the symbols it can read, e.g. {coin, push} or {0, 1}
- one start state (an arrow from nowhere)
- a transition function δ: for each state and symbol, the next state
- for an acceptor, a set of accepting (final) states (double circles)
The machine reads the input string one symbol at a time from left to right. After the last symbol, if it is in an accepting state, the string is accepted; otherwise it is rejected. An FSM like this has no output except yes/no.
If every state has exactly one arrow for every symbol, it is a deterministic FSM (DFA). If a state may have several arrows for the same symbol (or none), it is non-deterministic (NFA). Every NFA can be turned into an equivalent DFA.
State transition diagrams and tables
The same machine can be drawn as a diagram or written as a table.
| Current state | Input | Next state |
|---|---|---|
| LOCKED | coin | UNLOCKED |
| LOCKED | push | LOCKED |
| UNLOCKED | coin | UNLOCKED |
| UNLOCKED | push | LOCKED |
Example acceptor: states S0 (start, accepting) and S1. Input alphabet {0, 1}. Reading 1 swaps the state; reading 0 keeps it. This machine accepts exactly the binary strings with an even number of 1s: 1001 → S0 (accept), 111 → S1 (reject).
FSMs with output: Mealy machines
A Mealy machine gives an output on every transition. Each arrow is labelled input / output. It has no accepting states; its job is to translate input to output.
Example: the turnstile could output "open" or "beep": LOCKED —coin/open→ UNLOCKED, LOCKED —push/beep→ LOCKED. Another classic: a machine that outputs 1 whenever the input bit differs from the previous one (an edge detector). Mealy machines are used in traffic-light controllers, vending machines and simple ciphers.
(In a Moore machine the output depends only on the state, not on the transition.)
Sets, alphabets and words
An alphabet Σ is a finite set of symbols, e.g. Σ = {a, b}. A word (string) is a finite sequence of symbols; the empty word is ε. A language is a set of words, e.g. L = {ab, aab, aaab, …}.
Set notation: A = {1, 2, 3}; set-builder {x | x ∈ ℕ ∧ x < 4}; ∅ is the empty set. Operations: union A ∪ B, intersection A ∩ B, difference A \ B, Cartesian product A × B (all ordered pairs). Sets can be finite, countably infinite (like ℕ), or uncountable (like ℝ).
Syntax is the form of a word (is it built by the rules?); semantics is its meaning.
Regular expressions and regular languages
A regular expression is a short pattern that describes a set of strings:
ab: a then ba|b: a or ba*: zero or more aa+: one or more aa?: zero or one a- brackets group:
(ab)*= ε, ab, abab, …
A language is regular if it can be described by a regular expression, and exactly then it can be accepted by an FSM. Example: (0|1)*1 = binary strings ending in 1; 1*01* = strings with exactly one 0.
Everyday use: a simple pattern for an Indian vehicle plate like KA05MN1234 is [A-Z]{2}[0-9]{2}[A-Z]{1,2}[0-9]{4}. A postcode, phone number or date can be checked the same way.
Limit: an FSM cannot count without bound. The language {aⁿbⁿ} (same number of a then b) is not regular, so no FSM accepts it.
Context-free languages: BNF and syntax diagrams
Nested structures, like matching brackets or expressions inside expressions, need a grammar. A grammar has terminals (actual symbols), non-terminals (names in angle brackets) and production rules. Written in Backus–Naur form (BNF):
<digit> ::= 0|1|2|3|4|5|6|7|8|9 <integer> ::= <digit> | <digit><integer>
The second rule is recursive, so it can make integers of any length. Recursion is what makes BNF more powerful than regular expressions: e.g. <S> ::= ab | a<S>b produces {aⁿbⁿ}.
EBNF adds shortcuts: {x} for repetition, [x] for optional. A syntax diagram shows the same rules as railway tracks: follow any path from left to right; ovals are terminals, rectangles are non-terminals.
A derivation (parse) tree shows how a word is built from the start symbol: e.g. 42 → <integer> → <digit><integer> → 4 <digit> → 4 2. Compilers use such trees to check programs.
Try it: predict, then check
In the 3D free play, try to find a short input that ends in LOCKED even though it contains two coins. (Hint: what does the last symbol have to be?)
On paper: draw an FSM with alphabet {0, 1} that accepts strings ending in 1. You need only two states. Test it on 1011 (accept) and 110 (reject).
Key formulas and definitions
- FSM = (states Q, alphabet Σ, transition δ: Q × Σ → Q, start q₀, accepting F)
- Accepted ⇔ the state after the last symbol is in F
- Mealy arrow label: input / output
- Regex: | (or), * (0 or more), + (1 or more), ? (0 or 1), () group
- BNF: <non-terminal> ::= alternative | alternative
Worked examples
1. Trace the turnstile on "coin, coin, push, coin". Which state does it end in?
LOCKED → coin → UNLOCKED → coin → UNLOCKED → push → LOCKED → coin → UNLOCKED. It ends UNLOCKED (accepted).
2. Using the even-1s machine (S0 accepting, 1 swaps state), is 10110 accepted?
It has three 1s. S0 →1→ S1 →0→ S1 →1→ S0 →1→ S1 →0→ S1. Ends in S1: rejected.
3. Write a regular expression for binary strings that start with 1 and end with 0.
1(0|1)*0. The middle part can be anything.
4. Which of these match a(b|c)*d: ad, abcd, abd, acbx?
ad (zero repeats), abcd and abd match. acbx does not end in d.
5. Using <integer> ::= <digit> | <digit><integer>, show that 305 is valid.
<integer> → <digit><integer> → 3<integer> → 3<digit><integer> → 30<integer> → 30<digit> → 305. Valid.
6. Design a Mealy machine that outputs 1 when the current bit differs from the previous bit (start: assume previous = 0).
States P0 (last bit 0, start) and P1 (last bit 1). P0 —0/0→ P0, P0 —1/1→ P1, P1 —1/0→ P1, P1 —0/1→ P0. Input 0110 gives output 0101.
Common mistakes
- Forgetting the start arrow or the double circle for accepting states; the machine is then not fully defined.
- Leaving out a transition in a DFA. Every state needs exactly one arrow for every input symbol (use a "dead" state if needed).
- Thinking a* means "at least one a". * allows zero; + needs at least one.
- Thinking an FSM can check balanced brackets of any depth. That needs a context-free grammar (BNF), not a regular expression.