Linguistics 484 - Grammars Ling484 Notes A. C. Brett
Department of Linguistics
University of Victoria
Clearihue C139
Last updated: 25 March 2001

Transition Network Grammar

Transition Network Grammars developed out of the concept of the transition network of a finite-state automaton, but are equivalent to push-down automata because the arcs comprising the network of a Transition Network Grammar represent transcriptions of the rules of a context-free grammar (Woods (1970)). Sentences generated by the grammar are accepted by a Transition Network Grammar through the process of traversing the network comprised of these arcs.

The simplest form of Transition Network Grammar is called a Recursive Transition Network (RTN). RTNs form the core or basic component of the Augmented Transitions Networks (ATNs). An ATN is an RTN with additional resources that permit it to process the complex attributes or features of lexical and syntactic categories. Thus, for example, an ATN can perform subject/verb number agreement. ATNs are historically important, both computationally, but also in terms of their application as psychological models of language processing. See, for example, Fodor and Frazier (1980), Wanner (1980), and Wanner and Maratsos (1978).

This note deals only with Recursive Transition Networks, and the following topics are discussed:

Recursive Transition Networks. Recursive Transition Networks (RTNs) resemble Finite-State and Push-Down Automata (FSAs and PDAs) in several respects. In the first place, like FSAs and PDAs, RTNs are recognisers (acceptors) of sentences generated by phrase-structure grammars. In fact, RTNs are equivalent to PDAs in that they are capable of accepting sentences generated by Chomsky Type 2 (context-free) grammars. RTNs also resemble FSAs and PDAs in that their workings may be represented employing transition networks. RTNs actually developed out of the concept of the transition network associated with an FSA (and hence, their name).

NP Subnetwork

Arcs and Nodes. Beyond their pedigree, however, RTNs share little else with FSAs and differ substantively from FSA transition networks. The most obvious of the differences between the two classes of machine lies in the labelling of the states (nodes) and arcs of their transition networks. While the states of the transition network of an FSA are labelled by nonterminal symbols of the grammar to which the automaton is equivalent, and the arcs are labelled by the terminals, the arcs of an RTN are labelled by the nonterminals of the equivalent grammar, and the nodes (states) are labelled arbitrarily, with the labelling employed solely to distinguish among them. Thus, there is normally no connection between the nodes of an RTN and the grammar to which it corresponds (is equivalent).

Note that, although the foregoing observations cite FSA transition networks, these statements apply equally to PDA networks, with the exception that in the case of the latter machines, arcs corresponding to lambda/pop transitions are not labelled by terminal symbols of the equivalent grammar.

Note also that, notwithstanding the statements above regarding the labelling of RTN arcs only with nonterminal symbols, some special arcs can be treated as if they were labelled with terminals. In some treatments of RTNs, those arcs involved directly in the processing (reading and accepting) of terminal symbols can be labelled with the terminal symbols. This issue will be discussed below.

Subnetworks. Another significant difference between RTNs and the transition networks of FSAs and PDAs is that, while the networks of the latter machines consist of one complete network, the network of the former can be treated as a collection of subnetworks. There is one subnetwork for each distinct left- hand side symbol in the rules of the production set of the grammar to which the RTN is equivalent. For example, if the grammar includes the rewrite rules

NP DET N, and
then the RTN will consist of at least three subnetworks, one each for the symbols S, NP, and VP. In some treatments of RTNs, there will also be subnetworks for the preterminal, lexical category symbols DET, N, and V which appear on the left-hand sides of the lexical rules of the grammar.

Paths. The arcs in these subnetworks are labelled with the right-hand side symbols of the rules to which the subnetwork corresponds. For example, there are two arcs in the NP subnetwork corresponding to the two right-hand side category labels of the rule

One of these is labelled DET while the other is labelled N. These two arcs appear in the middle of the accompanying illustration of an NP subnetwork. The DET arc runs from the NP node to the node identified with the number 1. The N arc extends from this node to the one labelled with the number 9 which identifies an accepting state for the subnetwork. The two arcs constitute a path through the NP subnetwork because the starting node of the DET arc is the initial node of the subnetwork, and the ending node of the N arc is the final, accepting node of the subnetwork.

Recall that the node labels are arbitrary. Although the NP label is meaningful because it identifies the left-hand of the rewriting rules to which the NP-subnetwork corresponds, there is no such rationale underlying choice of the labels for the other two nodes except that they serve to distinguish among them.

VP Subnetwork

