INTRODUCTION

All the sciences share a tool which allows them to pursue their research and present their results with precision, to frame their theories, and to communicate with researchers in related disciplines: mathematics. Between the 1930s and the the mid-1950s a mathematical theory of language was developed, and this has since then evolved along three main lines:

1. Generative grammar, whose aim is the statement of explanatory theories of natural language. Chomsky's Transformational Grammar was an early attempt at this; more recent examples are Generalised Phrase Structure Grammar, Lexical-Functional Grammar, Government & Binding, and Minimalism.

2. Theory of computation, whose aim is to state a theory of computation in terms of language processing devices. This line of development is the scientific and engineering basis of all current computer technology.

3. Natural language processing, whose aim is to develop computer-based systems for applications involving speech and text forms of natural language. These applications range from word processing through statistical text analysis to artificial intelligence systems that interact with humans using spoken or written language.

Theoretical linguistics is concerned with (1), and computational linguistics with (2) and (3). We shall consequently be looking at (2) and (3). The structure of the discussion is as follows:

1. Mathematical characterization of language

2. The nature of computation

3. Formal language and automata theory

• Phrase structure grammars

• Automata

• Finite state automata for formal language definition

• Limitations of finite state automata

• Pushdown automata

• Parsing

• Natural language parsing with pushdown automata

1. Sets

A set is any collection of objects --of trains, teeth, policemen, numbers. Indeed, so general is the concept that the members of the set do not even have to have any obvious connection with one another: ships and snails and sealing wax, cabbages and kings. Intuitively, the notion of a set is simple and straightforward; it is also the foundation on which mathematics in general, and the theory of formal languages and automata in particular, are built. A well developed set theory exists. For present purposes, however, only the following observations need to be made:

a) Sets are given labels for ease of reference in discussion. By convention, these labels are uppercase letters: A, B, C...

b) There are two ways to define a set, that is, to specify which objects are included in a set:

i. The objects belonging to a set may be listed. To make it clear that such a list is meant to constitute a set, it is enclosed in curly brackets. For example, the days of the week may be specified as:

{Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday}

ii. Some criterion or criteria may be specified which can be used to determine which objects belong to set. This is the only practical course when the number of objects in a set is very large. It would be effectively impossible to list all the green objects in the world, for example, but one could easily state a rule for set membership: that any green object belongs to the set. Then, for any object, it would be possible to decide whether or not it belonged to the set. The usual way of writing such rules in mathematics is on the following pattern:

G = {x | x is green}

Note that this set is given an uppercase letter label, and that the definition is enclosed in curly brackets as before. The bar | is new: it is read as 'such that', and the above definition as a whole reads: 'G is the set of all x such that x is green'. The character x here is a variable, a place holder, which can be used to stand for any object we might want to test for set membership. Thus, if we let x = 'tree', then x is a member of the set, but not if x = 'sky'.

This style of set definition becomes indispensible when an infinite number of objects belongs to a set. The set of all green objects in the world is very large, but given enough time, manpower, and lunatic motivation a list could be made; the number of green objects is finite. But there are infinite sets, that is, sets whose members could never be listed, even given world enough and time. A familiar example is the set of positive numbers {1,2,3...}. No matter how large the last number in this sequence, it is always possible to add 1, thus creating a yet larger number, and the sequence consequently never ends. In such a situation it is not only impractical to make a list, but impossible, and as such the 'set definition by rule' approach is the only one available.

c) To indicate that a given object belongs to a set, the symbol ε which is read as 'belongs to', is used. Thus, for a set A = {x | x is an animal}, cat ε A.

d) It is often necessary to refer not to a whole set, but to some part of it. A part of a set is called a subset. In the set A below, B is a subset of A: very object in B is necessarily in A, but not vice versa.

The notion of a subset is precise. There is no such thing as 'more or less a subset': if there is even one object in B that is not also in A, then B is not a subset of A.

2. Cartesian product

Sets are not much use on their own. Things can be done with them, however. One operation on them is particularly important: multiplication. Assume the sets {a,b,c} and {x,y,z}. Multiplying them yields:

{(a,x), (a,y), (a,z), (b,x), (b,y), (b,z), (c,x), (c,y), (c,z)}

Note that:

i. The result of set multiplication is itself a set.

ii. Multiplication has yielded a set of pairs, such that each element from the first set is paired with each element from the second.

iii. The pairs are ordered pairs. That is, the order of the components of each pair matters: (a,x) is not the same as (x,a). The order of pairs is determined by the order in which the sets are multiplied. Thus {a,b,c} x {x,y,z} yields the above set of pairs, while {x,y,z} x {a,b,c} yields:

