proving non-regularity

Showing a language IS regular is easy in spirit — exhibit one finite automaton or regular expression for it. Showing a language is NOT regular is harder, because you cannot try infinitely many automata and watch them all fail. Instead you argue from a property that EVERY regular language must have, and demonstrate your language lacks it. The intuition is always the same: regular languages can only remember finitely much, so any language that needs to COUNT or MATCH without bound cannot be regular.

There are three standard weapons, all of which exploit finite memory. The pumping lemma argues that a long string must contain a pumpable loop and then shows your language breaks under pumping. A closure argument combines your language with known-regular pieces (via intersection, homomorphism, reversal) to manufacture a contradiction with a known non-regular language. The Myhill-Nerode theorem exhibits infinitely many strings that are pairwise distinguishable — pairwise needing to be remembered separately — which no finite-state machine can do. Myhill-Nerode is the most complete tool: it succeeds exactly when a language is non-regular, while the pumping lemma can occasionally fail to detect non-regularity.

The classic non-regular menagerie all share the 'unbounded memory' flavor: a^n b^n (must match the count of a's to b's), ww (must remember the whole first half to compare to the second), palindromes (must remember the string to check it reads the same backwards), a^{n^2} (must track a perfect square), and balanced parentheses. Each fails because no fixed-size memory suffices to enforce the constraint for arbitrarily large inputs.