Regular Expressions

A regular expression (regex) is a concise notation for describing patterns in text. Regular expressions and finite state machines are mathematically equivalent — every regular expression can be converted to an FSM, and every FSM can be described by a regular expression. Together, they define the class of regular languages.

---

Why Regular Expressions Matter

Regular expressions are used extensively in:

• Compilers — lexical analysis (tokenising source code)
• Text editors and IDEs — find-and-replace with patterns
• Data validation — checking email addresses, phone numbers, postcodes
• Web scraping and log analysis — extracting structured data from text
• Command-line tools — grep, sed, awk

---

Regex Syntax

The A-Level specification requires you to understand the following operators:

Operator	Name	Meaning	Example	Matches
(none)	Concatenation	One pattern followed by another	ab	"ab"
|	Alternation (OR)	One pattern or another	a|b	"a" or "b"
*	Kleene star	Zero or more repetitions	a*	"", "a", "aa", "aaa", ...
+	Kleene plus	One or more repetitions	a+	"a", "aa", "aaa", ...
?	Optional	Zero or one occurrence	a?	"" or "a"
()	Grouping	Group sub-expressions	(ab)*	"", "ab", "abab", ...

Operator Precedence (highest to lowest)

1. Kleene star / plus / optional (*, +, ?)
2. Concatenation
3. Alternation (|)

So ab*|c means a(b*) | c — "a followed by zero or more b's" OR "c".

---

Examples

Regex	Language described
a	{"a"}
ab	{"ab"}
a|b	{"a", "b"}
a*	{"", "a", "aa", "aaa", ...}
(a|b)*	All strings over {a, b}, including the empty string
a+b	{"ab", "aab", "aaab", ...}
(ab)+	{"ab", "abab", "ababab", ...}
a(b|c)d	{"abd", "acd"}
(0|1)*01	All binary strings ending in "01"
1(0|1)*1	All binary strings starting and ending with 1 (length ≥ 2)

---

Formal Connection to FSMs

Kleene's Theorem states that the following are equivalent:

1. A language is regular (can be recognised by a DFA).
2. A language can be described by a regular expression.
3. A language can be recognised by an NFA.

This means:

• For any regular expression, we can construct an FSM that accepts exactly the strings matching the regex.
• For any FSM, we can write a regular expression that describes the language it accepts.

Converting Regex to NFA (Thompson's Construction)