Consider, first, the spelling checker. It consists of a large dictionary of words in a particular language, and it is useful for compensating for the deficiencies of a progressive education, since if you have written a page of text the chances of a spelling error are quite high, and we all wish to conceal our intellectual inadequacies. It also has use when trying to do OCR, since if we are uncertain as to whether a given character is an `s' or a `5', we can look at the surrounding letters and use the fact, for example, that `Profes5or' is not a word but `Professor' is. When we do this we are using syntactic information to resolve an uncertainty. We are smoothing the word, filtering the string of characters, somewhat as we might use a moving average filter to use the neighbouring values in a time series to modify a particularly egregious value. It is plain to everyone who has tried to decipher bad handwriting that such methods are applied a good deal in human information processing.
We shall be concerned in this chapter with long strings of symbols, short strings of symbols, and what are known as formal languages, which is to say sets of strings of symbols. We do not insist that the language arise from people speaking or writing, although these do give particular cases, but we examine the subject in vastly more generality. We shall also be concerned with stochastic languages, briefly mentioned in the last chapter, where there is, for each string in the language, some number saying how often it comes up.
The reflective reader will, of course, be wondering why we devote a whole chapter to such matters.
Having focussed to a large extent of the recognition
of characters in discussing applications, the
reader might think that this is the important
connection with Pattern Recognition, since
strings of characters form words, strings of words
form sentences and sentences are (or aren't)
grammatical. Anyway, there is presumably
some connection between formal language and
natural
language, and characters come into natural language.
Thus the reader seeking for connections
between things, that is to say the reader who
is thinking about what he reads, might hazard
a guess
that we are going to be concerned with using a
spelling checker to improve the chances of a
correct
reading of some characters. He might also guess
that there is a connection with Speech Recognition,
since our first move there, when discussing the
standard approach, was to reduce the continuous
trajectories in 
to trajectories in a discrete
space, that is to say, symbol strings. So
maybe we are going to enlarge our perspectives
on Speech Recognition on the side.
It is true that one aim of this chapter is to show how to extract information about which strings of symbols occur and which don't in a page of text so as to improve recognition of characters, but this is the tip of a rather humongous iceberg. The problem in the case of strings of symbols is fairly easy to understand, but the ideas go across to cases which are on the face of things very different. For example, I shall explain in the next chapter how to clean up an image by using knowledge drawn from other images. This is a clever trick when human beings do it, and is known to psychologists as Transfer of Learning, and making a program do it is even cleverer. It is essentially a rather considerable generalisation of using a dictionary to resolve uncertainty or correct a preliminary decision at a lower level, as in `Profes5or'. The generalisation is so extreme as to require a good deal of preliminary technicality however, and this is one purpose of the present chapter.
We observe that our low level objects, characters in the above example, are combined together to form higher level objects, words in the example. You would not be the first person to notice that it doesn't stop there; words are aggregated into phrases, phrases into sentences, sentences into paragraphs, and so on. There are hierarchies out there. The idea of a `high level object' is rather an interesting idea to try to make precise. Cast your mind back to when you learnt to drive a car. As a rank tiro, you may have had to think quite hard when the instructor gave the order `turn left'. It requires slowing down, i.e. taking your right foot up a bit, signalling left, looking in the mirror to ensure that the driver of the car behind knows you are slowing, disengaging the gears by depressing the clutch (push your left foot down), and moving the gear lever from where it is to somewhere else (where, for God's sake?). In addition you have to keep an eye open to ensure that the turn is not prohibited by some road signs and that you won't run over any little old ladies. Oh, and you'd better remember to turn the steering wheel as well. Seen from this point of view, turning left is a pretty complicated business. Actually, the muscle contractions required to depress the clutch and reduce the pressure on the accelerator are also pretty complicated and you took years to learn to do them; most of the time between birth and three years of age in fact. And now you plan a drive of a hundred miles without, I hope, a trace of panic. It is clear that there is a chunking of low level actions consisting of muscle fibres firing, into larger things like lifting a foot, chunking of actions like lifting feet, pushing legs, turning the wheel and so on into `turning left', and a further chunking of turns and stops and starts in order to get you from A to B. Although why anybody should want to get to B is far from clear to anybody who, like myself, has never visited A.
Now the intuitive notion of chunking low level things into higher level things, and so on, and the corresponding decomposition of some things into sub-things occurs all over the place. If you are obliged to write a computer program for example, then you are asked to write a string of symbols which defines a map. The program will have some input, possibly several different sorts, and some output. You therefore are faced with the problem of constructing this map using the more primitive maps given in the language such as `+', `*', `&', `if' and so on. You also have standard ways to glue these primitive maps together. It is good programming practice to write your program as a set of procedures, and a procedure is a sub-map. A well written program is likely to have elements of a hierarchical structure to it, in other words it is a chunk of chunks of... of the given primitives. This is more obvious in the so called applicative or functional languages (the French word for map is application), but it holds in all of them. So again, chunking occurs, and the rather woolly idea of `high level' objects and lower level objects makes sense. And as observed, chunking occurs in natural language. In the case of a printed book, we may consider at the lowest level the pixels of ink on paper, then the edges which are defined by the pixels, then the strokes made up of edges, then the characters built up from strokes, then the words built up from characters, the phrases built up from words, the sentences from phrases, the paragraphs from sentences, the chapters from paragraphs, and finally the book from chapters. And you could, in good conscience, insert some intermediate levels if you wished.
The intuitive notions are quite compelling and
are even well known to psychologists, but the
Mathematician is impelled to ask how to define
the terms properly. Talking about things with
no
very clear meaning does very well in the Soggy
Sciences, but it doesn't cut the mustard in real
science or in engineering, and I have no wish
to be mistaken for a psychologist as the term
is
currently widely understood, anymore than anyone
in a Chemistry department might wish to be taken
for an alchemist. Nevertheless, it has to be admitted
that what we are studying was identified by
psychologists first as an important aspect of
cognitive processing in human beings. Our job
will be to
make the ideas precise. This will involve us in
defining syntactic structures of a continuous
sort,
and it would be a good idea to get the standard
ideas clarified in our minds first.
The really interesting parts of this chapter therefore
will be the sections that have to do with being
able to define clearly what is meant by a chunk,
for these have extensive applications to all
sorts of pattern recognition. If you want to describe
the shape of a set of points in it
may be convenient to find a description of parts
of the set and the relationship between the parts,
and here it pays to know what you mean by the
terms.
It is important to clarify ideas about structured objects with substructures, and the case of a sequential or temporal relation between the substructures is the easiest to deal with, so it makes sense to tackle this case first. This chapter is therefore a bridge between classical pattern recognition and the modern syntactic approach.
In the hope, then, that your interest has been aroused enough to carry you through the forest of definitions which are coming up, we proceed to investigate formal languages and streams of symbols.