A finite state automaton recogniser
The definition of language given above is deliberately very broad, but it is really too broad to be useful. In this it is similar to notions like binary relation or binary operation discussed earlier. Practically useful examples have more structure. As in abstract algebra, there is a hierarchy of levels of structure. The main levels of this hierarchy, from most restrictive to least, are
finite
regular
deterministic context free
context free
context sensitive
recursive
recursively enumerable
general
The easiest of these to define are finite, which just means a finite set of lists of tokens, and general, which is any set of lists of tokens. The levels in between have more complicated definitions, but are more useful.
Each level in the hierarchy above includes all the levels further on in the list, so every finite language is regular, every regular language is context free, etc. The step which is most likely to cause confusion is that every context free language is context sensitive. “Context sensitive” doesn’t really mean that the language is sensitive to context, merely that it could be, while context free means that it definitely isn’t.
This sort of terminology is often used in mathematics. In the theory of linear equations we make a distinction between homogeneous equations and inhomogeneous equations. Homogeneous equations have zero constant term. Inhomogeneous equations aren’t required to have zero constant term but are certainly allowed to. This means that every homogeneous equation is inhomogeneous. That certainly sounds weird but we define things in this way because there’s simply nothing of interest to be said about equations whose constant term is non-zero which doesn’t apply equally well when the constant term is zero. Similarly, the class of languages which are context sensitive but not context free simply has no interesting properties and therefore isn’t worth naming.
There are a number of different, but equivalent, ways to describe the various levels in this hierarchy. We’ll discuss this in more detail in later chapters, but I’ll just mention here that one of these is in terms of the types of idealised machines which can recognise them. Regular languages, for example, turn out to be precisely those for which it’s possible to construct a finite state automaton recogniser. As an illustration, the figure shows a finite state automaton which recognises the language of integer multiples of 3, which I gave a grammar for earlier.
We could, of course, ask the same question for other languages, like the language of palindromes. Is it possible to construct a finite state automaton which recognises the language of palindromes? The answer turns out to be no, but how could we possibly prove this? Writing down all finite state automata and checking that none of them work is not an option, both because there are infinitely many of them and because it’s not even obvious how we would check whether a single automaton recognises the language. We’ll return to this question in a later chapter.
Other levels in the language hierarchy can also be described in terms of the types of idealised machines which can recognise them. The most important of these is the recursive enumerable languages, recognised by Turing machines. Another important class is the context free languages, recognised by pushdown automata. A pushdown automaton is essentially a finite state automaton which has a stack available for storage. A Turing machine can be thought of as a finite state automaton with a pair of stacks.
A good rule of thumb when developing a language for a specific purpose is to choose one as early as possible in the list above, and to describe it by a grammar at that level, or not much higher. One of the reasons for this is that it makes automated processing of the language much easier. Most modern programming languages are technically context sensitive, but try to segregate their context sensitive features as much as possible. The remainder is context free, with significant parts which are regular or even finite. When you think of automated processing of a programming language your first thought is likely to be of an interpreter or compiler but in fact there are many other programs which process programming languages. Most modern text editors, for example, offer syntax colouring, which means parsing the source code of program in order to colour tokens according to the terminal they belong to.