{(x,a), (x,b), (x,c), (y,a)...etc}

Multiplication of sets is not, moreover, limited to only two. Any number of sets may be multiplied. For example, {a,b} x {i,j} x {x,y} yields:

{(a,i,x), (a,i,y), (a,j,x), (a,j,y), (b,i,x), (b,i,y), (b,j,x), (b,j,y)}

The components of this set are ordered triples. Multiples of four sets are called 4-tuples, of five sets 5-tuples, and so on. In general, given n sets A₁...A_n, the set of all n-tuples is called the Cartesian product.

3. Relations

In the language of love, a 'relationship' refers to the state in which two people find themselves. One can easily formalize this concept, and so gain understanding at the cost of losing its beauty. Take two sets: W = {x | x is a woman}, and M = {y | y is a man}. Then take the Cartesian product, which results in a set which contains all possible pairings of men and women. Now think of a man and a woman who are in love: they are one pair in the Cartesian product. Extend this idea, and think of all the men and women you know who love each other. These, too, will be pairs in the Cartesian product. And now go even further, and try to imagine all the men and women in Newcastle who are in love. By now we are dealing with a reasonably large set of pairs. Nevertheless, it is still a tiny subset of the Cartesian product of all the men and women in Newcastle --after all, any given man or woman will be in love with, usually, one or at most two or three others, but hardly with all the other women or men in the city. If one were now to be in a position to identify and pick out all the relevant love pairs from the Cartesian product of all men and women in Newcastle, and put them into a set, one would have what a mathematician would call a relation, a subset of a Cartesian product of sets such that members of the set are 'related' in some way, that they share certain specified characteristics, such as being in love.

Another example is the 'father of' relation. The set of father-son and father-daughter pairs is a subset of the Cartesian product of F x C, where F = {x | x is a man and x has offspring} and C = {y | y is human and y is not equal to x}. In this example, the significance of pairs being ordered emerges clearly: to say that John is the father of Mary is not the same as saying that Mary is the father of John, that is, (John, Mary) is not equivalent to (Mary, John).

A relation, therefore, is simply a subset of some Cartesian product of sets. In principle, the tuples in a relation can be of any length (corresponding to n-fold Cartesian product). In practice, a very important kind of relation is the binary relation, which consists of ordered pairs such as those discussed above.

4. Alphabet

In everyday usage, 'alphabet' refers to the 26 letters which comprise our writing system; the erudite will also know of other alphabets like Greek and Cyrillic. In formal language and automata theory, however, the notion of an alphabet is generalised to include any set of symbols representable in any medium: knots in a string, flashes of light, coloured flags, marks on paper, sounds. An alphabet can therefore be defined as a finite set of symbols.

5. Strings

A string over an alphabet is a finite sequence of symbols taken from an alphabet and written from left to right; repetition of symbols is allowed. Thus, assuming an alphabet A= {a,b,c}, some strings over this alphabet are:

aaaaabbbbb

abccba

ab

c

bbbbbbbbbbbbbbbbb

Clearly, many others are possible. Indeed, for any alphabet, it is possible to construct an infinite number of strings. If this seems outlandish, take the words of the English language as an alphabet --that is, each word as a separate symbol: A = {x | x is an English word}. Now we can start making strings:

This is the number one

This is the number two

...etc...

This is the number four trillion and one

...etc...

There is no end to the sequence. No matter what number is named at the end of the most recent sentence, it is always possible to name the next. There are, in short, at least as many sentences as there are positive numbers, and, as we saw, there are infinitely many positive numbers. And, of course, we haven't even begun to consider all the other possible English sentences yet. The set of all possible strings over an alphabet A is denoted A*.

So far, we have been talking about 'strings' as 'finite sequences of symbols' without asking where the notion of 'sequence' comes from. Intuitively, we all know what sequence means, but mathematics is not --and cannot be-- built on intuitions. Rather, mathematics is built on set theory; we have to base a definition of 'sequence' on set theory as well. The way to do this is via the Cartesian product described earlier. It was noted that there is no limit to the number of sets that may be multiplied: for n sets, the result is a set of n-tuples. One further point about set multiplication now needs to be made: a single set may be multiplied by itself any number of times. For example, given the set {a,b}, the operation {a,b} x {a,b} x {a,b} yields:

{(a,a,a,), (a,a,b), (a,b,a), (a,b,b), (b,a,a), (b,a,b), (b,b,a), (b,b,b)}

Each of these triples is in fact a sequence over the alphabet {a,b}, that is, each is a string. Thus we have definition of sequence, and thereby of string, in terms of set theory. To obtain strings of length 4 over this alphabet, multiply the set {a,b} four times, and so on up to arbitrary n. In general, then, a string is a member of the n-fold Cartesian product of an alphabet.

