2.2.3 正式语法的表达力量

正式语法的主要属性就是它有生成规则,可用于重写部分句子形式(=正在构建的句子),和产生所有句子形式的起始符。在生成规则中我们发现有终结符和非终结符;而在完整的句子中只有终结符。这大概就是:剩下的部分就看语法作家和句子创造者的创造力了。

这是一个令人印象深刻的简洁的框架,然后就马上有了一个问题:这就足够了吗?这很难说,但是如果这还不是最好的,那我们暂时也没有更好的表达形式了。听起来可能有点奇怪,所有其他人们已知的生成集合,都被证明相同或甚至不那么强大,比起短语结构语法。明显生成一个集合的方法,当然最简单的是写一个程序来生成,不过这也证明了所有可以用程序生成的集合都可以用短语结构语法来生成。甚至还有一些神秘的方法,但最终都被证明不够具有表现力。另一方面,也没有证据能表明还存在更强大的方法。但鉴于许多完全不同的方法最后都由于相同的阻碍而停止,所以几乎不可能1在找到一个更强大的方法了。见例子Révész [394, pp 100-102].

作为表现力的另外一个例子,我们应该谈谈Manhattan龟的运动的语法。 Manhattan龟只能在平面上运动,且只能往东南西北方向运动,每次运动距离为一个格子。图Fig 2.5给出了所有可以回到原点的循环路劲。根据第2条规则,应该说明,许多作者需要在左侧至少有一个非终结符的符号。这条规则总是可以强制执行通过添加新的非终结符。

Fig 2.5

简单的东南西北循环路劲已经在图Fig 2.6中展示(使用首字母缩写)。注意规则(ε)中的空替代,这导致了上图中第三个M后的结束。

Fig 2.6

1. Paul Vitány指出如果科学家说神秘东西“几乎不可能” has pointed out that if scientists call something “highly unlikely” they are still generally not willing to bet a year’s salary on it, double or quit.

results matching ""

    No results matching ""