Why There's (Likely) No Pumping Lemma for Context-Sensitive Languages

Here we give an involved proof to give strong evidence that there is no "pumping lemma for context-sensitive languages." The idea is that if there is one, then one can show that the "infinity" problem for that model is recognizable, but this is impossible for CSLs because that problem is unrecognizable (as we prove with linear bounded automata).

Timeline:
0:00 - Intro
1:20 - What does a "pumping lemma" mean?
6:45 - If the predicate exists, then Infinity Problem is recognizable
13:43 - Infinity Problem for LBAs is not recognizable

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