We live in a finite world, and all our machines are finite, so regular languages are very important to us, since they are the languages that are recognised by finite state machines. It's important to be able to spot (I nearly wrote 'recognise' there!) when a language is regular and when it isn't. Here is a thought- experiment that can help.
I am in a darkened room, whose sole feature of interest (since it has neither drinks cabinet nor coffee-making facilities) is a wee hatch through which somebody every now and then throws at me a character from the alphabet Σ. My only task is to say "yes" if the string of characters that I have had thrown at me so far is a member of L and "no" if it isn't (and these answers have to be correct!)
After a while the lack of coffee and a drinks cabinet becomes a bit much for me so I request a drinks break. At this point I need an understudy, and it is going to be you. Your task is to take over where I left off: that is, to continue to answer correctly "yes" or "no" depending on whether or not the string of characters that we (first I and then you) have been monitoring all morning is a member of L.
What information do you want me to hand on to you when I go off for my drinks break? Can we devise in advance a form that I fill in and hand on to you when I go off duty? That is to say, what are the parameters whose values I need to track? How many values can each parameter take? How much space do I require in order to store those values?
Let us try some examples
Each language L generates an equivalence relation on strings, and the thought-experiment is a way of getting us to think about it. While I am running the thought experiment I retain - each time a new character comes through the hatch to give me a string s - only that information which I will need in order to answer subsequent questions about whether or not later extensions of s are members of L. For example, when L is the language that consists of strings with an even number of as and an even number of bs, I don't bother distinguishing between - for example - aabb and abab. It's true they are different strings. But as far as I am concerned they are equivalent. Indeed, it's even true that for any string w of characters that I might later receive and put on the end of aabb or abab, ababw and aabbw are equivalent - in the same way ababa and aabb are.
As you remember from Discrete Maths (and if you don't, well! - you know now!) to each equivalence relation there corresponds a set of equivalence classes. The key idea behind the thought-experiment is that the machine that you are imagining yourself to be is that machine whose states are equivalence classes of strings under this relation of equivalence-from-the-point-of-view-of-L. Do not worry if you do not see how to give a satisfactory mathematical-looking definition of this relation of equivalence-from-the-point-of-view-of-L: it's quite hard to do it properly, even though the idea should be appealing enough. The language L is regular if and only if the binary relation on strings of equivalence-from-the-point-of-view-of-L has only finitely many equivalence classes.
Equivalence-from-the-point-of-view-of-L must be a congruence relation for each of the |Σ| operations "stick w on the end" (one for each w ∊ Σ). This is all explained in the new Discrete Mathematics notes.
Next: 1.3 The Pumping Lemma