Two notes on strings:

i. It is possible to subdivide a string into substrings. Substrings are in effect chunks taken out of a string: if aaabbb is a string, then aa and abbb are substrings, as are aaabb, b, etc.

ii. There is such a thing in formal language and automata theory as the null (or empty) string, that is, a string consisting of no symbols at all. This is the kind of apparent fatuousness that gives mathematics its bad name --it's like calling an open field a null city, or an area of table a null cup of coffee-- but it has its uses in the theory of languages, and has to be tolerated.

6. Languages

Having defined sets, alphabets, and strings, we are now in a position to give a precise definition of what a language is. The definition is simple, even disappointingly so: a language is a subset of all the strings over an alphabet. Stated more formally, a language L is some subset of A*, where A is some alphabet.

Note that, though a language is a subset of an infinite set, it may itself be infinite. This appears nonsensical, but common sense fails where infinity is involved. It is easy to show that a subset of an infinite set can itself be infinite. Earlier we noted that the set of positive numbers constitutes an infinite set. Now, the set of all even positive numbers is clearly a subset of these. However, the sequence 2,4,6... has no end: it is always possible to add 2 to the most recent number in the sequence, without end. Thus a language turns out to be a (possibly infinite) set of strings.

This module is called Computational Linguistics, and we shall be dealing extensively with computation, both theoretically and in practice via computer programming. In all things it's crucial to know what one is talking about. 'Linguistics' is clear enough: it is, broadly, the study of language. But what is 'computation'? This section defines it.

To understand computation, it is first necessary to understand two fundamental concepts:

1. Functions

Functions are a special case of binary relations. Take two sets S and T. The Cartesian product S x T consists of ordered pairs (s,t) where s ε S and t ε T, and a binary relation is a subset of this product. What differentiates a function from a binary relation is the following restriction: each of the members of S included in the relation appears exactly once as the first component of an ordered pair. This is in sharp contrast with a relation, where any member of S included in the relation can appear as the first component of many ordered pairs. The difference is easily seen pictorially:

Note that, in the case of a function, each element in the first set is associated with one and only one element in the second. Note also that any number of elements in the first set may be associated with a single element in the second. Some examples:

A common mathematical function is 'squared', that is, a number multiplied by itself. Pictorially, the function looks like this:

For any number in the first set, there is exactly one number in the second. This is the same as saying that any number squared has a unique result: 2x2 is always 4, 3x3 is always 9, and so on. Thus, if one were to choose a number from the first set, say 4, the result would always be the same; the relevant pair is (4,16). The squared function as a whole goes: {(1,1), (2,4), (3,9), (4,16)...}.

The formal definition of function is rather abstract, and for most people takes a while to sink in. But functions are extremely important in mathematics, including language and automata theory, and the aim was to show that the concept is not plucked out of thin air, but rather is derivable from set theory via Cartesian product and relations. In practice, picture a function as a device for solving some particular problem. On the input side of the device, insert the information that needs to be processed; the output gives a unique answer:

2. Algorithms

An algorithm is a sequence of instructions which, if followed, is guaranteed to result in some desired state of affairs. Say, for example, the desired state of affairs is to get to the Student Union from the third floor of the Percy Building. An algorithm to achieve that might be:

i. Go through the red doors on the landing

ii. Walk down to the ground floor

iii. Go through the front door

iv. Walk down the quad

v. Walk under the arches

vi. Cross the road

vii. Walk 10 metres

viii. Turn right

Note two things: the instructions are in a prescribed sequence, and each instruction is absolutely explicit –there's no possibility of misinterpretation. If this sequence of instructions, or algorithm, is followed exactly, you are guaranteed to end up at the front door of the Union. Another example of an algorithm is a cooking recipe.

3. Computation

What do functions and algorithms have to do with computation? The answer is this: algorithms compute functions. Or, in other words, computation is algorithmic solution of functions. To understand what this means, consider an example. 'Subtraction' is an important and well known function in mathematics, and everyone uses it as a matter of course to subtract one number from another. But what if you were required to say how to do subtraction, that is, to specify an algorithm for subtracting one number from another? There are various possibilities; here are two:

1. Count backwards. Say 34 is to be subtracted from 256. The algorithm is to count backwards 34 from 256, and the result is the answer. This method may seem moronic, but it always works.

2. Write one number on a piece of paper, then the other one below it to that the digits line up, and then follow some rules; we all know what they are:

256

-34

___

222

