Using the Contrapositive: The Regular Pumping Theorem

$\newcommand{\N}{\mathbb N} \newcommand{\Z}{\mathbb Z} \newcommand{\Q}{\mathbb Q} \newcommand{\R}{\mathbb R} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} $

Subsection 8.3.8 Using the Contrapositive: The Regular Pumping Theorem

In this video, we’ll see an example of this approach.

The Pumping Theorem for regular languages is an important theorem in formal language theory. You can ignore its details. It is an interesting example of a significant and nontrivial contrapositive proof. Note that it requires that we negate an expression with four nested quantifiers.