The Pumping Game

A simple game to help you understand the pumping lemma for regular languages. (See notes at the bottom of the page.)

Here we go: The computer claims that the language $$L=\{\mathtt{a}^k\mathtt{b}^n \mid k \text{ is even or } n \text{ is odd}\}$$ over the alphabet $\Sigma=\{\mathtt{a},\mathtt{b}\}$ is regular. It also claims it can build a finite automaton accepting $L$ using $18$ states (or alternatively a regular grammar defining $L$ with $17$ nonterminal symbols).

It's your turn now. Please enter a word belonging to $L$ that's at least $18$ characters long, then press the "Continue" button.

Now use the sliders to highlight a part of the string that's at least $18$ characters long, then press the "Continue" button. (The computer will pick a substring of what you've highlighted.)

This is the computer's pick:

You can now change how often this pick appears in the string. Your job of course is to end up with a string that does not belong to the language.

Do the same language again (maybe even with the same number of states) or randomly select another language.

When you're entering your initial word, you can type something like, say, a5 as a shorthand for aaaaa. More complicated expressions like (a3b5)2 will also work as expected. Characters other than a and b (including whitespace) will simply be ignored.

Note that some of the languages presented here are regular and the computer should always win in these cases. It is part of your task to figure out which are which …

And please also note that above zero is always a natural number and all variables like $m$ or $n$ are implicitly understood to be natural numbers. Finally, $w^{\mathtt{R}}$ is the word $w$ reversed.

Copyright (c) 2014–2023, Prof. Dr. Edmund Weitz. Impressum, Datenschutzerklärung