So, given some Cartesian product P, a computation is an algorithm for selecting from P the tuples that constitute some desired function. Applying this to the above discussion, we take a 3-tuple Cartesian product of the numbers from, say, 0 to 999; this is a very large set, so only example tuples are given:

P = {(0,0,0), (0,0,1), (0,0,2)...(255, 34, 222), (256, 34, 222)...(998, 999, 999)...}

To subtract 34 from 256, we select the triple (256, 34, 222), where 222 is the answer. If we wanted to subtract 15 from 30, we would select (30, 15, 15), and so on. Note that most of the triples in this set do not belong to the function 'Subtract': 255 – 34 is not, for example, 222.

What, then, is 'computational linguistics'? The answer is now straightforward: computational linguistics is the computation of functions involving language. In other words, computational linguistics does not concern itself with, say, functions involving numbers (which is the preserve of numerical mathematics), but with functions involving symbol strings.

To introduce the notion of functions involving language, we consider the simplest of such functions: language definition. We have seen that a language is just a (possibly infinite) subset of an infinite set of strings. Let us now assume that we have an alphabet, and that we want to define some particular language. Can we invent a function that will specify which strings comprise the appropriate subset? To state the problem a little more formally: given an alphabet A, the set A* (that is, the Cartesian product) consists of all possible strings over A; for some specific language L, we want a function which will allow us to decide whether or not any particular string in A* is a member of L.

For present purposes, there are three ways of functionally defining L:

1. Make an exhaustive list of all the strings in A* belonging to L, that is, define the function by listing all the tuples which belong to it.

2. Construct a grammar which generates all and only the strings of L

3. Construct an automaton that either generates or recognises the strings of L

The straightforwardness of the first approach is appealing: to decide if a given string in A* belongs to L, simply look it up in the list. But what happens when the language to be defined contains a very large number of strings? The larger the number, the less practical the list becomes. True, there is no objection in principle, and very long lists can be constructed. In fact, though, this first approach is not merely potentially impractical but simply inadequate for our purposes. Why? We have seen that languages, though subsets of infinite sets, may themselves be infinite. Any generally effective language defining function has to be able to handle such languages. But, as the discussion of sets showed, there is no way to list an infinite set, since such a list would never end, and if the list never ended, the language would never be defined. The first of the above approaches has therefore to be rejected; the rest of this manual deals with the other two.

We now derive a sentence, and at each step build the corresponding tree:

AUTOMATA

Introduction

We have looked at grammars as one of two viable ways of stating functions for language definition. We now look at the other way: automata (singular: 'automaton'). An automaton is a machine. Machines are familiar enough. They are mechanisms consisting of parts that move in some specifiable relation to one another for some purpose. An old fashioned clock consists of gears, a spring, pointer arms, and a numbered face. These parts are interconnected so that the energy stored by the spring drives the gears, which in turn causes the arms to move around the clock face and so indicate the time. Now, before a physical machine like a clock is built, it has to be designed, that is, precisely described in some way --words, blueprints, etc. At this design stage the machine is abstract. It exists only by virtue of its specification, and has no physical reality yet; to construct a physical device in accordance with an abstract specification is to implement it. In what follows, we shall be both designing and implementing language definition machines.

An automaton is a function that can define a language as an acceptor. Picture an automaton as a black box whose internal workings are, for the moment at least, of no interest:

An acceptor looks like this:

A string from A* is fed into the machine. The machine processes it, and either accepts or rejects it by putting out a signal on either the accept or reject output. The set of all strings accepted by M is the language which M defines. Note that the result is a function: for every string, there is one and only one output value: 'accept' or 'reject'.

There are four main classes of machine: finite state automata, pushdown automata, linear bounded automata, and Turing machines. We shall confine ourselves to the first of these for the moment. This will mean looking inside the black boxes to see how finite state machines actually work. Finite state automata will be considered as acceptors in what follows. Before going on to consider them, however, some relevant concepts and terminology have to be introduced.

At the start of a chess game, the two players' pieces are arranged in rows on opposing sides of the board; the game ends when the pieces are arranged such that one player's king can no longer avoid being taken. Between beginning and end, the pieces assume a sequence of configurations on the board as each player makes his move in alternation with the other. Each successive configuration of pieces constitutes what automata theory calls a state --literally, the state of play. The initial opposing rows represent the start state. When a player makes the first move, the state of the game changes, that is, the configuration of pieces on the board has altered. When the opposing player then makes his move, the state changes again. And so on. In fact, a chess game can be seen as a sequence of state changes corresponding to the changing configurations of the board as the players take their turns. In the end, a final state is reached --checkmate-- and the game stops.

