内容发布更新时间 : 2025/5/7 1:41:51星期一 下面是文章的全部内容请认真阅读。
3. 该产生式是A?(E1)*的形式。这时要引入一个新的变元B（同样，B不能在别处出
现）然后把这个产生式变为：
A ? BA A ? ε B ? E1
4. 该产生式是A?(E1)+的形式。这时要引入一个新的变元B（同样，B不能在别处出
现）然后把这个产生式变为：
A ? BA A ? B B ? E1
5. 该产生式是A?(E1)?的形式。把这个产生式变为：
A ? ε A ? E1
例5.24：下面来考虑 怎样把这条DTD的规则
转换为合法的CFG产生式。首先，这条规则的体可以看作两个表达式的连接，第一个是型号，价格，处理器，RAM，第二个是DISK+。因此引入两个变元A和B来分别代表这两个子表达式，就可以得到下面的产生式：
PC ? AB
A ? 型号 价格 处理器 RAM B ? DISK+
其中仅有最后的一个产生式不是合法的形式。这时再引入一个新的变元C和两个新的产生式来代替它：
B ? CB | C C ? DISK
在这个特例下，由于A所能得出的表达式仅仅是几个变元的连接，而DISK仅仅是一个单个的变元，因此实际上没必要有A和C这两个变元，而只要用下面的产生式来代替它们就够了：
PC ? 型号 价格 处理器 RAM B B ? DISK B | DISK
□
5.3.5 5.3节习题
习题5.3.1：证明如果一个串是括号匹配的，就像例5.19中所说的那样，那么它一定能用B?BB|(B)|ε来生成。提示：对串的长度进行归纳。
* 习题5.3.2：考虑同时包含圆括号和方括号且这两种括号都匹配的所有串的集合。对于这种串的来历有一个例子。考虑C语言中的表达式，圆括号表示函数的参数，方括号表示数组的下标。如果把C语言中的表达式里除了括号以外的字符都去掉，那么剩下的串就是这种类型的括号匹配的串了。例如：
f (a[i]*(b[i][j], c[g(x)]), d[i])
就变成了一个括号匹配的串([]([][][()])[])。试着设计一个文法来定义所有的圆括号和方括号都匹配的串。
! 习题5.3.3：在第5.3.1节中，考虑下面的文法：
S ? ε| SS | iS | iSe
并且当时说过可以通过重复的使用下面的方法来测试它的语言L的成员性：（这个测试过程从w开始，并且在这个重复的过程中串w会发生变化）
1. 如果这个串是从e开始的，那么测试失败，w不在L中。 2. 如果串里没有e了（还可以有i），那么测试通过，w在L中。
3. 否则，删掉第一个e和它左边的i，然后继续对剩下的串进行这三个步骤的测试过
程。 试证明这个测试过程能够正确的识别出L中的串。
习题5.3.4：把下面的东西加入到图5.13中的HTML的文法中去： * a) 项目列表必须用标记符来表示结束。
b) element可以试无序列表，就像有序列表一样。无序列表是通过用标记符
- 和
括住来表示的。 ! c) element可以是一个表格。表格是用和
里面可以有一行或多行，每一行都用和来表示。第一列是标题，包含一个和多个域，分别用标记符来表示（假设它们不是闭的，虽然它们应该是）。接下来的列用标记符来表示。