我试图证明以下几点：
如果 G 是乔姆斯基范式中的上下文无关文法，那么对于任何字符串 w 属于长度为 n ≥ 1 的 L(G)，它恰好需要 2n-1 步来对 w 进行任何推导。
我将如何证明这一点？
问问题
10151 次
1 回答
16
作为提示-因为乔姆斯基范式中的每个产品都具有以下形式
S → AB，对于非终结符 A 和 B，或形式
S → x，对于终端 x，
然后派生一个字符串将按以下方式工作：
- 创建一个正好有 n 个非终结符的字符串，然后
- 将每个非终结符展开为单个终结符。
应用第一种形式的产生式会将非终结符的数量从 k 增加到 k + 1，因为您将一个非终结符 (-1) 替换为两个非终结符 (+2) 以获得 +1 个非终结符的净增益。由于您从一个非终结符开始，这意味着您需要执行第一种形式的 n - 1 个产品。然后，您需要 n 多个第二种形式来将非终结符转换为终结符，总共得到 n + (n - 1) = 2n - 1 个产品。
为了证明你确实需要这么多，我建议做一个矛盾的证明，并表明你不能用更多或更少来做到这一点。作为提示，请尝试计算每种类型的产生式的数量，并显示如果不是 2n - 1，则字符串太短，或者您仍将保留非终结符。
希望这可以帮助！
于 2013-03-03T19:13:11.510 回答