Further on chess. The pieces cannot move arbitrarily around the board. Each is constrained by:

• The pattern of movement prescribed for it by the rules of the game. For example, a pawn may only move forward, and only one square at a time; a knight may move two squares in any direction, and from there one square left or right, and so on.

• The current state of the board. It may not, in fact, be possible for a given piece to make a theoretically legal move because another piece is in the way.

So, at any given stage of the game, the choice of possible next moves is governed by these two constraints. Or, put another way, the transition between successive states is governed by the rules relating to the movement of specific pieces together with the current state of the game. A transition can, therefore, be regarded as the specification of the conditions under which it is possible to move from one state to another. The notions of state and transition will be fundamental to what follows.

Finite state automata for language definition

Finite state automata (henceforth FSA) are the simplest class of machines in automata theory. Unlike the other, more complex classes (which may have an infinite number of states), FSAs can only have a finite number of states, as the name indicates; it is this finiteness restriction which limits what FSAs can do in terms of language definition. We shall be looking at why this is so later.

Intuitively, an FSA consists of (a) a set of symbols which make up the strings which it is to process, (b) a set of states, and (c) rules which, given the current input symbol and the current state, say what the next state of the machine will be. The game of chess therefore constitutes a finite state machine. The set of symbols = the chess pieces. The set of states = the various possible configurations of the pieces in the board. The current input symbol = the piece which a player moves when it is his turn. The rules = the rules of chess which, given the current configuration of the board and the piece currently being moved, say what the next configuration of the board will be. What about the input string? It is the sequence of piece-moves in the course of the game, that is, since the pieces are symbols, the piece-move sequence becomes a symbol-sequence --a string. A game of chess can therefore be thought of as a string processing device.

We now proceed to a more formal definition of FSAs, first as acceptors and then as generators.

The FSA as acceptor

An FSA acceptor has three components:

1. A finite set of input symbols

2. A finite set of states, one of which is designated as the initial state, and zero or more of which are designated as final states.

3. A state transition function which tells what the next state of the machine will be, given the current state and the current input symbol.

The state transition function is often specified by a state diagram. In such a diagram, each of the machine's states is represented as a circle with the name of the state written inside it. The circles are linked by arrows which represent the transitions. On each arrow is written the symbol or symbols which, when input to the machine, will cause a transition from the state where the arrow originates to the state where the arrow points. Finally, the initial state is labelled with a minus sign, and a final state with a plus sign. Note, incidentally, that a state diagram is none other than a graph.

Here is an example of a very simple finite state acceptor:

A = {x,y,z} (the input alphabet)

S = {A,B,C} (the state set)

T = the diagram below (the state transition function)

To operate this FSA as an acceptor, we present it with an input string, which its reads one symbol at a time. Each time a symbol is read there is a transition from one state to another, starting at the initial state. The state transition function in each case uses the current state of the machine together with the current input symbol to determine the next state of the machine. After the last symbol of the string has been read, processing stops. If, at this point, the machine is in one of the states designated as final, then it has accepted the string, and if not it has rejected the string. The set of all strings accepted by the FSA is the language it defines.

Let us present the above machine with a string xyz,and start it in the initial state A. The machine reads the first symbol x, which causes it to follow the arc to state B. That done, the next symbol is read. It is y, so the machine goes back to state A. Now the final symbol z is read, and the machine goes to state C. Since C is a final state, the string xyz is accepted. What if the string had been yxz? Starting again with the initial state A, there is no arc labelled y out of A, and so the machine is said to crash, and the string is rejected.

Determinism

It is characteristic of the class of machines discussed so far that a transition from one state to another is completely determined by the current input symbol: for a given input symbol, there is one any only one possible route from the current state to the next state. The sequence of state changes through which such a machine passes is completely determined by the input string. This being so, it is clear that, for a given input string, there is a unique path through the machine. No matter how many times it processes a given string, it will always go through the same sequence of transitions. Such FSAs are said to be deterministic.

It is, however, possible to build nondeterministic FSAs which permit two or more different paths through a machine for the same input string. This implies that, at one or more points in the processing of a string, the transition from the current to the next state is not completely determined by the current input symbol, but rather that, given an input symbol, the machine is free to choose between or among alternative next states. On what grounds does the machine choose? No one knows, and no one cares. It is not determined.

How can one tell a deterministic from a nondeterministic FSA? In a deterministic FSA, no two arrows coming out of any state have the same label. It is this characteristic which ensures that the machine behaves deterministically --that it never has to make a choice. In a nondeterministic FSA, this constraint does not apply. Two or more arcs coming out of any state may have the same label. That is what makes the machine nondeterministic. When it is in such a state, and the current input corresponds to labels on two or more arcs, it must choose one of the paths, and that choice is free. Inspection of a state transition diagram will, therefore, always reveal whether a machine is deterministic or nondeterministic.

