1

给出一个生成语言的上下文无关文法 H

 M = {a^m
b^n
| 2m > n > m}.
‘

提示：m 不能为 0，因为在这种情况下 2m = m。m 不能为 1，因为在那种情况下 2 > n > 1，这样的自然数 n 不存在。所以语言 M 中最短的字符串是 aabbb。对于较长的字符串，需要确保 bs 的个数 n 和 as 的个数 m 满足 2m > n > m。

4

1 回答 1

1

我们知道aabbb是在语言中，所以S -> aabbb这不是一个糟糕的开始。我们如何在语言中获得更长的字符串？好吧，我们需要保持2m > n > m. 这种语言中最短的字符串（对于给定数量的as）b比它们的 s 多一个a，所以我们可能会猜测这S -> aSb是一个不错的猜测；它当然会生成我们语言中的字符串，即最短的字符串（对于给定数量的as）。类似地，我们语言中最长的字符串的数量比它们的数量少b一倍a，因此S -> aSbb也是安全的，因为它会生成最长的字符串（对于给定数量的as）。到目前为止，我们的语法是这样的：

S -> aabbb
S -> aSb
S -> aSbb

第一个之后的每个产生式都添加一个单个a和一个或两个bs。第二个产生式可以单独使用以生成最短的字符串（对于给定数量的as），而第三个产生式单独使用时会生成最长的字符串（对于给定数量的as）。最短和最长的字符串之间的字符串呢？这些产品也可以用来获取所有这些字符串吗？

他们能。你可以用归纳法来证明。您必须证明语言中所有长度为n(1) 的字符串都是由语法生成的，并且 (2) 由语法生成的字符串都在语言中。

基本情况：语言中最短的字符串是aabbb，它是由语法生成的。

归纳假设：假设语法为任何字符串生成该语言中所有且唯一的字符串，直到并包括长度k。

归纳步骤：我们必须证明语法为任何长度的字符串生成语言中所有且唯一的字符串k + 1。我们已经论证过，文法不能产生不在该语言中的字符串；只使用第二个产生式，你得到n = m + 1，而通过使用第三个产生式，你只得到n = 2m - 1。要查看它生成该语言中的所有字符串，请回想该语言中的任何字符串至少以两个as 开头并以至少三个bs 结尾。所以，可以写成aaxbbb。可以证明，如果该字符串是语言，那么其中一个或两个axbb和/或axb也必须是该语言。

  1. axbb在Lif中2(m - 1) > n - 1 > m - 1，或2m - 1 > n > m
  2. axb在Lif2(m - 1) > n - 2 > m - 1或2m > n > m + 1.

因为在每种情况下，从基本情况开始，我们至少有一个2m - 1 > n和/或n > m + 1，其中一个也在L. 通过归纳假设，语法生成它；并且语法的一种产生将从它产生长度的原始字符串k + 1。所以语法会生成L.

于 2017-10-19T19:52:39.550 回答