为识别每个 L 的 PDA 创建图表
Creating a diagram for a PDA that recognizes each L
试图理解 PDA，但并不真正掌握如何绘制它们。
首先，我真的不明白如果限制说 #a、#b 或 #c 是 "greater than zero" 或 "greater than or equal to zero."，PDA 看起来会有什么不同 我画了下面的 PDA每个教科书问题的图表对我来说似乎足够正确。只是想看看二手货。
- 所以我的第一个 PDA 的逻辑是，对于每个 "a" 输入，都会有四的倍数 "a" 移到堆栈上。当输入 "b" 时，堆栈中的每个 "a" 都会产生一个空字符串，从而清除堆栈。
- 对于第二个 PDA，我创建了一个非确定性 PDA，因为可以有零个 "a" 或零个 "b"。因此，对于 "bb" 的每个偶数输入，堆栈都不会发生变化，因为可以有无限多个 "bb"，但是 "a" 将保留在堆栈中，因为它有如果有 "a".
，则在 "bb" 之后再次调用
如果我正确理解了您的图表，那么它们是不正确的，并且似乎暴露了对 PDA 工作原理的基本误解。我不会尝试与您合作来了解您在制作这些产品时的思维过程，而是会推导出新的 PDA 并让您将它们与您尝试过的相协调。我不会提供图纸，但我会描述图纸的样子；我将提供 tables，因为它们更容易渲染。
1) L = {a^i b^j | i > 0, j = 4i + 2}
当你制作任何自动机时，你都在尝试寻找状态和转换。一个很好的起点是想知道初始状态，因为我们知道我们需要一个。它是我们唯一需要的，还是我们需要更多？是接受吗？对于这种语言，我们可以看到它不接受（因为，如果初始状态是接受，PDA 将接受空字符串，这在我们的语言中是不可能的，因为我们要求 i > 0）。由于我们的语言确实包含字符串，我们知道我们需要一个接受状态，所以我们知道我们至少需要两个状态；称它们为 q0 表示初始状态，称它们为 q1 表示我们知道我们需要的其他状态。现在我们有了几个状态，我们可以暂时关注第一个转换。
现在，我们知道我们需要在字符串的开头允许一些 a。事实上，我们必须至少要求一个。让我们想一想这意味着什么。假设我们添加一个从 q0 回到 q0 接受 a 的转换。如果我们不把任何东西放到堆栈上，我们就会丢失关于我们是否看到了任何 a 的信息。然而，我们确实有一个堆栈，所以我们可以记住我们需要知道的东西：我们之前见过一个 a。因此，我们可以添加在读取 a 时从 q0 转换到 q0 的能力，并将该事实记录在我们的堆栈中。我们稍后将需要检查堆栈的能力，看看我们是否看到了一些 a。现在我们可以问要将什么放入堆栈。
我们这里有一些选择，没有正确或错误的答案。您选择什么将取决于您所依赖的自动机公式以及您的自动机设计目标。是的，自动机的设计方式与真机或计算机程序相同。我们希望做出符合形式主义规则且简单易用的设计选择。一种方法是添加我们稍后期望看到的与我们已经消费的符号相对应的内容；对于我们现在看到的每个 a，我们以后需要看到四个 b；所以我们现在可以将 bbbb 添加到堆栈中，然后为从输入中读取的每个 b 从堆栈中弹出一个 b。这很方便。请注意，当我们读取第一个 a 时，我们可以通过添加 bbbbbb 而不是 bbbb 来处理“+2”要求，只要我们知道何时读取第一个 a - 我们通过检查堆栈知道。
基于所有这些考虑，我们可以为我们一直在设计的 PDA 制作部分 table，然后我们可以评估我们的进度，看看我们还需要去哪里：
q e S q' S'
--- --- --- --- ---
q0 a Z q0 bbbbbbZ
q0 a b q0 bbbbb
我们用Z代表栈底。当我们看到第一个 a（我们知道它是第一个，因为堆栈是空的，即最上面的符号代表堆栈的底部）我们添加 bbbbbb。每个连续的 a 将 bbbb 添加到堆栈的顶部（通过将 b 替换为 bbbbb）。
现在我们必须考虑如何处理b。我们可以通过从 q0 循环到 q0 来处理 a b 吗？片刻的想法应该让你相信这不是一个好主意。如果我们在看到 a b 时从 q0 循环到 q0，那么我们没有简单的设施来防止 PDA 接受更多的 a。但这会导致字符串不可能是我们想要的语言，因为在我们的语言中，a 不能跟在 b 之后。因此，似乎有必要接受 b's 的任何转换，而不是将状态 q0 作为其目标。因此，我们选择 q1 作为所讨论过渡的目标。来源是什么？到目前为止，我们的PDA中只达到了q0，可供选择的只有q0和q1。我们现在有两个选择：要么我们提供一种从 q0 到 q1 的转换机制，而不会看到 a b，要么我们提供一种在 a b 上转换的机制。这些方法中的第一种需要基于我们之前的设计选择的不确定性，因此我们可能更喜欢后者，因为它更明确且更容易推理。这导致以下转换（添加到我们之前的 table）：
q e S q' S'
--- --- --- --- ---
q0 a Z q0 bbbbbbZ
q0 a b q0 bbbbb
q0 b b q1 -
这个转换表示当我们在 q0 中看到一个 b 并且我们之前在堆栈中看到过 a 时，转换到 q1 并丢弃最顶层的堆栈符号。请记住，我们设计堆栈的方式是，对于我们在输入中读取的每个 b，我们应该始终在堆栈中丢弃一个 b。
现在我们已经到达状态 q1，自然要问的问题是这个状态是否应该接受。答案是一定不能，否则我们可以接受一个没有足够 b 的字符串来清除它的堆栈；也就是说，我们会有 j < 4i + 2。所以我们需要一个新状态，称之为 q2，q1 不会接受。我们应该用 q1 做什么？通过添加以下转换，我们可以轻松地使用它来读取剩余的 b 并从堆栈中弹出：
q e S q' S'
--- --- --- --- ---
q0 a Z q0 bbbbbbZ
q0 a b q0 bbbbb
q0 b b q1 -
q1 b b q1 -
只要我们有 b 要读取并且 b 在堆栈上，就可以进行第四次转换。在此过程中可能会发生三件事：
- 我们 运行 出栈中的 b，但输入中仍有 b
- 我们 运行 在完成读取输入中的所有 b 的同时从堆栈中取出 b
- 当输入耗尽时，堆栈中仍有 b
只有第二种情况我们才接受，我们可以通过第四次转换的重复应用来达到第二种情况。但是，q1 不接受。因此，我们将需要一种方法从 q1 过渡到接受状态——我们不妨将 q2 称为这种状态——当我们可能处于这种状态时。如果我们真的处于那个状态，当我们在 q1 中看到一个空堆栈时，我们需要一个 epsilon 转换：
q e S q' S'
--- --- --- --- ---
q0 a Z q0 bbbbbbZ
q0 a b q0 bbbbb
q0 b b q1 -
q1 b b q1 -
q1 - Z q2 Z
现在，在 q2 中，我们可能是情况 1 或情况 2：堆栈是空的，但是我们还有更多符号要读取吗？事实证明这至少没有问题，因为进一步的输入符号将导致 PDA 在状态 q2 中立即崩溃。
第二个留作练习。
试图理解 PDA，但并不真正掌握如何绘制它们。 首先，我真的不明白如果限制说 #a、#b 或 #c 是 "greater than zero" 或 "greater than or equal to zero."，PDA 看起来会有什么不同 我画了下面的 PDA每个教科书问题的图表对我来说似乎足够正确。只是想看看二手货。
- 所以我的第一个 PDA 的逻辑是，对于每个 "a" 输入，都会有四的倍数 "a" 移到堆栈上。当输入 "b" 时，堆栈中的每个 "a" 都会产生一个空字符串，从而清除堆栈。
- 对于第二个 PDA，我创建了一个非确定性 PDA，因为可以有零个 "a" 或零个 "b"。因此，对于 "bb" 的每个偶数输入，堆栈都不会发生变化，因为可以有无限多个 "bb"，但是 "a" 将保留在堆栈中，因为它有如果有 "a". ，则在 "bb" 之后再次调用
如果我正确理解了您的图表，那么它们是不正确的，并且似乎暴露了对 PDA 工作原理的基本误解。我不会尝试与您合作来了解您在制作这些产品时的思维过程，而是会推导出新的 PDA 并让您将它们与您尝试过的相协调。我不会提供图纸，但我会描述图纸的样子；我将提供 tables，因为它们更容易渲染。
1) L = {a^i b^j | i > 0, j = 4i + 2}
当你制作任何自动机时，你都在尝试寻找状态和转换。一个很好的起点是想知道初始状态，因为我们知道我们需要一个。它是我们唯一需要的，还是我们需要更多？是接受吗？对于这种语言，我们可以看到它不接受（因为，如果初始状态是接受，PDA 将接受空字符串，这在我们的语言中是不可能的，因为我们要求 i > 0）。由于我们的语言确实包含字符串，我们知道我们需要一个接受状态，所以我们知道我们至少需要两个状态；称它们为 q0 表示初始状态，称它们为 q1 表示我们知道我们需要的其他状态。现在我们有了几个状态，我们可以暂时关注第一个转换。
现在，我们知道我们需要在字符串的开头允许一些 a。事实上，我们必须至少要求一个。让我们想一想这意味着什么。假设我们添加一个从 q0 回到 q0 接受 a 的转换。如果我们不把任何东西放到堆栈上，我们就会丢失关于我们是否看到了任何 a 的信息。然而，我们确实有一个堆栈，所以我们可以记住我们需要知道的东西：我们之前见过一个 a。因此，我们可以添加在读取 a 时从 q0 转换到 q0 的能力，并将该事实记录在我们的堆栈中。我们稍后将需要检查堆栈的能力，看看我们是否看到了一些 a。现在我们可以问要将什么放入堆栈。
我们这里有一些选择，没有正确或错误的答案。您选择什么将取决于您所依赖的自动机公式以及您的自动机设计目标。是的，自动机的设计方式与真机或计算机程序相同。我们希望做出符合形式主义规则且简单易用的设计选择。一种方法是添加我们稍后期望看到的与我们已经消费的符号相对应的内容；对于我们现在看到的每个 a，我们以后需要看到四个 b；所以我们现在可以将 bbbb 添加到堆栈中，然后为从输入中读取的每个 b 从堆栈中弹出一个 b。这很方便。请注意，当我们读取第一个 a 时，我们可以通过添加 bbbbbb 而不是 bbbb 来处理“+2”要求，只要我们知道何时读取第一个 a - 我们通过检查堆栈知道。
基于所有这些考虑，我们可以为我们一直在设计的 PDA 制作部分 table，然后我们可以评估我们的进度，看看我们还需要去哪里：
q e S q' S'
--- --- --- --- ---
q0 a Z q0 bbbbbbZ
q0 a b q0 bbbbb
我们用Z代表栈底。当我们看到第一个 a（我们知道它是第一个，因为堆栈是空的，即最上面的符号代表堆栈的底部）我们添加 bbbbbb。每个连续的 a 将 bbbb 添加到堆栈的顶部（通过将 b 替换为 bbbbb）。
现在我们必须考虑如何处理b。我们可以通过从 q0 循环到 q0 来处理 a b 吗？片刻的想法应该让你相信这不是一个好主意。如果我们在看到 a b 时从 q0 循环到 q0，那么我们没有简单的设施来防止 PDA 接受更多的 a。但这会导致字符串不可能是我们想要的语言，因为在我们的语言中，a 不能跟在 b 之后。因此，似乎有必要接受 b's 的任何转换，而不是将状态 q0 作为其目标。因此，我们选择 q1 作为所讨论过渡的目标。来源是什么？到目前为止，我们的PDA中只达到了q0，可供选择的只有q0和q1。我们现在有两个选择：要么我们提供一种从 q0 到 q1 的转换机制，而不会看到 a b，要么我们提供一种在 a b 上转换的机制。这些方法中的第一种需要基于我们之前的设计选择的不确定性，因此我们可能更喜欢后者，因为它更明确且更容易推理。这导致以下转换（添加到我们之前的 table）：
q e S q' S'
--- --- --- --- ---
q0 a Z q0 bbbbbbZ
q0 a b q0 bbbbb
q0 b b q1 -
这个转换表示当我们在 q0 中看到一个 b 并且我们之前在堆栈中看到过 a 时，转换到 q1 并丢弃最顶层的堆栈符号。请记住，我们设计堆栈的方式是，对于我们在输入中读取的每个 b，我们应该始终在堆栈中丢弃一个 b。
现在我们已经到达状态 q1，自然要问的问题是这个状态是否应该接受。答案是一定不能，否则我们可以接受一个没有足够 b 的字符串来清除它的堆栈；也就是说，我们会有 j < 4i + 2。所以我们需要一个新状态，称之为 q2，q1 不会接受。我们应该用 q1 做什么？通过添加以下转换，我们可以轻松地使用它来读取剩余的 b 并从堆栈中弹出：
q e S q' S'
--- --- --- --- ---
q0 a Z q0 bbbbbbZ
q0 a b q0 bbbbb
q0 b b q1 -
q1 b b q1 -
只要我们有 b 要读取并且 b 在堆栈上，就可以进行第四次转换。在此过程中可能会发生三件事：
- 我们 运行 出栈中的 b，但输入中仍有 b
- 我们 运行 在完成读取输入中的所有 b 的同时从堆栈中取出 b
- 当输入耗尽时，堆栈中仍有 b
只有第二种情况我们才接受，我们可以通过第四次转换的重复应用来达到第二种情况。但是，q1 不接受。因此，我们将需要一种方法从 q1 过渡到接受状态——我们不妨将 q2 称为这种状态——当我们可能处于这种状态时。如果我们真的处于那个状态，当我们在 q1 中看到一个空堆栈时，我们需要一个 epsilon 转换：
q e S q' S'
--- --- --- --- ---
q0 a Z q0 bbbbbbZ
q0 a b q0 bbbbb
q0 b b q1 -
q1 b b q1 -
q1 - Z q2 Z
现在，在 q2 中，我们可能是情况 1 或情况 2：堆栈是空的，但是我们还有更多符号要读取吗？事实证明这至少没有问题，因为进一步的输入符号将导致 PDA 在状态 q2 中立即崩溃。
第二个留作练习。