Pumping Lemma Example: Contractible Strings (Kinda Hard...)

Here we show that the set of strings over {0, 1, 2} that are contractible is not regular. These strings are the ones that removing a maximal substring of the same character eventually results in the empty string.

#easytheory

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Social Media:

Merch:

▶SEND ME THEORY QUESTIONS◀

▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.