Speak Maths · University

Regular expressions: patterns of text

A regular expression is a tiny language that describes a whole family of strings at once. Programmers use it every day; mathematicians ask which strings a pattern lets through.

Draft: written by an AI helper and not yet checked by a teacher.

The alphabet

Read each sign aloud, the way it is written under it.

$cat, c.t$ Say: c, a, t, just as written; and c, dot, t: a dot is any one characterMeans: Letters stand for themselves; a dot stands for any single character.
$a*, a+, a?$ Say: a star: a, any number of times, even none; a plus: at least once; a question mark: once or not at allMeans: Counts how often the piece before it may repeat.
$[abc], [a-z], [ˆ a]$ Say: square brackets a b c: one character from the list; a dash z: one from the range; a caret first: one character not in the listMeans: One character, taken from a chosen set.
$ˆ ab$$ Say: caret, a, b, dollar: the string starts here, says a b, and ends hereMeans: Pins the pattern to the start and to the end of the string.
$(ab|c)+$ Say: in brackets: a b, or c; all of that, one or more timesMeans: A bar chooses between pieces; brackets group pieces so that a count applies to all of them.
$a{2,4}$ Say: a, between two and four timesMeans: Says exactly how many repeats are allowed: a number, or from and to.
$\d, \w, \s$ Say: backslash d: one digit; backslash w: one letter, digit or underscore; backslash s: one spaceMeans: Short names for the commonest classes: digits, word characters, spaces.
$s \in L (r) \subseteq Σ^{*}$ Say: s is in L of r, which sits inside sigma starMeans: L of r is the set of strings that r accepts as a whole; sigma star is the set of all strings over the alphabet Σ.

The story: The gatekeeper

Subtitles:

Tap a line to see its words.

