1.1.1 A Simple Machine that can laugh
A finite state generator.
A finite state generator is a simple computing machine that outputs a sequence of symbols.
and then tries to reach a final state by making transition s from one state to another. Every time it makes such a transition it emits (or writes or generates) a symbol.
It has to keep doing this until it reaches a final state ; before that it cannot stop. All in all, finite state generators can only have a finite number of different states, that's where the name comes from. Another important property of finite state generators is that they only know the state they are currently in. That means they cannot look ahead at the states that come and also don't have any memory of the states they have been in before, or the symbols that they have emitted.
So, what does the generator in the pictures say? It laughs. It generates sequences of symbols of the form ha! or haha! or hahaha! or hahahaha! and so on. Why does it behave like that? Well, it first has to make a transition emitting h. The state that it reaches through this transition is not a final state. So, it has to keep on going emitting an a. Here, it has two possibilities: it can either follow the ! arrow, emitting ! and then stop in the final state (but remember, it can't look ahead to see that it would reach a final state with the ! transition); or it can follow the h arrow emitting an h and going back to the state where it just came from.
Finite state generators can be thought of as directed graphs. And in fact finite state generators are usually drawn as directed graphs. Here is our laughing machine as we will from now on draw finite state generators:
The nodes of the graph are the states of the generator. We have numbered them, so that it is easier to talk about them. The arcs of the graph are the transitions, and the labels of the arcs are the symbols that the machine emits. A double circle indicates that this state is a final state. An arrow pointing to a state like this:
indicates that this state is a start state.