Introduction
Drawing a DFA for every pattern would be slow. A regular expression (regex) is a compact formula for a language: (a|b)*abb means "any string of a's and b's that ends in abb". Programmers meet regular expressions in search tools, editors and input validation, but in the theory of computation they have a precise meaning and an exact power: they describe exactly the languages that finite automata recognise.
How it works
Regular expressions are built from small pieces:
- a symbol such as
adescribes the language {a}; - ε describes {ε}, and ∅ describes the empty language.
Three operations combine expressions R and S:
- Union
R|S: strings described by R or by S. - Concatenation
RS: a string of R followed by a string of S. - Star
R*: zero or more strings of R joined together, so it always includes ε.
Star binds tightest, then concatenation, then union, so ab*|c means (a(b*))|c. Brackets change the grouping: (ab)* repeats the pair.
Some languages and their expressions over {a, b}:
- every string:
(a|b)* - strings that end in abb:
(a|b)*abb - some a's, then some b's:
a*b* - strings of even length:
((a|b)(a|b))*
Kleene's theorem says that a language is described by a regular expression exactly when some finite automaton recognises it. One direction is a construction you will build in the next lesson: every regex becomes an NFA. The other direction turns a DFA back into an expression by removing states one at a time. That is why both are called regular languages.
In Python, the re module understands this notation. The theory's "the expression describes the string" means the whole string matches, which is re.fullmatch. re.search finds a match anywhere inside, which answers a different question:
import re
print(bool(re.fullmatch("a(b|c)*", "abcb")))
print(bool(re.fullmatch("a(b|c)*", "bab")))
print(bool(re.search("a(b|c)*", "bab")))Syntax
import re
re.fullmatch("(a|b)*abb", word) # is word in the language? (a match object or None)
"R|S" "RS" "R*" "(R)" # union, concatenation, star, grouping
"R+" == "RR*", "R?" == "(R|)" # common shorthands
Example
import re
from itertools import product
def words_up_to(n, sigma="ab"):
for length in range(n + 1):
for letters in product(sigma, repeat=length):
yield "".join(letters)
for pattern in ["(ab)*", "(a|b)*abb", "a*b*"]:
members = [w or "ε" for w in words_up_to(4) if re.fullmatch(pattern, w)]
print(f"{pattern:10} {len(members):2} words: {members}")Line by line
words_up_to(4)lists every string over {a, b} of length 0 to 4, shortest first.- For each pattern,
re.fullmatchkeeps the strings the whole expression describes; ε is printed as the symbol ε. (ab)*keeps only ε, ab and abab: repeated pairs.(a|b)*abbkeeps abb, aabb and babb: anything followed by abb.a*b*keeps 15 of the 31 strings: every string in which no b is followed by an a.
Expected result
(ab)* 3 words: ['ε', 'ab', 'abab']
(a|b)*abb 3 words: ['abb', 'aabb', 'babb']
a*b* 15 words: ['ε', 'a', 'b', 'aa', 'ab', 'bb', 'aaa', 'aab', 'abb', 'bbb', 'aaaa', 'aaab', 'aabb', 'abbb', 'bbbb']
In the real world
Lexers describe tokens with regular expressions: an identifier is [A-Za-z_][A-Za-z0-9_]*. Input validation, log analysis, search-and-replace in editors, and tools such as grep and sed are all built on them. Knowing their theoretical limit matters too: a regex cannot check balanced brackets, which is why HTML and programming languages need real parsers.
Common mistakes
- Using
re.searchorre.matchto test membership: onlyre.fullmatchchecks the whole string. - Misreading precedence:
ab*repeats only b; write(ab)*to repeat the pair. - Forgetting that star includes ε:
(ab)*matches the empty string. - Expecting a regex to count, as in "as many a's as b's": no regular expression can do that.
Best practices
- Test an expression on short strings, including ε, before trusting it.
- Use brackets generously, so that the grouping is obvious.
- Keep the theoretical operations in mind when reading library features: back-references, for example, go beyond regular languages.
Summary
A regular expression builds a language from symbols with union, concatenation and star. Star binds tightest, then concatenation, then union. In Python, re.fullmatch tests membership. By Kleene's theorem, regular expressions describe exactly the languages that DFAs and NFAs recognise.
Quick check
Key takeaways
- Three operations (|, concatenation, *) are enough to describe every regular language.
- In theory a regex must match the whole string, which is re.fullmatch in Python.
- Regular expressions, NFAs and DFAs are three views of the same class of languages.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.