0

我正在尝试为 L = {w ∈ {a,b}*| 构建一个 npda n a (w) <= 3*n b (w)}。这意味着对于每个b最多可以有 3 个a。

首先，这是我到目前为止所做的。从开始状态开始，我们将一个“ a ”压入堆栈。（在一天结束时，我们需要看到这个“ a ”才能到达最终状态，如果每个 b 有 3 个以上的 a，我们就会弹出这个“ a ”，并且我们不会到达最终状态状态）。

然后对于字符串上的每个b，我会推动 3 个a。对于输入上的每个a我都会弹出一个“ a ”。

最后，如果堆栈上有一个a，我们就进入最终状态。

点击这里查看 npda 图纸

因此，让我们考虑一个字符串，其中 nb(w)= 1 和 na(w) = 3。我们可以有排序为 baaa、aaab、abaa、aaba 的字符串。（还有其他的）

如果我们要为 baaa 运行 npda。这会很好。

什么都不读（lambda）我们推一个. 然后我们读b，然后按aaa。堆栈内容为 (aaaa)。然后我们读取 a 并弹出一个 a。我们这样做 3 次，堆栈变为 (a)。读取字符串后，堆栈上有一个左侧，所以我们可以进入最终状态。

问题在于，这种结构仅在b在a出现在字符串上之前首先向堆栈提供 3 个 a时才有效。如果我们在字符串 aaab 上运行 npda，这将不再有效。我们将在堆栈上有一个 a ，读取第一个a我们必须弹出一个a。读第二个，没有什么可以做的操作。堆栈上没有任何东西，我们不能压入a，因为那会搞砸一切。

我该如何修复这种结构，或者该语言是否有更好的 npda 结构。

我已经为此工作了好几天。帮助将不胜感激。

也知道我对 npda 很陌生，所以可能是我在做一些根本错误的事情。所以，解释清楚。

谢谢

4

2 回答 2

1

好的，这里有一个提示。到目前为止，您的解决方案基本上只是使用堆栈作为计数器，在扫描字符串时计算值 3*nb(w) - na(w)，使用堆栈深度作为计数器的值。在“b”上加 3，在“a”上减 1。基本上，一个很好的解决方案。

问题是，这只有在计数器永远不会变为负数时才有效。为了使它适用于所有情况，您需要一种方法让您的计数器记录一个负数。考虑一种可以将堆栈用作计数器的方法，该计数器可以轻松记录正数或负数，并告诉您最终值是否> = 0...

于 2016-11-13T04:10:34.000 回答
1

不确定我能否给你确切的答案，因为我很确定我们在同一个 335 班。哈哈。

主要问题是您没有考虑所有可能性。

初始状态在其循环中有 14 种可能性，它可以分支成 2 个返回初始状态的分支。在看到堆栈符号结束时，它也会转换到最终状态。

除了提到的那些之外，所有这些都是在初始状态的循环中完成的。

看到一个：

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.

如果我有另一种沟通方式，我可能会提供更多帮助。

于 2016-11-13T03:47:59.027 回答