Different paths in a subnetwork arise from the different rules in the equivalent grammar with the same left-hand side symbol. For example, if the production set of the grammar includes the three rules

VP V NP, and
with the left-hand side VP, then the corresponding subnetwork will consist of three paths.

The topmost path in this illustration of a VP-subnetwork, consisting of the one arc labelled V, corresponds to the rule VP V. The middle path, consisting of the V and the NP arcs, corresponds to the VP V NP rule, while the bottom path, consisting of the AUX and VP arcs, corresponds to the VP AUX VP rule.

Nondeterminism. In connection with this VP-subnetwork, note that the RTN must be nondeterministic because there are two arcs bearing the same label starting from the initial VP node. Procedurally, nondeterministic behaviour of RTNs is emulated by backtracking. If we assume arcs of the subnetwork are tested in the order from top to bottom as indicated in the foregoing figure, then the V arc terminating in the final state node of the subnetwork will be tried first. Should this test fail, and result in the data string not being accepted, then the RTN will, in effect, backup and try the second path, that consisting of the V and NP arcs.

Recursion. Note also in the subnetwork illustrated above that there is an arc, namely the VP arc in the bottom path, the label of which is the same as the name of the subnetwork itself. Thus, traversal of this arc requires re-entry into the subnetwork containing it; that is, the recursive nature of the rule VP AUX VP is translated into recursive traversal of the corresponding subnetwork. This recursive traversal of a subnetwork is actually the origin of the use of "recursive" in the name Recursive Transition Network for this class of recogniser.

Top-Down Processing. An RTN performs a top-down recognition; that is, it begins by testing paths of an S-subnetwork corresponding to those rules in the equivalent grammar the left-hand side of which consists of the root or initial symbol. An input string is accepted as a sentence generated by the equivalent grammar if there exists a path in the S-subnetwork; that is, there exists a sequence of contiguous arcs from the initial node to the final node of the S-subnetwork.

S Subnetwork

A particular arc in a given subnetwork can be traversed only if there exists a path in another subnetwork that has the same name as the label of the the particular arc. For example, the paths in the S subnetwork illustrated here correspond to the rewrite rules

S WH VP, and
The NP arc in the S subnetwork shown here, which corresponds to the NP label on the right-hand side of the rule S NP VP, can be traversed only if a path can traversed the NP subnetwork. Similarly, the VP arc in the S subnetwork can be traversed only if a path in the VP subnetwork can be traversed.

Depth-First Processing. The NP arc must, however, be traversed before the VP can be attempted. Thus, the NP subnetwork must be entered, and one of its paths be traversed, before an attempt to traverse the VP arc in the S subnetwork can be undertaken. Consequently, the NP subnetwork is entered, and the arcs comprising one of its paths are traversed before a return is made to the S subnetwork. The NP subnetwork path might consist of the DET and N arcs, meaning that first a word in the determiner category, and then a word in the noun category must be identified before any further arcs in the S subnetwork can be traversed. Processing by an RTN can therefore be described as proceeding depth-first.

Cat Operation. A cat operation is performed when an arc is traversed that is labelled by a lexical category symbol. For example, a "catting" operation is undertaken when the DET arc in the NP subnetwork is traversed. During this operation, a DET subnetwork is entered. Subnetworks such as the DET, as well as any other subnetworks corresponding to lexical rewriting rules, consist of arcs that are labelled with words. Thus, these subnetworks may be viewed as something like the arcs in the transition network of a finite-state automaton. If the word on the arc traversed is the same as a word in the sentence being processed by the RTN, then that word is accepted.

Push Operation. The entry from one subnetwork into another is described as a push operation. For example, if an NP arc in the S subnetwork is being traversed, and the RTN leaves the S subnetwork to enter the NP subnetwork, then the RTN is described as "pushing for an NP." The NP symbol in this case is pushed onto a push-down store to record the arc of the S subnetwork that is being travered when the RTN leaves it to enter the NP subnetwork. On return to the S subnetwork from the NP subnetwork, if a noun phrase has been identified, the NP label is popped from the store.

The push-down store is normally not included explicitly in the specification of an RTN. This store actually resides in the memory of the computer on which the RTN is implemented. It is this memory which enables a computer to keep track of its position in a procedure, corresponding to the traversal of one subnetwork, while it is performing another procedure that corresponds to a different subnetwork. This memory, in the form of a push-down store, provides RTNs with the resources required to accept sentences generated by context-free grammars. Hence, recursive transition networks are equivalent to context-free grammars, and to push-down automata.

Linguistics 484 Notes Index Top of Page