$r = ˆ [AB]\d$$ The gatekeeper’s rule r: a code is one letter, A or B, then one digit, and nothing more.
$A7 \in L (r)$ The code A7 fits the rule: it is in the language of r.
$C7 \in / L (r)$ The code C7 does not: C is not in the class.
$A77 \in / L (r)$ A77 is turned away: the end anchor insists that the code stops after one digit.
$r^{'} = ˆ [AB]\d+$$ Visitors complain, so a plus allows one or more digits. Call the new rule r′.
$A77 \in L (r^{'})$ Now A77 is let in.
$d = ˆ \d{2}:\d{2}$$ For visiting hours she checks times: two digits, a colon, two digits. Call this rule d.
$09:30 \in L (d)$ The time 09:30 passes.
$9:30 \in / L (d)$ The time 9:30 does not: it has one digit where two are required.
$L (r) \subseteq L (r^{'}) \subseteq Σ^{*}$ Whatever r lets in, r′ lets in too; and both judge only strings over the alphabet.

In words this story is 624 letters long; in symbols, 99.

Read it

What does it say?

$ˆ ab*$$

$[ˆ 0-9]$

$(ab)+$

$L (r) = Σ^{*}$

$colou?r$

${ˆ}\d{3}-\d{4}$$

$[A-Z][a-z]+$

$\w+\s\w+$

${ˆ}(0|1)*$$

$a.c$

${ˆ}[{ˆ}aeiou]+$$

${ˆ}$$

Write it

Which notation says this?

A code is a letter a, b or c followed by exactly three digits, and nothing else.

The whole string is either cat or dog.

The string s is accepted by the pattern r.

A locker code: exactly two capital letters, then exactly two digits, and nothing else.

The word colour, where the u is optional.

The whole string is the pair ab repeated one or more times.

Between two and four a’s, then a single b, and nothing else.

The pattern r accepts no string at all.

The string s is not accepted by the pattern r.

Every string that r accepts, r′ accepts too.

A word: one or more letters, digits or underscores, and nothing else.

The whole string is yes, or no, or empty.

Build it

Tap the tiles in order. One tile does not belong.

A time of day: the string starts, two digits, a colon, a minute digit from 0 to 5, any digit, the string ends.

The string s is accepted by r, and everything r accepts is a string over the alphabet.

A seat code: the string starts, one capital letter from A to Z, exactly three digits, the string ends.

The whole string is the pair ab one or more times, then an optional c.

The string s is accepted by r but not by r′: it lies in the language of r minus the language of r′.

A room label: the string starts, one or more small letters, one space, one or more digits, the string ends.

Challenges

Creative puzzles that use every sign of this chapter. Take your time; there is no clock.

1 The gatekeeper’s grid

Four rules (columns), five codes (rows). The letter s runs over the five codes and r over the four rules. Judge each sentence in this grid.

	$r_{1} = ˆ [AB]\d$$	$r_{2} = ˆ [AB]\d+$$	$r_{3} = ˆ \w\d$$	$r_{4} = ˆ \d+$$
$A7$	✓	✓	✓
$B12$		✓
$C7$			✓
$77$			✓	✓
$AB$

A tick means the code s is accepted, as a whole, by the rule r.

$\exists s : s \in L (r_{1}) \land s \in / L (r_{2})$
$\exists s : s \in L (r_{2}) \land s \in / L (r_{1})$
$\forall s : s \in L (r_{1}) \Rightarrow s \in L (r_{3})$
$\forall s : s \in L (r_{3}) \Rightarrow s \in L (r_{2})$
$\exists! s : s \in L (r_{4})$
$\forall s \exists r : s \in L (r)$

2 Look-alike patterns

Four patterns that differ by a bracket or a star. Pair each with what it accepts (whole strings, made of a and b).

Tap a line, then its meaning.

3 The wrong digit count

This pattern should accept a year of exactly four digits, a dash and a month of two digits, like 2026-10 (the whole string). One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

4 Which string gets in?

The gate has this rule: a pair ab or a single c, then at most one digit, and nothing more. Which of the three strings does it accept?

$ˆ (ab|c)\d?$$

5 How many get in?

The rule accepts only strings over the three letters a, b and c. How many strings does the language of this pattern contain?

$r = ˆ [ab]{3}$, ∣ L (r)∣ = ?$

6 The pattern that lets everyone in

What is the language of the pattern dot-star?

$L (.*) = ?$

7 Write the time-checker

A clock string looks like 09:30: hours from 00 to 23, a colon, minutes from 00 to 59. Write a pattern that accepts exactly such strings, then compare.

Your version

8 Say it as a set

Write, as a set, the language of the pattern cat|dog.

Your version

9 Five plates, four rules

Four rules for a number plate (columns) and five plates (rows). The letter s runs over the plates and p over the rules. Judge each sentence in this grid.

	$p_{1} = {ˆ}[a-z]+\d*$$	$p_{2} = {ˆ}[a-z]\d+$$	$p_{3} = {ˆ}\w+$$	$p_{4} = {ˆ}(ab\|cd)+$$
$ab$	✓		✓	✓
$ab12$	✓		✓
$a12$	✓	✓	✓
$abcd$	✓		✓	✓
$12ab$			✓

A tick means the plate s is accepted, as a whole, by the rule p.

$\forall s : s \in L (p_{2}) \Rightarrow s \in L (p_{1})$
$\exists s : s \in L (p_{4}) \land s \in / L (p_{1})$
$\exists s : s \in L (p_{3}) \land s \in / L (p_{1})$
$\exists! s : s \in L (p_{2})$
$\forall s \exists p : s \in L (p)$
$\forall s : s \in L (p_{1}) \Rightarrow s \in L (p_{4})$

10 Password rules

Four password checks (columns): at least eight characters; only word characters; contains a digit; only small letters. Five passwords (rows). Judge each sentence in this grid.

	$q_{1} = {ˆ}.{8,}$$	$q_{2} = {ˆ}\w+$$	$q_{3} = {ˆ}.\d.$$	$q_{4} = {ˆ}[a-z]*$$
$hello$		✓		✓
$hello123$	✓	✓	✓
$h3llo_w0rld$	✓	✓	✓
$12345678$	✓	✓	✓
$pass word$	✓

A tick means the password s passes the check q.

$\forall s : s \in L (q_{3}) \Rightarrow s \in L (q_{1})$
$\forall s : s \in L (q_{1}) \Rightarrow s \in L (q_{3})$
$\exists s : s \in L (q_{4}) \land s \in L (q_{3})$
$\forall s : s \in L (q_{4}) \Rightarrow s \in L (q_{2})$
$\exists! s : s \in / L (q_{2})$
$\exists s \forall q : s \in L (q)$

11 How many a’s?

Five ways to count the letter a. Pair each with what it allows (whole strings).

Tap a line, then its meaning.

12 One character, which one?

Five patterns for a character or a few. Pair each with what it accepts.

Tap a line, then its meaning.

13 A number, not nothing

This pattern should accept a whole string of one or more digits. As written it also accepts the empty string. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

14 One letter, not three

A code is one of the letters a, b or c, then exactly two digits, and nothing else. This pattern asks for all three letters in a row. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

15 Who is turned away?

The rule accepts any whole string made of a’s and b’s, even none. Which of the three strings is not accepted?

$r = {ˆ}[ab]*$, s \in / L (r) : s = ?$

16 How many two-digit strings?

The rule accepts a whole string of exactly two digits. How many strings does its language contain?

$r = {ˆ}\d{2}$, ∣ L (r)∣ = ?$

17 Write the plate rule

A plate is two capital letters, a dash, then three digits, and nothing else. Write the pattern, then compare.

Your version

18 Even in binary

A binary number is even exactly when its last digit is 0. Write a pattern that accepts exactly the binary strings of even numbers, then compare.

Your version

Tell your own

Invent a rule for a gate (a password, a plate, a door code) and write it as a pattern, then one string it lets in and one it keeps out.

Kept on this device only.

Regular expressions: patterns of text

The alphabet

The story: The gatekeeper

Read it

Write it

Build it

Challenges

1 The gatekeeper’s grid

2 Look-alike patterns

3 The wrong digit count

4 Which string gets in?

5 How many get in?

6 The pattern that lets everyone in

7 Write the time-checker

8 Say it as a set

9 Five plates, four rules

10 Password rules

11 How many a’s?

12 One character, which one?

13 A number, not nothing

14 One letter, not three

15 Who is turned away?

16 How many two-digit strings?

17 Write the plate rule

18 Even in binary

Tell your own

Download for offline use