2.3 Recursive transition networks

This section describes a more powerful technique for defining languages. The surface forms of a textual language are a (typically infinite) set of strings. To define a language, we need to define a system that produces all strings in the language and no other strings. (The problem of associating meanings with those strings is more difficult; we consider it in later chapters.)

A recursive transition network (RTN) is defined by a graph of nodes and edges. The edges are labeled with output symbols—these are the primitives in the language. The nodes and edge structure provides the means of combination.

One of the nodes is designated the start node (indicated by an arrow pointing into that node). One or more of the nodes may be designated as final nodes (indicated by an inner circle). A string is in the language if there exists some path from the start node to a final node in the graph where the output symbols along the path edges produce the string.

Figure 2.1 shows a simple RTN with three nodes and four edges that can produce four different sentences. Starting at the node marked Noun, there are two possible edges to follow. Each edge outputs a different symbol, and leads to the node marked Verb. From that node there are two output edges, each leading to the final node marked S. Since there are no edges out of S, this ends the string. Hence, the RTN can produce four strings corresponding to the four different paths from the start to final node: “Alice jumps”, “Alice runs”, “Bob jumps”, and “Bob runs”.

Figure 2.1: Simple recursive transition network.

Recursive transition networks are more efficient than listing the strings in a language, since the number of possible strings increases with the number of possible paths through the graph. For example, adding one more edge from Noun to Verb with label “Colleen” adds two new strings to the language.

recursive definitionThe expressive power of recursive transition networks increases dramatically once we add edges that form cycles in the graph. This is where the recursive in the name comes from. Once a graph has a cycle, there are infinitely many possible paths through the graph!

Consider what happens when we add the single “and” edge to the previous network to produce the network shown in Figure 2.2 below.

Figure 2.2: RTN with a cycle.

Now, we can produce infinitely many different strings! We can follow the “and” edge back to the Noun node to produce strings like “Alice runs and Bob jumps and Alice jumps” with as many conjuncts as we want.

Exercise 2.5.  Draw a recursive transition network that defines the language of the whole numbers: 0, 1, 2, $\ldots $

Exercise 2.6.  How many different strings can be produced by the RTN below:

Exercise 2.7.  Recursive transition networks.

  1. How many nodes are needed for a recursive transition network that can produce exactly 8 strings?

  2. How many edges are needed for a recursive transition network that can produce exactly 8 strings?

  3. $\left[\star \star \right]$Given a whole number $n$, how many edges are needed for a recursive transition network that can produce exactly $n$ strings?

Subnetworks. In the RTNs we have seen so far, the labels on the output edges are direct outputs known as terminals: following an edge just produces the symbol on that edge. We can make more expressive RTNs by allowing edge labels to also name subnetworks. A subnetwork is identified by the name of its starting node. When an edge labeled with a subnetwork is followed, the network traversal jumps to the subnetwork node. Then, it can follow any path from that node to a final node. Upon reaching a final node, the network traversal jumps back to complete the edge.

For example, consider the network shown in Figure 2.3. It describes the same language as the RTN in Figure 2.1, but uses subnetworks for Noun and Verb. To produce a string, we start in the Sentence node. The only edge out from Sentence is labeled Noun. To follow the edge, we jump to the Noun node, which is a separate subnetwork. Now, we can follow any path from Noun to a final node (in this cases, outputting either “Alice” or “Bob” on the path toward EndNoun.

Figure 2.3: Recursive transition network with subnetworks.

Suppose we replace the Noun subnetwork with the more interesting version shown in Figure 2.4.This subnetwork includes an edge from Noun to N1 labeled Noun. Following this edge involves following a path through the Noun subnetwork. Starting from Noun, we can generate complex phrases like “Alice and Bob” or “Alice and Bob and Alice” (find the two different paths through the network that generate this phrase).

Figure 2.4: Alternate Noun subnetwork.

To keep track of paths through RTNs without subnetworks, a single marker suffices. We can start with the marker on the start node, and move it along the path through each node to the final node. Keeping track of paths on an RTN with subnetworks is more complicated. We need to keep track of where we are in the current network, and also where to continue to when a final node of the current subnetwork is reached. Since we can enter subnetworks within subnetworks, we need a way to keep track of arbitrarily many jump points.

A stack is a useful way to keep track of the subnetworks. We can think of a stack like a stack of trays in a cafeteria. At any point in time, only the top tray on the stack can be reached. We can pop the top tray off the stack, after which the next tray is now on top. We can push a new tray on top of the stack, which makes the old top of the stack now one below the top.

We use a stack of nodes to keep track of the subnetworks as they are entered. The top of the stack represents the next node to process. At each step, we pop the node off the stack and follow a transition from that node.

Using a stack, we can derive a path through an RTN using this procedure:

  1. Initially, push the starting node on the stack.

  2. If the stack is empty, stop. Otherwise, pop a node, $N$, off the stack.

  3. If the popped node, $N$, is a final node return to step 2.1

  4. Select an edge from the RTN that starts from node $N$. Use $D$ to denote the destination of that edge, and $s$ to denote the output symbol on the edge.

  5. Push $D$ on the stack.

  6. If $s$ is a subnetwork, push the node $s$ on the stack. Otherwise, output $s$, which is a terminal.

  7. Go back to step 2.

Figure 2.5: RTN generating “Alice runs”.

Consider generating the string “Alice runs” using the RTN in Figure 2.3. We start following step 1 by pushing Sentence on the stack. In step 2, we pop the stack, so the current node, $N$, is Sentence. Since Sentence is not a final node, we do nothing for step 3. In step 4, we follow an edge starting from Sentence. There is only one edge to choose and it leads to the node labeled S1. In step 5, we push S1 on the stack. The edge we followed is labeled with the node Noun, so we push Noun on the stack. The stack now contains two items: $\left[\textit{Noun}, \textit{S1}\right]$. Since Noun is on top, this means we will first traverse the Noun subnetwork, and then continue from S1.

As directed by step 7, we go back to step 2 and continue by popping the top node, Noun, off the stack. It is not a final node, so we continue to step 4, and select the edge labeled “Alice” from Noun to EndNoun. We push EndNoun on the stack, which now contains: $\left[\textit{EndNoun}, \textit{S1}\right]$. The label on the edge is the terminal, “Alice”, so we output “Alice” following step 6. We continue in the same manner, following the steps in the procedure as we keep track of a path through the network. The full processing steps are shown in Figure 2.5.

Exercise 2.8. Show the sequence of stacks used in generating the string “Alice and Bob and Alice runs” using the network in Figure 2.3 with the alternate Noun subnetwork from Figure 2.4.

Exercise 2.9.  Identify a string that cannot be produced using the RTN from Figure 2.3 with the alternate Noun subnetwork from Figure 2.4 without the stack growing to contain five elements.

Exercise 2.10.  The procedure given for traversing RTNs assumes that a subnetwork path always stops when a final node is reached. Hence, it cannot follow all possible paths for an RTN where there are edges out of a final node. Describe a procedure that can follow all possible paths, even for RTNs that include edges from final nodes.

  1. For simplicity, this procedure assumes we always stop when a final node is reached. RTNs can have edges out of final nodes (as in Figure 2.2) where it is possible to either stop or continue from a final node.