图3 覆盖形容词短语内部组成成分细节的FSA语法的FSA语法的一部分

图2和图3中的自动机可以组合成一个单一的更大的名词组识别器。这个识别器以NG自动机开始，迭代地把每个参照展开为其他规则或自动机。因为这些参照中没有一个是递归的，即AdjP的展开不必参照AdjP，所以这样的展开是可能的。

但是，如果建立一个更复杂的英语语法，就会出现这种递归。例如，在关系从句和其他名词后修饰语的规则中，定义一个完整的NP需要参照其他NP。

处理递归的一个方法是限制递归的数量，只允许有限数量的递归。FASTUS就是这样做的。在FASTUS中使用了层叠式自动机，一层一层地从较小的名词组逐渐构成较大的名词组，这样就限制了递归在每个层次中的数量。FASTUS的第二层发现非递归的名词组；第三层把这些名词组加上度量短语，结合成更大的像NP那样的单位：

20, 000 iron and "metal wood" clubs a month

然后再附加上介词短语：

production of 20, 000 iron and "metal wood" clubs a month

再处理名词组连接词：

a local concern and a Japanese trading house

在一个单层的系统中，这些现象的每个都分别要求递归规则（例如，NP→NP and NP）。但是，如果把剖析分解成两个层次，FASTUS就可以把规则左手边的一个NP作为不同种类的对象来处理，也就是说，把规则左手边的一个NP作为规则右手边的两个NP来处理。

处理递归的第二种方法是使用貌似有限状态而实际上并非有限状态的模型。其中的一个模型是递归转移网络（Recursive Transition Network,简称RTN）。一个RTN可以使用如图2和图3所示的状态图的集合来定义，其中每个弧上有一个终极符号或非终极符号。RTN和FSA的不同之处在于它们处理非终极符号的方法。在RTN中，每当自动机遇到一个带有非终极符号的弧时，它把这个非终极符号作为一个子程序（subroutine）来处理。自动机把它的当前位置放到一个栈中，跳到这个非终极符号。当这个非终极符号剖析结束之后，自动机再跳回原位置。如果一个NP规则包含一个自身的参照，RTN再次把当前位置放到栈中，然后再跳回NP的开始处。

由于RTN与上下文无关语法是完全等价的，所以遍历一个RTN就可以想像成是使用一个上下文无关规则来进行简单的自顶向下剖析的过程，而且这个过程可以用图表示出来。在描述或显示一个语法时，通常可以使用RTN作为一个恰当的比喻图示，或者作为实现具有小量递归但又不是有限状态的系统的一种方法。

责任编辑：admin