查找上下文無關語法（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中的所有字符串。