In the deterministic machine on the left, an a read when the machine is in the initial state A always causes a transition to B, but in the nondeterministic version on the right, a can lead to B, C, or D.

Two observations have to be made about determinism in FSAs:

i. Both sorts of FSA are equivalent in terms of their language defining capabilities

ii. A deterministic FSA is an efficient language acceptor. It either accepts or rejects a string at one pass through that string. Nondeterminstic FSAs are not as efficient. We have seen that they allow multiple paths through a machine for a given string. For every nondeterministic choice that is made, a separate and distinct state transition sequence comes into being. Now, it might happen that, for some string, one or more of these sequences leads to rejection. This introduces an element of uncertainty. Let us assume that a nondeterministic FSA rejects a string. Can we be sure that it is a 'real' rejection? Might it not be that the machine has made a 'bad' choice at some point, and that, given a 'good' choice at that point, the string would have been accepted? Yes, indeed. But, on the other hand, it might be a real rejection after all. The only solution to such uncertainties is to examine each of the state sequences which the machine is capable of generating for a given string to see if any of them leads to acceptance. In fact, when dealing with nondeterministic FSAs, it is usual to assume that the machine exhaustively explores all possible sequences, and if at least one of them leads to a final state, then the input string is accepted.

In view of all this, the characterization of a deterministic FSA as a language acceptor given earlier has to be modified for nondeterministic FSAs. We say that a string is accepted by a nondeterministic FSA if there is at least one state transition sequence for the string which leads to an accept state. If none of the possible paths through the machine leads to an accept state, then the string is rejected. For example:

Using the alphabet {a,b,c}, we present the deterministic machine with the string abbc. The first transition is from A to B, then two loops in B, and finally a c transition to the final state D; the string is accepted. Presented with the same string, the nondeterministic machine might decide on that same path, in which case it accepts the string, but it might also take the middle arc out of A, in which case it goes immediately to the final state D. But the string has not been completely read, so it crashes, and another possible path is tried. Finally, the a arc from A to C leads to accept.

Limitations of finite state automata

The foregoing discussion has several times referred to the 'power' of language defining devices, be they grammars or automata, and the time has come to say what this means.

There are languages which no FSA can define. The standard example of such a language is aⁿbⁿ, that is, the language consisting of strings where some number of a's is followed by exactly the same number of b's: ab, aabb, aaabbb and so on. For an FSA to accept strings belonging to this language, it would have to remember how many a's it has read from input, and then read exactly the same number of b's; if the a and b sequences match, the string is accepted. The only way to achieve this is to have a separate state for every a and b in the sequence. A machine like this:

doesn't work because, in addition to aⁿbⁿ strings, it also accept strings consisting of any number of a's followed by any number of b's: abbb, aaaaab, etc. Thus, to accept the language a¹b¹ the machine has to look like this:

For a²b² it looks like this:

And so on. But an FSA for aⁿbⁿ cannot be built because n is unbounded --that is, of arbitrary size, and not specified in advance-- and an FSA, by definition, has a bounded number of states. No matter how many a and b states are built into an FSA, one can always present a string of greater n --say, n + 1-- and thereby cause the accepter to fail.

To overcome this problem, it is necessary to move to a more powerful type of automaton: the Pushdown Automaton. That is dealt with in what follows.

Pushdown automata

The finite state machine is the simplest kind of computational architecture. But, as we have just seen, there are languages which no FSA can define. The standard example of such a language is aⁿbⁿ, that is, the language consisting of strings where some number of a's is followed by exactly the same number of b's: ab, aabb, aaabbb and so on. This limitation is not merely theoretical for the computational linguist who wants to design an NLP system: natural languages include the aⁿbⁿ structure. An example from English is centre-embedding sentences like

where the number of noun phrases and the number of verb phrases must be the same. FSA computational architecture cannot, therefore, be used for general NLP work. A more appropriate architecture is proposed in what follows: the pushdown automaton, or PDA.

A pushdown automaton is essentially an FSA with some extra features added to make it more powerful as a language defining mechanism, and in particular to overcome thc aⁿbⁿ problem just mentioned. Since we have already studied FSAs, and since PDAs are just uprated FSAs, it is probably best to preface a formal definition of PDAs by an informal discussion of the extra features which these machines have.

Input tape

