查找上下文无关语法（CFG）

Question

给出一个上下文无关语法H，该语法生成​​语言 M = {a^m b^n | 2m> n> m}。 ' 提示：m不能为0，因为在这种情况下2m = m。 m不能是1，因为在这种情况下2> n> 1，这样的自然数n不存在。所以语言M中最短的字符串是aabbb。对于较长的字符串，您需要确保 bs的数量n和m的数量满足2m> n> m。

Answer 1

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

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

第一后每个生产将单个a和一个或两个b秒。第二个生产可以单独使用以生成最短的字符串（对于给定数量的a s），而第三个单独使用时生成最长的字符串（对于给定数量的a s）。那些最短和最长的琴弦呢？这些制作能用来获取所有这些字符串吗？

他们可以。你可以通过归纳来证明。您必须证明语言中所有长度为n（1）的字符串都是由语法生成的，而（2）是由语法生成的语言是用语言生成的。

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

归纳假设：假定语法生成所有字符串，并且语言中包含长度为k的任何字符串。

归纳步骤：我们必须显示语法生成所有字符串的唯一字符串长度为k + 1。我们已经说过，语法不能产生一个不在语言中的字符串;通过仅使用第二次生产，您将获得n = m + 1，并且通过使用第三次生产，您只能获得n = 2m - 1。要看到它会生成该语言中的所有字符串，请回想一下，该语言中的任何字符串都以至少两个a s开始，并以至少三个b s结尾。所以，它可以写成aaxbbb。可以看出，如果该字符串是用该语言编写的，则axbb和/或axb中的一个或两个都必须使用该语言。

1. axbb是在L如果2(m - 1) > n - 1 > m - 1，或2m - 1 > n > m
2. axb是在L如果2(m - 1) > n - 2 > m - 1，或。

由于在任何情况下开始与基部情况下，我们具有2m - 1 > n至少一个和/或n > m + 1，其中之一也是L。通过归纳假设，语法产生它;并且其中一个语法产物将从中产生长度为k + 1的原始字符串。所以语法生成L中的所有字符串。