Regular Expressions

A regular expression is a compact notation for describing a set of strings — a language. Rather than listing every string in the set individually, a regular expression defines a pattern, and any string that matches the pattern is a member of the described set.

Example from the AQA spec: the regular expression a(a|b)* generates the set {a, aa, ab, aaa, aab, aba, …} — every string that starts with 'a' and is followed by any sequence of a's and b's (including no further characters).

Regular expressions are used throughout computing:

• Compilers use them in lexical analysis to recognise tokens such as identifiers, keywords, and literals
• Text editors and command-line tools use them for pattern matching and search-replace operations
• Input validation (checking that a postcode or email address matches the expected format) is often implemented using regular expressions

A regular expression is a way of describing a set. Every string in that set matches the regular expression. Strings outside the set do not match.

The five metacharacters assessed by AQA are: *, +, ?, |, and ( ). Any other metacharacter used in an exam question will be defined within that question.

These five metacharacters are the building blocks of AQA regular expressions. Any character that is not a metacharacter is a literal — it matches itself exactly.

Metacharacter	Name	Meaning	Example
*	Star / Kleene star	0 or more repetitions of the preceding element	ab* matches a, ab, abb, abbb, …
+	Plus	1 or more repetitions of the preceding element	ab+ matches ab, abb, abbb, … (not a alone)
?	Question mark	0 or 1 repetitions — makes the preceding element optional	colou?r matches color or colour
|	Pipe / alternation	Either the left or the right — logical OR	cat|dog matches cat or dog
( )	Parentheses	Grouping — applies an operator to a sub-expression	(ab)* matches ε, ab, abab, ababab, …

The difference between * and +:

• a* includes the empty string (zero repetitions)
• a+ requires at least one a — the empty string does not match

How ? works:

• u? means "zero or one u" — the element is optional
• colou?r = colo(u?)r = "colo, then optionally u, then r"

Grouping with parentheses:

• Without grouping: ab* means "a, then zero or more b's" — the * applies only to b
• With grouping: (ab)* means "zero or more copies of ab" — the * applies to the whole group ab

The key skill is parsing a regular expression left to right, respecting operator precedence: *, +, ? bind tightly to the single preceding element (or group); | has lower precedence and separates alternatives.

Worked examples:

a(a|b)*

• a → a literal 'a' (required)
• (a|b) → either an 'a' or a 'b'
• (a|b)* → zero or more repetitions of (a|b)
• Full match: one 'a', followed by any sequence (including empty) of a's and b's
• Matches: a, aa, ab, aaa, aab, aba, abba, …
• Does NOT match: b, ba, empty string

(0|1)*1

• (0|1)* → any sequence of 0s and 1s (including empty)
• Followed by a literal 1
• Full match: any binary string that ends with 1
• Matches: 1, 01, 11, 001, 101, 111, …
• Does NOT match: 0, 10, 100, empty string

ab?c

• a → literal a
• b? → optional b (0 or 1 times)
• c → literal c
• Matches: ac, abc
• Does NOT match: abbc, a, bc

Building a regular expression from a description requires identifying what is fixed, what repeats, and what is optional.

Strategy:

1. Identify the required literals and their positions
2. Identify what can repeat — use * (0 or more) or + (1 or more)
3. Identify alternatives — use | with grouping ( )
4. Identify optional parts — use ?

Worked example — write a RE matching non-empty binary strings with an even number of digits:

An even-length binary string can be seen as pairs of digits: (0|1)(0|1) repeated one or more times.

RE: ((0|1)(0|1))+

• (0|1) → any single binary digit
• (0|1)(0|1) → any pair of binary digits
• ((0|1)(0|1))+ → one or more pairs

Matches: 00, 01, 10, 11, 0000, 0101, 1100, … Does not match: 0, 1, 000, 010 (odd-length strings)

Note on + vs * here: the empty string has length 0, which is technically even. Using + (one or more pairs) deliberately excludes it. If the empty string should be included, replace + with *: ((0|1)(0|1))* — this matches all binary strings with an even number of digits, including the empty string. This distinction (whether * includes the empty string and + does not) is assessed by AQA.

