Some languages have sensible definitions in terms of machines. There is an easy and natural way of associating languages with machines. It goes like this.
For each machine we single out one state as the designated "start" state. Then we decorate some of the states of our machines with labels saying "accepting". My (highly personal and nonstandard!) notation for this is a smiley smacked on top of the circle corresponding to the state in question. The more usual notation is much less evocative: states are represented as circles, and accepting states are represented by a pair of concentric circles.
Aside on notation
Some people write pictures of machines from which arrows might be
missing, in that there could be a state s and a character c such that
there is no arrow from s labelled c. With some people this means
that you stay in s, and with some it means that you go from s to a
terminally unhappy state - which I notate with a scowlie. My policy
is to put in all arrows. This is a minority taste, but I think it makes
things clearer. It's important to remember that what this affords us
is not two examples of a different concept of machine, but different
notations.
(For some reason the expression 'final state' is sometimes used for 'accepting state'. I don't like this notation, since it suggests that once you get the machine into that state it won't go any further or has to be reset or something, and this is not true. But you will see this nomenclature in the literature.)
The use of the word "accepting" is a give-away for the use we will put this labelling to. We say that a machine accepts a string if, when the machine is powered up in the designated start state, and is fed the characters from s in order, when it has read the last character of s it is in an accepting state.
This gives us a natural way of making machines correspond to languages. When one is shown a machine ℳ one's thoughts naturally turn to the set of strings that ℳ can accept - which is of course a language. We say that this set is the language recognised by ℳ, and we write it L(ℳ).
Pin this to the wall too:
People often confuse a machine-recognising-a-language with a machine-accepting- a-string. It is sort-of OK to end up confusing 'recognise' and 'accept' once you really know what's going on: lots of people do. However if you start off confusing them you will become hopelessly lost.
Two points to notice here. It's obvious that the language recognised by a machine is uniquely determined. However, if you start from the other direction, with a language and ask what machine determines it then it's not clear that there will be a unique machine that recognises it. There may be lots or there may be none at all. The first possibility isn't one that will detain us long, but the second possibility will, for the difference between languages that have machines that accept them and languages that don't is a very important one. We even have a special word for them.
Definition:
If there is a finite state machine which recognises L then L is regular.
I'm not sure why Kleene (for it was he) chose the word 'regular' for languages recognised by finite state machines. It doesn't seem well motivated.
Next: 1.1.2 Some exercises