老实说，我对数学归纳的了解如下：
1. prove P(0) - base step
2. for all n ≥ 1, prove (P(n − 1) -> P(n)) - inductive step
我目前正在尝试从上图中解决问题，但我做不到。我刚接触这种东西，我不知道，我也无法从我仅有的一点知识中推断出任何东西。
我不知道如何开始，我也不知道如何将我上面描述的小知识应用到那个问题上。
如果您能通过仔细的解释帮助我解决上述问题，非常感谢您。
问问题
122 次
1 回答
1
作为提示，让 P(k) 成为“任何具有恰好 k 个字符串的语言都是正则的”语句。使用您的归纳想法，您需要执行以下操作：
证明任何包含 0 个字符串的语言都是正则的。对于没有字符串的语言，你能说什么？你能为这种语言构建一个 DFA、NFA 或正则表达式吗？
假设任何具有 n-1 个字符串的语言都是正则的，然后证明任何具有 n 个字符串的语言都是正则的。如果一种语言中包含 n 个字符串，则可以将其拆分为包含 n-1 个字符串的语言和包含一个字符串的语言。关于第一语言，你能说什么？如果你有一个正则表达式，你能做些什么来将它改编成一个语言的正则表达式，其中还有一个字符串？
于 2016-01-21T04:25:38.583 回答