< previous page page_50 next page >
Page 50
The two different ways of counting using automata, described in Section 2.3, were highlighted on page
5 of [88]. In Chapter 11, we classify those languages in which counting, in the sense of modulo
n
counting, need not be used in recognising them. The languages of Section 2.4 turn out to be particular
instances of such languages, and they are discussed further in the notes at the end of Chapter 11.
The automata of Section 2.4 are also simple cases of pattern-matching algorithms. Propositions 2.4.3
and 2.4.5, which are just variants of the same idea, are automata-theoretic manifestations of the Knuth-
Morris-Pratt algorithm. This is proved on page 875 of the voluminous [36]. This algorithm is also
discussed in [2]. Further examples of pattern-matching algorithms and their applications can be found in
[126]. Automata-theoretic algorithms for locating substrings of a string together with applications are
discussed in [8].
The Pumping Lemma was first proved in [9].
I would like to place automata in a slightly wider context so that we can better appreciate why they
should be interesting. To do this, I will introduce a more concrete model of an automaton. We regard an
automaton A as a black box equipped with a read-head and two lights: one labelled ‘accept’ and one
labelled ‘reject.’ There is also a reset-button, which re-initialises the automaton. The input to the
automaton is written on a paper tape that is right infinite: it has a beginning but no end. This tape is
divided into squares. The symbols of the input are written into the successive squares on the tape
starting from the leftmost square. So if our input string is abab, then the tape will look like this:
To process the input string, the read-head of A is placed over the leftmost square and the reset button
of A is pushed. From now on A runs completely automatically: it reads the contents of the current
square, changes its internal state as a result and moves one square to the right. When A reads a blank
square, then it knows that it has read a complete input string; if it is in a terminal state, then the
‘accept’ light is activated, whereas if it is in a non-terminal state, the ‘reject’ light is activated, after
which A goes into a rest state and does nothing until the reset button is pushed. It is clear, I think, that
it would not be too difficult to build such a machine from any finite automaton and, conversely, any
such machine could be modelled by a finite automaton.
My reason for describing finite automata in such concrete terms is that two limitations in their design
are now obvious: the read-head is restricted to move always one square to the right, in addition it is
unable to overwrite the contents of a square. Automata in which the tape-head can move left as well as
right are called two-way automata. Despite appearances, they are in fact no more powerful than
ordinary automata. Proofs of this result can be found in [109] and [120]. However, if we allow the two-
way automata also to overprint the contents of a square, then the situation changes radically. Such
automata are called
Turing machines
after Alan Turing who first studied them
< previous page page_50 next page >