如何在输入字符串的长度上使用感应来编写证明？

Question

在我的计算理论课程中，我们的许多问题涉及对输入字符串长度的归纳来证明有关有限自动机的陈述。我了解数学归纳，但是当串发挥作用时，我会真正绊倒。如果有人会逐步进行这样的证明的过程，我将非常感谢。

这是一个示例问题（hopcroft and ullman 3rd Edition的练习2.2.10）：

考虑使用以下过渡表的DFA：

        0    1
       ________
-> A |  A    B
  *B |  B    A

非正式地描述该DFA接受的语言，并通过归纳来证明您的描述正确的输入字符串。

这是书中答案的问题，所以我不是在寻找有人做我的作业。我只需要有人直接向我解释。

书的答案：（摘自 这里)

自动机告诉后一种情况下，所见1的数量是否为（状态A）或奇数（状态B）。这是对| w |的容易吸引力显示DH（a，w）= a，并且仅当W具有偶数为1的数字。基础：| W | = 0。然后w，空字符串肯定具有1个，即零1，而δ-hat（a，w）=A。

归纳：假设字符串陈述短于w。然后w = za，其中a为0或1。

• 情况1： a = 0。如果W具有偶数为1，则Z也是如此。通过电感假设，δ帽（a，z）= A。DFA的跃迁告诉我们δ-hat（a，w）=A。如果w的奇数为1，则z也是如此。通过电感假设，δhat（a，z）= b，而DFA的过渡告诉我们δ-hat（a，w）=B。因此，在这种情况下，δ-hat（a，w）= a如果且仅当W具有偶数1的1。

• 案例2： a =1。如果W具有偶数1的数量，则Z的奇数为1。通过电感假设，δ帽（a，z）=B。DFA的跃迁告诉我们δ-hat（a，w）= A 1。通过电感假设，δhat（a，z）= a，DFA的过渡告诉我们δ-hat（a，w）=B。因此，在这种情况下，δ-hat（a，w）（a，w） ）= a，仅当w具有偶数1的1。

我了解如何证明$ sum_ {i = 0}^{n} i = frac {n（n+1）} {2} $使用感应的东西。我只是对这与构建字符串的作用感到困惑。我对粗体部分感到困惑。我不明白它们是如何提出的/如何实际证明什么是被接受的/它是如何归纳的。

顺便说一句，δ-hat是扩展的过渡函数。

Answer 1

^{由于不清楚您的问题在哪里，我将从一开始就开始。}

数学归纳就像游戏一样 中国耳语 （在理想情况下，即所有沟通都是无损的）或（完美设置） 骨牌: ：您从某个地方开始，并表明您的下一步不会破坏任何东西，假设直到那时才打破。

更正式地，每个归纳证明都由三个基本要素组成：

• 就职 锚, ， 还 基本情况: ：您在小案例上显示索赔所持。
• 就职 假设: ： 你 认为 该主张适用于您要证明某些内容的一定子集。
• 感应 步: ：使用该假设，您表明该主张适用于更多要素。

当然，必须对步骤进行调整，以使其覆盖整个基础集（以极限为单位）。

重要说明：对自己的归纳技能充满信心的人通常会掩盖锚点并隐含假设。虽然在向专家受众（例如论文）展示您的作品时，这是可以的，但这是 不是 建议自己做证据，尤其是作为初学者。写下一切。

---

考虑一个简单的示例（ Mathbb {n}， leq）$;我们要证明$ sum_ {i = 0}^{n} i = frac {n（n+1）} {2} $ hold com in in mathbb {n} $持有所有$ n 。

• 锚: ：对于$ n = 0 $，$ sum_ {i = 0}^{n} i = 0 = frac {n（n+1）} {2} $清楚地保持。
• 假设: ：假设$ sum_ {i = 0}^{k} i = frac {k（k+1）} {2} $保留任意的，但固定²$ n in mathbb {n} $。

• 步: ：对于$ n+1 $，计算总和：

  美元n+1+ frac {n（n+1）} {2} = frac {（n+2）（n+1）} {2} $

  因此，身份以$ n+1 $的价格保留。 （我们注意到，我们只需要假设的一小部分，即$ k = n $。经常发生。）

