Constructing and Testing Regular Expressions

AQA 4.4.13 — Constructing and testing regular expressions

Retrieval: the previous lesson's three operations — concatenation, union, Kleene star — are directly what regex notation encodes: writing symbols next to each other means concatenation; | means union; * means Kleene star. This lesson uses that vocabulary to construct patterns from real requirements, not merely recognise notation.

Key vocabulary (this course's regex scope)

• Literal character — a symbol matching only itself.
• | — union/alternation: matches whichever side is present.
• * — zero or more repetitions of whatever immediately precedes it.
• + — one or more repetitions of whatever immediately precedes it.
• ? — zero or one occurrence (optional) of whatever immediately precedes it.
• () — grouping, controlling exactly what an operator like *, + or | applies to.
• [ ] — a character set/class, e.g. [0-9] matches any single digit.

Understand — construct the logic first, then the syntax

Before writing any regex symbols, work out precisely, in words, what the string must start with, contain, end with, or repeat. Only then translate that description into notation — exactly the same discipline the FSM lessons used for state meanings before transitions.

See it — constructing from a specification, step by step

Specification: match exactly "cat" or "dog". Logic: two literal alternatives. Regex: cat|dog.

Specification: match "cat" or "dog", optionally followed by an "s". Logic: the same alternatives, each optionally followed by one more literal character. Regex: (cat|dog)s? — the grouping is essential here; without it, ? would apply only to the g immediately before it.

Specification: match any binary string containing at least one 1 — the exact language the "at least one 1" FSM (two lessons ago) accepts. Logic: any number of 0s-or-1s, then a 1, then any number of 0s-or-1s. Regex: (0|1)*1(0|1)*.

Trace it — why a regex accepts or rejects, precisely

For (cat|dog)s? against "dogs": the group (cat|dog) matches "dog"; the remaining "s" is matched by s? choosing its optional occurrence. Full match — accepted.

For (cat|dog)s? against "catss": the group matches "cat"; s? can match at most one s, leaving a second, unmatched "s" — the pattern does not account for the whole string. Not a full match — rejected.

Debug it — diagnose, explain, fix, test, justify (accepts an invalid case, via precedence)

A student intends "any binary string" (zero or more of either 0 or 1) and writes:

0|1*

This is intended to accept "01" and "10", but a check reveals it does not.

1. Diagnose: in 0|1*, does * apply to the whole (0|1) group, or only to the 1 immediately before it?
2. Explain: what does 0|1* actually mean, read strictly by precedence (* binds tighter than |, applying only to its immediate neighbour)?
3. Fix: add the grouping the student intended.
4. Test: confirm the fixed version accepts "01" and "10", which the original could not.
5. Justify: explain why this is a logical error, not a syntax error — 0|1* is perfectly valid regex syntax, it simply doesn't mean what the student intended.

(Without grouping, 0|1 means "(a single literal 0) OR (zero or more 1s)" - two completely different alternatives, neither of which is "any string of 0s and 1s." It cannot match "01" (not a single 0, and not zero-or-more-1s) or "10". The fix is (0|1), grouping the alternation before applying the star. This is a logical error because 0|1 is completely valid, well-formed regex - the mistake is entirely in what it means, precisely the kind of precedence pitfall that's easy to miss since the visual difference from the intended (0|1)* is tiny.)*

Common mistake

Forgetting that * and + apply only to the single symbol or group immediately to their left, not to "everything written so far." Explicit grouping with () is required whenever an operator needs to apply to more than one symbol.

Modify it

Starting from (cat|dog)s? (matches "cat", "dog", "cats", "dogs"), modify the expression so it also matches "catfish" and "dogfish", in addition to everything it already matches.

(cat|dog)(s|fish)? - the optional suffix is now itself a choice between "s" and "fish", rather than only "s".)

Check your understanding

Explain precisely why the regex a+b rejects the string "b", and explain why it accepts "aaab". (3 marks)

("b" is rejected because a+ requires AT LEAST ONE "a" (one or more, not zero or more) before the required "b" - a string with no "a" at all cannot match. "aaab" is accepted because a+ can match "aaa" (three repetitions of "a", satisfying "one or more"), immediately followed by the required literal "b", accounting for the entire string.)

Challenge

Construct a regular expression matching strings that consist of one or more digits, optionally followed by a decimal point and one or more further digits (e.g. "42" and "3.14" should both match; "." and "4." should not).

Looking ahead: the next lesson connects everything so far — showing that a regular expression, a finite state machine, and a described language are three representations of exactly the same underlying idea.