Worked example — write a RE matching strings over {a, b} that begin and end with 'a':

The string must start with 'a' and end with 'a'. The middle (which could be empty) can be anything over {a, b}.

RE: a(a|b)*a

This works for strings of length ≥ 2. But "a" alone (length 1) also starts and ends with 'a'. Combine:

RE: a(a|b)*a|a → or equivalently a((a|b)*a)?

The second form: 'a' followed by an optional group ((a|b)*a) — the optional part handles the middle content and the final 'a'.

A language is any set of strings over a given alphabet. A language is called regular if it can be described by a regular expression — equivalently, if a finite state machine (FSM) can be constructed that accepts exactly the strings in the language.

Regular languages have a fundamental limitation: they cannot express patterns that require counting or matching of arbitrarily nested structures. The language {$0^n{1}^n$ | $n\ge 1$} — equal numbers of 0s followed by equal numbers of 1s — is not regular. No regular expression can describe it, and no FSM can accept it.

Language	Regular?	Reason
Strings over {a, b} ending in 'ab'	Yes	RE: (a|b)*ab
Binary strings with an even number of 1s	Yes	Can be described by an FSM with 2 states
Equal numbers of a's followed by b's	No	Requires counting — no finite number of states suffices
All strings over {0,1}	Yes	RE: (0|1)*

A language is regular if and only if it can be represented by a regular expression — and regular expressions and FSMs are equivalent ways of defining regular languages.

Regular expressions and FSMs are two different notations for the same class of languages — every regular expression has a corresponding FSM that accepts exactly the same strings, and vice versa.

Converting a simple FSM to a regular expression:

FSM over {a, b} with states $q_0$ (start), $q_1$, $q_2$ (accept):

• $q_0$ on 'a' → $q_1$; $q_0$ on 'b' → $q_0$
• $q_1$ on 'a' → $q_1$; $q_1$ on 'b' → $q_2$
• $q_2$ on 'a' → $q_1$; $q_2$ on 'b' → $q_0$

This FSM accepts strings that end in 'ab'. The regular expression is: (a|b)*ab

Verify: (a|b)* matches any prefix; ab matches the final two characters. Any string ending in 'ab' is accepted. ✓

Converting a regular expression to an FSM:

RE: a*b — any number of a's followed by exactly one b.

FSM:

• $q_0$ (start): on 'a' → $q_0$ (self-loop); on 'b' → $q_1$
• $q_1$ (accept): no further transitions (or any input leads to a dead/reject state)

State transition table:

State	Input a	Input b
$q_0$ (start)	$q_0$	$q_1$
$q_1$ (accept)	reject	reject

For AQA exam questions, you may be asked to: write the RE for a given FSM, draw the FSM for a given RE, or determine whether a specific string is accepted by a given RE or FSM. All three require the same underlying understanding of what strings the expression/machine accepts.

1. Confusing * with +

a* matches the empty string; a+ does not. If the question says "one or more", use +. If zero occurrences are allowed, use *. Applying the wrong quantifier generates a different (usually larger) set than intended.

2. Forgetting that * and + apply to only the immediately preceding element

ab* means "a followed by zero or more b's" — not "zero or more copies of ab". To repeat the pair, write (ab)*. This is the most common grouping error.

3. Testing a string against a RE incorrectly

To check whether a string matches, parse the RE left to right and check whether the string can be consumed character by character following the pattern. Work through the string methodically — do not judge by inspection.

4. Writing (a|b)* when a simpler form exists

(a|b)* means "any string over {a, b}". This is often a correct component of a longer RE, but students sometimes write it when the intended language is more restricted. Read the description carefully before writing the full expression.

5. Claiming all pattern-matching is done with regular expressions

Regular expressions can only describe regular languages. Patterns with balanced brackets, matching open/close tags, or equal numbers of two symbols cannot be expressed with the five metacharacters above — they require more powerful formalisms such as context-free grammars (BNF).