Pumping Lemma for Regular Languages
Ashwin Lall · Mathematical Foundations of Computer Science · 2024
Now that you have learned about proof by contradiction, you will see how to apply it to show that certain languages are not regular—no matter how hard you try, you cannot create a DFA for them. This is our first taste of what is not computable with (a specific model of) computers. It also means that there are fairly simple problems for which we cannot design a DFA and thus DFAs are not the model of computation that we want to use to represent all computers.