4.4.2.3–4.4.2.4 - Regular expressions and regular languages (Python)
Describe sets of strings using regular expressions and connect them with finite-state machines. Construct simple patterns, check whole strings and apply the same ideas to Python matching and replacement.
Languages and patterns
A language is a set of strings, and a regular expression describes which strings belong to that set.
An alphabet is the set of permitted symbols. Over alphabet , strings include a, ab and bba, as well as the empty string . A regular expression is a convenient shorthand for a particular set, not a single example string. Spaces used to make an expression readable are not input symbols unless explicitly stated.
Regular language
A language is regular if a regular expression can represent it; equivalently, it is a language accepted by a finite-state machine.
The expression a(a|b)* describes a first a followed by zero or more symbols, each chosen from a or b. Its language includes a, aa, ab, aaa, aab and aba. It excludes the empty string because the first a is required, and excludes ba because it begins with b. It also excludes ac because c is outside the alternatives. A pattern describes the complete allowed form; a finite list of a few accepted examples does not define the whole language.
In theoretical questions, “recognise the language” means accept exactly its strings. When using a software matching library, distinguish recognising an entire string from finding a matching substring. Finding a inside ba would not make ba a member of the language a(a|b)*.
Repetition, choice and grouping
Metacharacters combine literal symbols into patterns with precise boundaries and repetition rules.
| Notation | Meaning | Example |
|---|---|---|
* | Zero or more repetitions of the preceding item | a* includes the empty string, a and aa |
+ | One or more repetitions | a+ includes a and aa, but not the empty string |
? | Zero or one occurrence | ab? includes a and ab only |
| | Alternation, meaning a choice | a|b accepts a or b |
( ) | Group an expression as one item | (ab)+ accepts ab, abab, ababab, … |
Concatenation places items in order. ab* means a followed by any number of b symbols; (ab)* repeats the whole pair and can be empty. Grouping also fixes the intended scope of alternation: a(b|c) accepts ab or ac, while (ab)|(ac) describes the same set. If an exam uses a metacharacter beyond these five, its meaning will be supplied; do not assume a library's entire feature set is compulsory notation.
Build an expression from requirements. “One or more ab pairs followed by an optional c” becomes (ab)+c?. It accepts ab, abc and ababc; it rejects c because an ab pair is required, and rejects abcc because at most one final c is allowed.
Python's re.fullmatch(pattern, text) returns a match object only if the complete text matches; otherwise it returns None. Comparing with is not None produces a Boolean. Python's re.sub(pattern, replacement, text) replaces matching substrings: it deliberately does not require the whole text to match. For example, re.sub('(ab)+', 'X', 'ab cabab ba') gives X cX ba, replacing each maximal run of ab pairs.
Check a pattern boundary
{"code":"import re\n\npattern = 'a(b|c)*'\nfor text in ['', 'a', 'ab', 'acbc', 'ba', 'ad']:\n print(repr(text), re.fullmatch(pattern, text) is not None)\nprint(re.sub('(ab)+', 'X', 'ab cabab ba'))\n","instructions":"Predict which complete strings match and the replacement output, then run. Change * to + in pattern, run again and explain precisely which membership decision changes. Leave the replacement statement unchanged.","files":[],"original_filename":"main.py","runtime_profile":"python-console-v1","file_mode":"fresh"}
The original accepts a, ab and acbc; the changed expression rejects a because at least one following b or c is now required. The other decisions and replacement output stay the same. Test a shortest permitted string, an empty string and a string with an invalid symbol to expose different pattern errors.
Equivalence with finite-state machines
A regular expression and an FSM can describe the same language while presenting its structure in different ways.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account