Overview

Throughout this module, we’ve been working within the regular languages—the class of languages generated by finite state automata and regular expressions. We’ve seen that this class is closed under union, concatenation, Kleene star, complement, and intersection, and that the subregular hierarchy provides a fine-grained classification of the subclasses where phonological patterns actually live.

But how far do the regular languages extend? Are there patterns that finite state automata simply cannot capture? The answer is yes, and in this section we’ll develop the formal tool for proving it: the pumping lemma for regular languages. We’ll then apply this tool to show that certain morphological patterns—particularly reduplication—lie outside the regular languages, motivating the move to context-free grammars in the next module.