Proving that a language is not regular using pumping lemma

Question

I'm asked to like come up with a language that is not regular but im unsure how to. Could someone explain how to come up with a simple one so it would be easy to prove it later?

Answer 1

One rule of thumb is that regular languages "can't count". So languages that require that two things appear the same number of times aren't regular.

Examples of non-regular languages include $\{w : w \text{ is a palindrome}\}$ and $\{\mathtt{a}^n\mathtt{b}^n : n \geq 1\}$.

These languages are non-regular because they require the machine to remember arbitrary amounts of the string they've read before— the first half of the string, for palindromes, and the number of characters read so far, for $a^nb^n$.

To see the difference, note that the following languages are regular: $\{w : w\text{ is a palindrome}, |w| \leq 100\}$ and $\{\mathtt{a}^n\mathtt{b}^n : 1 \leq n \leq 100\}$ and $\mathtt{a}^*\mathtt{b}^*$ (which is a language where the number of $a$s and $b$s is unrelated, so the machine doesn't need to count anything.)

If a language is regular, it can be accepted by a DFA with a finite number of states. So for sufficiently large strings, its memory eventually will run out— to put it another way, the DFA must eventually re-visit one of the states it's visited before; since the only form of memory the DFA has is its current state, this amounts to forgetting everything about the string that happened between the last visit and the latest visit.

The DFA forgets a piece of long palindromes, for example, or loses count of how many $\mathtt{a}$s it's seen so far for $a^nb^n$ when $n$ is too large.