npda 为语言数量a的小于等于b的数量的3倍
npda for the language number a's less than or equal to 3 times the number of b's
我正在尝试为 L = {w ∈ {a,b}*| 构造一个 npda na(w) <= 3*nb(w)}。
这意味着对于每个 b 最多可以有 3 个 a。
首先，这是我到目前为止所做的。
从开始状态开始，我们将单个“a”压入堆栈。 （归根结底，我们需要看到这个“a”才能达到最终状态，如果每个 b 有超过 3 个 a，我们就会弹出这个“ a”，我们不会达到最终状态。
然后对于字符串上的每个 b，我将推 3 a。对于输入中的每个 a，我都会弹出一个“a”。
最后，如果堆栈上有 a，我们将进入最终状态。
Click here for the npda drawing
所以让我们考虑一个字符串，其中 nb(w)= 1 且 na(w) = 3。
我们可以有 baaa、aaab、abaa、aaba 这样的字符串。 （还有其他的）
如果我们要 运行 baaa 的 npda。这会很好用。
什么都不读 (lambda) 我们推送 a。然后我们读取 b，然后推送 aaa。堆栈内容是（aaaa）。然后我们读取 a 并弹出一个 a。我们这样做 3 次，堆栈变为 (a)。读取字符串后，堆栈中有一个 a 左边，所以我们可以进入最终状态。
问题是只有当 b 在 a 显示之前首先向堆栈提供过量的 3 a 时，此构造才有效在弦上。如果我们 运行 字符串 aaab 上的 npda，这将不再有效。我们将在堆栈上有单个 a，读取第一个 a 我们将不得不弹出一个 a。读第二个a，没有可以做的操作。堆栈上没有任何东西，我们不能压入 a 因为那会把一切都搞砸。
我该如何修复这个结构，或者是否有更好的语言 npda 结构。
我已经为此工作了好几天。帮助将不胜感激。
还知道我是 npda 的新手，所以可能是我做的事情从根本上是错误的。所以，在解释中要清楚。
谢谢
不确定我能否给你我的确切答案，因为我很确定我们在同一个 335 class。哈哈
主要问题是您没有考虑到所有可能性。
初始状态在其循环中有 14 种可能性，它可以分支成 2 个分支 return 到初始状态。在看到堆栈符号结束时，它也会转换到最终状态。
除了注明的以外，所有这些都是在初始状态的循环中完成的。
看到一个：
a input:
Push a onto the stack
b input:
You can pop it or replace it with 1 or 2 b's
Or
You can pop one b
Or
You can pop 2 or 3 b's (Done by branching into 2 different branches of
states that do just that, respectively, and return to the initial state)
看到b:
a input:
Pop b (Only way to meet criteria for final state)
b input:
Push 0 to 3 b's
看到堆栈符号结束时：
empty string input:
Go to final state.
如果我有其他沟通方式，我可能会提供更多帮助。
好的，这是一个提示。到目前为止，您的解决方案基本上只是使用堆栈作为计数器，在扫描字符串时计算值 3*nb(w) - na(w)，使用堆栈深度作为计数器的值。在 "b" 上加 3，在 "a" 上减一。基本上，一个很好的解决方案。
问题是，这只有在计数器永远不会变为负值时才有效。为了使其适用于所有情况，您需要一种让计数器记录负数的方法。想一想你可以使用堆栈作为计数器的方式，它可以很容易地记录正数或负数，并告诉你最后的最终值是否 >= 0...
我正在尝试为 L = {w ∈ {a,b}*| 构造一个 npda na(w) <= 3*nb(w)}。 这意味着对于每个 b 最多可以有 3 个 a。
首先，这是我到目前为止所做的。 从开始状态开始，我们将单个“a”压入堆栈。 （归根结底，我们需要看到这个“a”才能达到最终状态，如果每个 b 有超过 3 个 a，我们就会弹出这个“ a”，我们不会达到最终状态。
然后对于字符串上的每个 b，我将推 3 a。对于输入中的每个 a，我都会弹出一个“a”。
最后，如果堆栈上有 a，我们将进入最终状态。
Click here for the npda drawing
所以让我们考虑一个字符串，其中 nb(w)= 1 且 na(w) = 3。 我们可以有 baaa、aaab、abaa、aaba 这样的字符串。 （还有其他的）
如果我们要 运行 baaa 的 npda。这会很好用。
什么都不读 (lambda) 我们推送 a。然后我们读取 b，然后推送 aaa。堆栈内容是（aaaa）。然后我们读取 a 并弹出一个 a。我们这样做 3 次，堆栈变为 (a)。读取字符串后，堆栈中有一个 a 左边，所以我们可以进入最终状态。
问题是只有当 b 在 a 显示之前首先向堆栈提供过量的 3 a 时，此构造才有效在弦上。如果我们 运行 字符串 aaab 上的 npda，这将不再有效。我们将在堆栈上有单个 a，读取第一个 a 我们将不得不弹出一个 a。读第二个a，没有可以做的操作。堆栈上没有任何东西，我们不能压入 a 因为那会把一切都搞砸。
我该如何修复这个结构，或者是否有更好的语言 npda 结构。
我已经为此工作了好几天。帮助将不胜感激。
还知道我是 npda 的新手，所以可能是我做的事情从根本上是错误的。所以，在解释中要清楚。
谢谢
不确定我能否给你我的确切答案，因为我很确定我们在同一个 335 class。哈哈
主要问题是您没有考虑到所有可能性。
初始状态在其循环中有 14 种可能性，它可以分支成 2 个分支 return 到初始状态。在看到堆栈符号结束时，它也会转换到最终状态。
除了注明的以外，所有这些都是在初始状态的循环中完成的。
看到一个：
a input:
Push a onto the stack
b input:
You can pop it or replace it with 1 or 2 b's
Or
You can pop one b
Or
You can pop 2 or 3 b's (Done by branching into 2 different branches of
states that do just that, respectively, and return to the initial state)
看到b:
a input:
Pop b (Only way to meet criteria for final state)
b input:
Push 0 to 3 b's
看到堆栈符号结束时：
empty string input:
Go to final state.
如果我有其他沟通方式，我可能会提供更多帮助。
好的，这是一个提示。到目前为止，您的解决方案基本上只是使用堆栈作为计数器，在扫描字符串时计算值 3*nb(w) - na(w)，使用堆栈深度作为计数器的值。在 "b" 上加 3，在 "a" 上减一。基本上，一个很好的解决方案。
问题是，这只有在计数器永远不会变为负值时才有效。为了使其适用于所有情况，您需要一种让计数器记录负数的方法。想一想你可以使用堆栈作为计数器的方式，它可以很容易地记录正数或负数，并告诉你最后的最终值是否 >= 0...