2.7.2 uvw理论

uvw理论的简单形式应用于正则(3型)语言。我们已经看到FS语法生成的句子形式全部都仅只包含一个非终结符,在结尾出现。在一个很长的句子的生成期间,一个或多个非终结符必须出现两次或多次,因为只能有有限数量的非终结符。图Fig2.23展示了当我们一个一个列出句子形式时所看到的。

图1 Fig 2.23

子串vA的一次出现到下一次之中被生成,u是让我们能到达A的一个序列,w是让我们能终止生成过程的序列。将明确指出,从第二个A开始,我们可能重复了跟第一个A一样的路径,从而生成了uvvw。这将我们引导到uvw理论,或正则语言的泵引理(pumping lemma for regular languages):正则语言的任何一个足够长的字符串都能被切分成u,v,w3个部分,所以对n ≥ 0的所有uvnw都是这个语言的一个字符串。