Automata

Symptom You need to prove a language is not regular. Everyone points you at the pumping lemma, and you spend an afternoon losing to it. The statement is a nest of quantifiers: for every regular language there exists a pumping length $p$ such that for every string $w$ with $|w| \ge p$ there exists a decomposition $w = xyz$ with $|xy| \le p$ and $|y| > 0$ such that for all $i \ge 0$, $xy^i z$ is in the language. To use it you negate all of that and play a game against an adversary who picks $p$ and the decomposition while you pick $w$ and $i$. ...

Symptom Your service goes down. CPU pinned at 100% on one core, no memory growth, no error logs, requests timing out. The cause is a validation regex — something reasonable-looking like ^(a+)+$, or in real life a URL or email validator with nested quantifiers — matched against a 30-character string that happens not to match. The engine is exploring an exponential number of ways to split the input among the nested groups, and it will get there eventually, some time after the heat death of everything. ...

Symptom The most upvoted answer in Stack Overflow history is a refusal to answer. Someone asked how to match nested HTML tags with a regular expression, and the reply is a page of escalating horror about the centre not holding. It is funny, and it is also a theorem, which is not obvious from reading it. ...