In the discussion of FSAs no mention was made of how an input string is actually presented to the machine. For a PDA, an input medium is specified. It is a tape on which the input string is written. The tape can be thought of as being divided into squares or cells, as below. Initially each cell is blank; the $ symbol is used to indicate this:

The string to be input is written on the tape, starting at the left and putting one symbol in each successive cell. For example, the string abcde appears like this:

The tape extends as far as one likes to the right, so that it can accommodate any finite length string. When the machine reads the tape, it does so one symbol at a time, starting at the leftmost cell, and keeps going until it reaches the first blank cell on the right (ie, the first $), which tells it that the string has been completely read. The tape may be read from left to right only, and any given cell may only be read once.

Stack

Unlike an FSA, a PDA has a memory by means of which it can remember what symbols it has read from the input tape, and what order it read them in. It is this memory which crucially distinguishes the class of PDAs from the class of FSAs. The mechanism which gives a PDA its memory is called a stack; understanding how a stack works is essential to understanding PDAs.

Assume that you are washing dishes in a retaurant. Once you have dried each one, you put it on top of the existing pile. Every now and then, a waiter needs a plate and takes one from the top; the pile shrinks and grows as you wash and the waiter serves, depending on supply and demand.

The two important things to note are:

i. At any given time, only the top plate is readily accessible. It is, of course, possible to grab one from elsewhere in the pile, but that's inconvenient and can bring the whole thing crashing down --the normal thing is to remove each plate in succession from the top.

ii. The order of stacking is preserved. The first plate washed is at the very bottom of the pile, and, assuming as above that plates are taken only from the top, it will be the last the waiter takes. In such a pile the rule is: first in, last out, or, equivalently, last in, first out.

The stack in a PDA works just like the pile of plates except that. instead of storing plates, it stores symbols. As the PDA reads symbols, it may decide that it needs to keep some record of having done so, and inserts each successive one on top of the stack: the first symbol goes into an empty stack, the second goes on top of it, the third on top of the second, and so on. Thus, if the machine were to read the string abcd and store each successive symbol on the stack, the following would happen:

If these symbols are needed again later (and they typically are), they can be removed one at a time from the top of the stack. As with the top plate in a restaurant stack, only the top symbol of the PDA stack is accessible.

Why the apparently arbitrary restriction that only the top of the stack should be accessible? To function, a PDA needs to be able to remember what symbols it has read from the input tape, and also the order in which it read them. The first half of this memory requirement could be satisfied by simply throwing the symbols already read onto a heap, and letting the machine root through the heap when it needed to know whether or not it had read some particular symbol. But if the order of reading is also crucial, then this approach is clearly inadequate: this is where the restriction that symbols can only be added to or taken from the top of the stack begins to make sense. The machine knows that the first symbol it read is at the bottom of the stack. the second above it, and so on up to the most recently read symbol at the top. The original order of reading is presented: allowing random access to any part of the stack would destroy that ordering.

Controller

The heart of a PDA is a controller which coordinates (i) reading from the tape, and (ii) putting symbols into and taking them out of the stack. This controller is an FSA whose states are restricted to the following types:

i. START: start the machine

ii. READ: read a single symbol from the input tape

iii. PUSH: insert a single symbol on top of the stack

iv. POP: remove the topmost symbol from the stack

v. ACCEPT: accept the input string and stop

vi. REJECT: reject the input string and stop

What such a controller actually looks like will emerge shortly. 

We are now in a position to give a formal definition of a PDA. A pushdown automaton consists of six components:

1. a finite set of input symbols

2. a finite set of stack symbols

3. an input tape

4. a stack

5. a set of control states: {START, READ, PUSH. POP, ACCEPT, REJECT}

6. a state transition function which given the current state and the current input symbol, tells what the next state of the machine will be.

Note that items (1), (5), and (6) of this definition are exactly the same as those for an FSA: this is because a PDA is, at heart, an FSA with tape and stack added. Nothing has yet been said about the stack alphabet. This is irrelevant for the moment, but will be important when the issue of parsing or syntax analysis is addressed later in this module.

The PDA as acceptor

Let's go back to the very simple FSA we looked earlier:

This FSA accepts all strings consisting of c or any number of ab alternations (abababab. . . ) including none, and ending with a c. The equivalent PDA looks like this:

Let us follow the operation of this machine. The transition to the START state can be made any time one likes. Thereafter, follow (1)-(2) below until the machine enters an ACCEPT or a REJECT state:

1. In the READl state do the following according to the symbol which is read from the tape:

i. If a, make a transition to READ2

ii. If b, reject the string because

• if this b is the first symbol in the string, then the string is illegal since it does not begin with a

• if this b is not the first symbol in the string, then it must follow another b, which is illegal.