归纳原则现在向我们保证了这一主张确实存在：我们以$ 0 $的价格直接向其展示。该步骤说，如果价格售价为$ 0 $，它也以$ 1 $的价格持有；如果售价为$ 1 $，则价格也售价为$ 2 $；等等。

---

让我们看看另一个示例，这次是在$（2^ mathbb {n}， subseteq）$上。我们要证明的声明是：对于每个有限的子集$ a $ a $ mathbb {n} $，电源的大小$ 2^a $ a $ a $ a $ as $ as $ 2^{| a |} $³。再次，我们在$（ Mathbb {n}， leq）$上执行了归纳，即在$ a $的大小上。

• 锚： 考虑（仅）尺寸$ 0 $的（仅）集空套。显然，$ 2^ emptySet = { emptyset } $，因此$ | 2^ emptyset | = 1 = 2^0 $，如所声称的。
• 假设： 假设所有集合$ a subseteq mathbb {n} $ with $ | a | leq n $带有一些任意，但已修复$ n in mathbb {n} $，我们有$ | 2^a | = 2^{| a |} $。

• 步： 令$ b subseteq mathbb {n} $ untunary size $ n+1 $，然后让$ b in b $ intunary（此类$ b $都存在为$ n+1> 0 $）。现在，该假设适用于$ b setMinus {b } $，因此$ | 2^{b setMinus {b }} | = 2^n $。自从

  $ qquad displayStyle 2^b = 2^{b setMinus {b }}} cup {a cup {b } mid a in a in 2^{b setminus setminus {b }} } $，

  我们确实有$ | 2^{b} | = 2 cdot | 2^{b setminus {b }} | = 2 cdot 2^n = 2^{n+1} $，如所声称的。

同样，通过归纳，索赔得到了证明。

---

现在，就您的问题而言，可以使用一个常见的技巧： 加强声明. 。如果您将自己的主张提出为“自动机接受所有单词奇怪的单词”，则您会得到一个归纳假设，例如“在所有长度$ n $的单词中，正是那些奇怪数量的单词在自动机中接受了奇数，” 。这不会带您到任何地方，因为我们对给定（接受）单词的哪个部分中的哪些一无所知。该假设不适用于您从任意选择的单词中删除的任何内容。

因此，您想提出一个更强有力的主张：“当自动机$ b $时，只有当输入的消耗部分包含奇数时，并且只有一个奇数”。请注意，这意味着前者的主张。

• 锚: ：在处理唯一的零长字符串（$ varepsilon $）之后，自动机显然处于状态$ a $中。
• 假设: ：假设索赔保留了长度长达$ n $的输入片段，该片段是任意选择但修复的。
• 步: ：考虑一个任意的单词$ w in {0,1 }^{n+1} $。有两种情况。
  1. $ W $包含偶数数量。最后符号有两种情况。
     1. $ w_n = 0 $：在这种情况下，$ w'= w_1 dots w_ {n-1} $包含偶数数量。通过归纳假设，消耗$ w'$后，自动机在状态$ a $中。 $ w_n = 0 $ $ w_n = 0 $会导致自动机停留在状态$ a $。
     2. $ w_n = 1 $：在这种情况下，$ w'= w_1 dots w_ {n-1} $包含一个奇数。通过归纳假设，自动机在消耗$ w'$之后处于状态$ b $。如声称，消耗$ w_n = 1 $会导致自动机切换到状态$ a $。
  2. $ w $包含奇数。类似于情况1。

归纳原则意味着该主张确实存在。

---

1. 您按照部分顺序执行归纳；锚需要涵盖所有最小元素，有时甚至更多（取决于陈述）。
2. “任意但固定”是必不可少的！我们无法在步骤中更改$ n $，并将其视为固定的数字，但我们也不能假设任何事情。
3. 用$ 2^a $表示电源套装似乎很奇怪。它植根于观察到的电源集等于从$ a $到$ {0,1} $的所有功能的集合，这是这样表示的。
4. 选择$ b $ nutary对于覆盖整个空间至关重要。人们可能会说：“拿任何这样的$ a $，添加以前没有的元素。”在这种情况下，这将做同样的事情，但是在更复杂的设置中犯错可能很容易（例如将节点添加到图形上）。始终将任意的更大对象进行分开，以将假设应用于其各个部分；切勿从较小的较小物体中组装出较小的物体，这些物体被假设掩盖。