问题

问题2.1:2.1.3.4节的对角化似乎是一个不在列表上语言的有限描述。为什么这个描述不在列表上,列表可是包含所有有限描述的?

问题2.2:在2.1.3.4节中,我们考虑函数n,n+102n,来找到应该有别于行n的位的位置。这些函数的一般形式是什么,既,什么样的函数集合可以生成不具有有限描述的语言?

问题2.3:位Manhattan龟路径设计一个语法,使其从其起点开始不允许向西爬行。

问题2.4:图Fig 2.7的单调1型语法生成所有**anbncn**形式的字符串,n≥1。为什么n=0排除在外?

问题2.5:设计一个1型语法,可以生成包含两个相同部分的所有字符串的语言:www是给定字母表(见2.10)的任何字符串。

问题2.6:在2.4.1节,我们有句子生成机制,将新创建的句子形式添加到队列结尾,并声称这实现了广度优先生成。当我们将它放在队列开头时,机制采用深度优先生成。说明这是不起作用的。

问题2.7:2.4.1节的最后一段中说到“在增加(实际上是‘不减少’)的长度”。解释为什么说是“不减少”就足以表明。

问题2.8:将一个没有递归的语法生成的有限语言的字符串数量与该语法的结构关联。

问题2.9:查阅2.6节。在你的计算环境中找到更多的例子,零作为一个数字得到二等对待。

问题2.10:在你最喜欢的解析器生成器系统中,为语言{ε}写一个解析器。同样也为语言{}写一个解析器。

问题2.11:使用uvw理论(2.7.2节),说明对于语言***aibi***没有可用的3型语法。

问题2.12:在2.9节我们说到,无用的规则可以被从语法中移除掉而不影响语言的生成。这似乎是表明“其移除不影响语言”就是我们所希望的,而不是仅仅是没有无用的。注释。

问题2.13:根据2.2.2节,写一个Chomsky生成过程,作为一个闭包算法。