iii. If c, accept the string.

iv. If $, the end-of-string marker, reject the string because

• If no other symbols have previously been read, then there are no symbols on the input tape, and the null string is not part of the language.

• If other symbols have already been read, then the string does not end in c and is therefore illegal.

2. In the READ2 state, do the following according to the symbol which is read from the tape:

i. If a, reject the string because the aa combination is illegal

ii. If b, return to READl

iiii. If c, reject the string because the ac combination is illegal

iv. If $, reject the string because no string can end in a.

Note that this PDA does not use its stack --there are no PUSH or POP states in the diagram. It is no less a PDA for that. The point about PDAs is that they can use a stack if they need to, and this one didn't. A PDA without a stack is pretty pointless, though. After all, the whole point of going to PDAs was to gain more power in terms of language defining capability, and the stack is what gives it that extra power; without a stack, it's nothing more than an FSA, and nothing is gained. What recommends the above PDA is its simplicity. It is easy to understand, both intrinsically and in relation to the equivalent FSA, and as such was useful as a first encounter with PDAs. We now go on to consider a 'real' PDA --one with a stack-- and see how it deals with the problemmatical aⁿbⁿ structure:

To illustrate the operation of this machine. Iet us assume that the stack is initially empty, and that the input tape contains the string aaabbb. A read head (analogous to the read head on a tape deck) is also shown. so as to make clear which cell is being read at any one time. So:

The machine STARTs and goes to the first READ state. which reads the first cell of the tape and moves the read head one cell to the right. That cell contains a, so there is a transition from READ to PUSH. The PUSH inserts a into the stack; the stack and tape now look like this:

After the PUSH there is a loop back to the beginning. The machine enters the READ state again, reads another a, and PUSHes that a onto the stack:

The same thing happens a third time, and we are back to READ again:

This READ, however, gets the symbol b, which causes a transition to a POP state, which in turn takes the top symbol off the stack. Depending on whether this top symbol is S or b on the one hand, or a on the other, the machine will either REJECT or else READ again. In this case an a is POPped, so there is a transition to READ. The stack and tape now look like this:

Note that there is now one fewer a on the stack after the POP. The READ now returns a b, which leads back to POP. This POPs another a, which takes us one again to READ. The situation now is:

This READ produces a third b, which initiates the same cycle once more, and leaves the tape and stack looking like this:

The stack is now empty, and the tape read head is over a blank square (that is, the input string has been completely read). Since it is now in a READ state, the machine gets $, which causes a transition to the rightmost POP. If that POP produces $, then the machine goes to ACCEPT. Otherwise --that is, if there are any symbols left in the stack-- it goes to REJECT. In the present case it gets a $, and all is well.

The discussion of automata ends at this point. We now have enough knowledge of them to go on to one of the main applications of automata in computational linguistics: natural language processing, and syntax analysis (also known as parsing) in particular.

NATURAL LANGUAGE PROCESSING

Introduction

Natural language processing (NLP) aims to develop computer-based systems for applications in speech and text forms of NL. Various types of application have been or are being developed:

a) Word processing

b) Text analysis: extraction of syntactic regularities from text for purposes of stylistic analysis, author attribution, and so on.

c) Data search: search of large bodies of text for particular words or combinations of words for information retrieval, as in library catalogues or Web browsers.

d) Data mining: summarization of large text corpuses, such as case law.

e) NL front ends for computational systems, such as computerized telephone answering services or database query systems

f) Artificially intelligent systems, the aim of which is to build systems that understand NL as humans do, and respond to queries and commands appropriately.

The above list is in order of difficulty: (a) – (d) are now well established, (e) is coming along, but (f) has proven much more difficult than anyone imagined, and there is currently a huge research effort devoted to it.

In what follows, we consider a central issue in a variety of NLP applications: syntax analysis or parsing. The notion that NL strings have a complex constituent structure is fundamental to linguistic theory; parsing is a function that, given an NL string as input, outputs a description of its constituent structure. A parser for any language, natural or otherwise, is a transducer. A transducer can, as a first approximation, be seen as a black box which takes strings as input, and delivers corresponding structural descriptions as output:

What follows is devoted to specifying the contents of the black box.

Another way to represent the structure which this tree represents is:

B (C,D)

For this tree

the alternative representation is:

And so on; the algorithm will eventually generate the target string, and will thereby have discovered the target string's structure.

Pop S and follow the arc. The state now is

Pop ( and follow the arc

Pop NP and follow the arc. This is where our problems arose. Let's say the machine (metaphorically) flips a coin and follows the left branch

The parse should now proceed successfully. Pop (

Pop DET