Regular expressions and their limits
Regular expressions as formulas for languages, Thompson's construction that turns them into NFAs, and the pumping lemma that proves some languages are beyond any finite automaton.
About 5 hours of study
Learning objectives
- Write and test regular expressions
- Compile a regular expression into an NFA
- Prove a language is not regular with the pumping lemma
Lessons
- 1
Regular expressions Advanced
A regular expression describes a language with union, concatenation and star. Learn the three operations, how they relate to finite automata, and how to test membership with Python's re.fullmatch.
- 2
From regular expression to NFA: Thompson's construction Advanced
Parse a regular expression and build an ε-NFA for it piece by piece, then run the NFA to match strings. This is how fast regex engines work, and it proves that every regular expression describes a regular language.
- 3
Beyond regular: the pumping lemma Advanced
Some languages, such as aⁿbⁿ, need unlimited memory, so no finite automaton recognises them. The pumping lemma turns that intuition into a proof, and Python can search every split of a word to watch the argument work.
Module practice
- Theory: Does the expression describe the word?Easy
- Theory: List a regular languageMedium
- Theory: Do two expressions agree?Hard
- Theory: Make concatenation explicitEasy
- Theory: A regular expression in postfixMedium
- Theory: Your own regex engineHard
- Theory: Pump a wordEasy
- Theory: Which splits survive?Medium
- Theory: Find a word that cannot be pumpedHard