AQA 7517 · Paper 1 · 4.4.1b

Regular
Languages

Regular expressions · Kleene star · FSM equivalence · Section 4.4

WHAT YOU'LL LEARN

Regular expressions · Kleene star · Union · Concatenation · FSM equivalence

AQA SPEC LINK

4.4.1 — Regular languages and regular expressions

Regular Languages

What is a Regular Language?

A regular language is a set of strings that can be recognised by a Finite State Machine. Every regular language can be described by a regular expression.

Regular languages sit at the bottom of the Chomsky hierarchy (Type 3)

All strings in a regular language share a describable pattern

Key equivalence: FSM = Regular Expression = Regular Language

Regular Expressions

Regular Expression Operations

CONCATENATION — placing side by side

ab matches exactly the string "ab"

UNION (alternation) — pipe symbol |

a|b matches "a" OR "b" — either one

KLEENE STAR — zero or more repetitions

a* matches "", "a", "aa", "aaa", … (any number of a's including none)

Plus & Optional

Additional Regex Operators

KLEENE PLUS — one or more

a+ = aa* — one or more a's ("a","aa","aaa"…) but NOT empty string

OPTIONAL — zero or one

a? matches "" or "a" exactly

GROUPING — parentheses

(ab)* matches "", "ab", "abab", "ababab"…

Examples

Regular Expression Examples

Strings of 0s and 1s ending in 0: (0|1)*0

Binary strings with even number of 1s: (0*10*1)*0*

Lowercase letters followed by digits: [a-z]+[0-9]*

Email-like pattern (simplified): [a-z]+@[a-z]+\.[a-z]+

FSM Equivalence

Regular Expressions ↔ FSMs

Every regular expression describes a language that can be recognised by an FSM, and vice versa. The two notations are equivalent in power.

Given a regex, you can build an FSM that accepts exactly those strings

Given an FSM, you can write a regex for the language it accepts

Example: a*b ↔ FSM: start state loops on 'a', transitions to accepting on 'b'

Chomsky Hierarchy

Language Classes

TYPE 3 — REGULAR (FSMs)

Simplest class. Recognised by FSMs. Example: strings ending in 'ab'

TYPE 2 — CONTEXT-FREE (push-down automata)

Example: {aⁿbⁿ | n≥0} — requires counting

TYPE 0 — RECURSIVELY ENUMERABLE (Turing machines)

Most powerful. Everything computable.

Applications

Real-World Uses of Regular Expressions

Validation — checking email, phone number, postcode formats

Lexical analysis — compilers use regex/FSMs to recognise tokens (keywords, identifiers)

Search & replace — grep, sed, text editors use regex for pattern matching

Network security — firewalls use regex for packet content inspection

AQA Exam Style

Practice Question

AQA 7517 — Paper 1 Style

(a) Write a regular expression that describes all binary strings (over {0,1}) that start with '1'. [2]
(b) Write a regular expression for strings over {a, b} that contain at least two consecutive b's. [2]
(c) State the relationship between regular expressions and finite state machines. [1]

[5 marks]

2 marks

(a) 1(0|1)* — starts with 1, then any combination of 0s and 1s (including empty)

2 marks

(b) (a|b)*bb(a|b)* — any strings, then 'bb', then any strings

1 mark

(c) Every regular expression describes a language that can be recognised by an FSM, and vice versa — they are equivalent

Summary

Key Points to Remember

Regular language — can be described by a regex and recognised by an FSM

* Kleene star = 0 or more; + = 1 or more; ? = 0 or 1

| = union (OR); concatenation = side-by-side; () = grouping

Type 3 in Chomsky hierarchy — weakest/simplest class of formal languages

Used in: compilers (lexical analysis), validation, search tools

🎉 Lesson complete — move to the quiz!