Regular Expressions and Finite State Machines
Regular Expressions and Finite State Machines
Regular expressions and finite state machines are two sides of the same coin — they define exactly the same class of languages (regular languages). Understanding both representations and converting between them is essential at A-Level.
Finite State Machines (FSMs)
An FSM is an abstract model of computation with a finite number of states and transitions between them, triggered by input symbols.
Components of an FSM:
- A finite set of states (including a start state and one or more accept/final states)
- An alphabet (set of input symbols)
- A transition function (rules for moving between states)
- A start state (where computation begins)
- A set of accepting states (where input is accepted)
Two types:
| Type | Abbreviation | Determinism |
|---|---|---|
| Deterministic FSM | DFA | Exactly one transition per symbol per state |
| Non-deterministic FSM | NFA | Zero, one, or multiple transitions per symbol; may have ε-transitions |
Key theorem: Every NFA can be converted to an equivalent DFA (they recognise the same languages). The DFA may have more states.
State Transition Diagrams
States are drawn as circles; the start state has an arrow pointing to it; accepting states have a double circle. Transitions are labelled arrows.
Example: Accept all binary strings ending in "01":
- States: S0 (start), S1, S2 (accept)
- S0 —0→ S1, S0 —1→ S0
- S1 —0→ S1, S1 —1→ S2
- S2 —0→ S1, S2 —1→ S0
State Transition Tables
| Current State | Input 0 | Input 1 |
|---|---|---|
| →S0 | S1 | S0 |
| S1 | S1 | *S2 |
| *S2 | S1 | S0 |
(→ = start state, * = accepting state)
Mealy and Moore Machines
These are FSMs with outputs (used for modelling circuits, protocols):
| Type | Output depends on | Output placement |
|---|---|---|
| Moore machine | Current state only | Output labelled on states |
| Mealy machine | Current state AND input | Output labelled on transitions |
They produce outputs but do not accept/reject — they are transducers, not recognisers.
Regular Expressions
A regular expression (regex) is a pattern that describes a set of strings (a regular language). It is built from:
| Symbol | Meaning | Example | ||
|---|---|---|---|---|
a | The literal character a | a matches "a" | ||
ab | Concatenation: a followed by b | ab matches "ab" | ||
| `a\ | b` | Alternation: a or b | `a\ | b` matches "a" or "b" |
a* | Kleene star: zero or more a's | a* matches "", "a", "aa", "aaa", ... | ||
a+ | One or more a's | a+ matches "a", "aa", "aaa", ... | ||
a? | Zero or one a | a? matches "" or "a" | ||
(ab) | Grouping | (ab)* matches "", "ab", "abab", ... |
Regular Expression Examples
| Pattern | Language described | |
|---|---|---|
a*b | Zero or more a's followed by exactly one b: b, ab, aab, aaab, ... | |
| `(a\ | b)*` | Any string over {a, b}: ε, a, b, aa, ab, ba, bb, aab, ... |
| `a(a\ | b)*b` | Strings starting with a and ending with b |
| `(0\ | 1)*00` | Binary strings ending in 00 |
1(01)* | 1, 101, 10101, 1010101, ... | |
[a-z]+@[a-z]+\.[a-z]+ | Simple email pattern (not a proper validator) |
Equivalence: Regex ↔ FSM
Every regular expression has an equivalent FSM, and vice versa. They define exactly the class of regular languages.
Regex → NFA: Use Thompson's construction — build small NFAs for each part and combine them.
DFA → Regex: Use state elimination — remove states one by one, labelling transitions with increasingly complex regex patterns.
Regular vs Non-Regular Languages
Regular languages can be described by a regex/FSM. They include:
- Strings matching a fixed pattern
- Languages with finite "memory" requirements
Non-regular languages cannot be described by any regex/FSM:
- a^n b^n (equal numbers of a's and b's) — needs to "count" arbitrarily
- Balanced parentheses — needs a stack
- Palindromes — needs to remember the first half
The Pumping Lemma is used to prove a language is not regular (beyond most A-Level specs but good to know conceptually).
Applications of Regular Expressions
| Application | Use |
|---|---|
| Text search | Find patterns in documents (Ctrl+F with regex) |
| Input validation | Email addresses, phone numbers, postcodes |
| Lexical analysis | Compilers use regex to tokenise source code |
| Log analysis | Extracting timestamps, error codes from server logs |
| Data cleaning | Find-and-replace patterns in datasets |
Exam Tips
- Be able to draw an FSM from a description ("accepts all strings containing 010")
- Be able to write a regex for a given language and vice versa
- Trace through an FSM with a given input string — state by state — and say whether it is accepted or rejected
- Know the difference between DFA and NFA: DFA has exactly one transition per symbol per state
- State clearly which states are accepting (double circle) — forgetting this loses marks
- When converting between regex and FSM, test your answer with specific strings (both accepted and rejected examples)
- Regular expressions cannot count unbounded quantities — if the language needs counting, it is not regular