Regular Languages: Connecting FSMs and Regular Expressions

AQA 4.4.14 — Regular languages

Retrieval: the last two lessons built the exact same "at least one 1" language twice — once as an FSM, once as a regular expression — without stopping to name what that means. This lesson names it directly: regular language ↔ regular expression ↔ finite state machine are three representations of the same underlying idea, not three disconnected topics.

Key vocabulary

• Regular language — any language that can be recognised by some finite state machine (equivalently: described by some regular expression — the two definitions describe exactly the same set of languages).
• Equivalence — two different representations that accept/describe the exact same set of strings.

Understand — the same language, three ways

The language "binary strings containing at least one 1":

1. As a set (informally described): {s | s is a binary string containing at least one "1"}.
2. As a regular expression: (0|1)*1(0|1)* (Sequence 15's regex lesson).
3. As an FSM: the two-state "at least one 1" machine (this sequence's FSM-construction lesson) — q0 (start, no 1 seen), q1 (accepting, at least one 1 seen).

These are not three separate facts to memorise — they are three equivalent descriptions of the identical language. Every string either belongs to all three representations' accepted set, or none of them.

See it — verifying equivalence on a second example

The "ends in 01" FSM (this sequence's tracing lesson) has the equivalent regex (0|1)*01. Verifying on the same test strings used earlier:

| String | FSM result | Regex (0|1)*01 result | Agree? | |---|---|---|---| | "1001" | Accept (ends in q2) | Accept ("10" matched by (0|1)*, then "01") | Yes | | "1010" | Reject (ends in q1) | Reject (the string doesn't end in the literal "01") | Yes |

Two completely different-looking descriptions — a state-transition table and a compact symbolic pattern — genuinely agree on every input, because they describe the same regular language.

Evaluate — when is each representation more appropriate?

An FSM's explicit states and transitions are more naturally suited to modelling a system's behaviour over time, especially when different states correspond to different real actions or outputs (the login-lockout example). A regular expression is more compact and directly usable within real text-processing code (validating a form field, searching a log file) where the goal is a single yes/no match against a string, not modelling an ongoing process. Neither is universally "better" — as with every representation choice this course has covered, the right one depends on what the task actually needs.

Reason about the limits of regular languages

Not every language is regular. Consider matching balanced brackets of any depth — "()", "(())", "((()))", and so on. No finite state machine can recognise this language: a finite number of states cannot "count" an unbounded nesting depth (there are infinitely many possible depths, but only finitely many states to represent them in). Since a regular expression is exactly equivalent in power to an FSM, no regular expression can match this language either. This isn't a minor technical footnote — it's precisely why programming language syntax (which genuinely does need to handle arbitrarily nested brackets, parentheses and blocks) cannot be fully specified using regular expressions alone.

Common mistake

Assuming that because regular expressions are powerful and flexible, they can describe any pattern given enough cleverness. As the balanced-brackets example shows, some genuinely simple-sounding requirements are provably impossible for a regular expression or FSM to satisfy, no matter how it's constructed — the limitation is structural, not a skill issue.

Why this matters for the NEA

Regular expressions are a genuinely practical tool for validating input formats in an NEA project (a username pattern, a simple code format) — but recognising when a requirement has crossed into needing a full grammar (see the next lesson) rather than a regex is itself a useful piece of design judgement, not something to guess at.

Check your understanding

State whether the following language is regular, and justify your answer: "strings of the form aⁿbⁿ" — that is, some number of as followed by exactly the same number of bs (e.g. "ab", "aabb", "aaabbb", but not "aab" or "abb"). (3 marks)

(Not regular. Like the balanced-brackets example, this requires "counting" and comparing an unbounded number of a's against an unbounded number of b's - a finite state machine has only finitely many states and cannot remember an arbitrarily large count, so no FSM (and therefore no equivalent regular expression) can recognise this language exactly.)

Challenge

Construct both an FSM (state meanings and transition table) and an equivalent regular expression for the language "strings over {a, b} that start with a." Verify both agree by tracing/testing them against the same two strings.

Looking ahead: the next lesson introduces BNF grammar — a formalism genuinely more powerful than regular expressions, capable of describing exactly the balanced-bracket-style languages this lesson showed are out of reach.