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

Lessons

  1. 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. 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. 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

Module quiz

1. Which expression describes strings over {a, b} that end in b?
2. Which Python function tests whether a whole string is in a regex's language?
3. In Thompson's construction, how many new states does a star add?
4. What is the postfix form of a.b|c, with . for concatenation?
5. Which language is NOT regular?
6. In the proof that aⁿbⁿ is not regular, why does pumping down (k = 0) work for every split?

‹ NondeterminismContext-free languages ›