识别最大类型的形式语言
recognise max type of formal language
目前我正在努力学习和理解正式语言和语法。
我了解乔姆斯基层次结构，但我发现了一项我不知道他们如何获得解决方案的任务。
任务是：
G=({S},{a,b},S,P)
P={S->epsilon, S->aS, S->Sb}
- 这个语法的最大类型是什么？
L(G)的最大类型是什么？
我知道语法是类型 2，但答案中写着 L(G) 是
输入 3.
好像也有一种描述这种语言的类型3文法，但是你怎么知道哪种是形式语言的最大类型呢？有什么技巧吗？
我不认为有一些简单的算法方法可以始终区分语言 L(G) 的 class 是什么；我的意思是说，总的来说，我认为有些案例根本无法以一种或另一种方式证明。这来自 incompleteness/undecidability，假设不受限制的文法可以编码算术。这个手感很波浪
启发式的，你可以试着去理解你的语言是什么，你可以改造语法来试图强制语法更简单等等，但是这些并不能保证成功。
在这种特殊情况下，弄清楚语言是什么，识别它是正则的，并为它写下语法也不错。
S -> e
S -> aS
S -> Sb
从 S 派生的任何字符串可以以 S -> aS 之前的任意数量的 a 开始，并且可以以 [=16] 之前的任意数量的 b 结束=].我们可能会假设语言是 a*b*，然后通过显示 (1) L(G) 是 ab 和 (2) a[=67 的子集来证明它=]b 是 L(G) 的子集。
(1) 对S -> aS和S -> Sb的应用次数进行归纳证明。基本情况：如果这些都不应用，则只有字符串 e 是可导出的。 e 在 a*b* 中，因此基本情况得到确认。归纳假设：假设由 S -> aS 和 S -> Sb 的 k 个应用派生的任何字符串都在 a*b* 中。归纳步骤：我们表明使用这些产品的 k+1 应用派生的任何字符串也在 a*b* 中。通过跳过 k+1st 产生式，在 k+1 产生式中派生的任何字符串都有一个在 k 产生式中产生的字符串。这是因为产生式使非终结符集保持不变。我们已经知道 k 应用程序中派生的这个较短的字符串在 a*b* 中。我们有两种情况需要考虑：
S -> aS：这会在 a*b* 中的较短字符串的前面添加一个 a，将其保留在 a*b*.S -> Sb：这会在 a*b* 中的较短字符串的末尾添加一个 b，将其保留在 a*b*.
由于这两种情况都将字符串保留在 a*b* 中，因此产生式的 k+1 应用程序中派生的所有字符串都在 a*b* 中，并且通过归纳，语法生成的所有字符串都是.
(2) 考虑 a*b* 中的任何字符串 a^n b^m。它由以下语法生成：n 应用 A -> aS、m 应用 B -> Sb 和 1 应用 S -> e。因此 a*b* 中的所有字符串都是由语法生成的。
目前我正在努力学习和理解正式语言和语法。 我了解乔姆斯基层次结构，但我发现了一项我不知道他们如何获得解决方案的任务。 任务是：
G=({S},{a,b},S,P)
P={S->epsilon, S->aS, S->Sb}
- 这个语法的最大类型是什么？
L(G)的最大类型是什么？
我知道语法是类型 2，但答案中写着 L(G) 是
输入 3.
好像也有一种描述这种语言的类型3文法，但是你怎么知道哪种是形式语言的最大类型呢？有什么技巧吗？
我不认为有一些简单的算法方法可以始终区分语言 L(G) 的 class 是什么；我的意思是说，总的来说，我认为有些案例根本无法以一种或另一种方式证明。这来自 incompleteness/undecidability，假设不受限制的文法可以编码算术。这个手感很波浪
启发式的，你可以试着去理解你的语言是什么，你可以改造语法来试图强制语法更简单等等，但是这些并不能保证成功。
在这种特殊情况下，弄清楚语言是什么，识别它是正则的，并为它写下语法也不错。
S -> e
S -> aS
S -> Sb
从 S 派生的任何字符串可以以 S -> aS 之前的任意数量的 a 开始，并且可以以 [=16] 之前的任意数量的 b 结束=].我们可能会假设语言是 a*b*，然后通过显示 (1) L(G) 是 ab 和 (2) a[=67 的子集来证明它=]b 是 L(G) 的子集。
(1) 对S -> aS和S -> Sb的应用次数进行归纳证明。基本情况：如果这些都不应用，则只有字符串 e 是可导出的。 e 在 a*b* 中，因此基本情况得到确认。归纳假设：假设由 S -> aS 和 S -> Sb 的 k 个应用派生的任何字符串都在 a*b* 中。归纳步骤：我们表明使用这些产品的 k+1 应用派生的任何字符串也在 a*b* 中。通过跳过 k+1st 产生式，在 k+1 产生式中派生的任何字符串都有一个在 k 产生式中产生的字符串。这是因为产生式使非终结符集保持不变。我们已经知道 k 应用程序中派生的这个较短的字符串在 a*b* 中。我们有两种情况需要考虑：
S -> aS：这会在a*b*中的较短字符串的前面添加一个a，将其保留在a*b*. 中
S -> Sb：这会在a*b*中的较短字符串的末尾添加一个b，将其保留在a*b*. 中
由于这两种情况都将字符串保留在 a*b* 中，因此产生式的 k+1 应用程序中派生的所有字符串都在 a*b* 中，并且通过归纳，语法生成的所有字符串都是.
(2) 考虑 a*b* 中的任何字符串 a^n b^m。它由以下语法生成：n 应用 A -> aS、m 应用 B -> Sb 和 1 应用 S -> e。因此 a*b* 中的所有字符串都是由语法生成的。