1

在此处输入图像描述

为了绘制接受 L 的 NPDA 的转换图，我认为可以通过读取 an a，写入 an a，然后向右移动，然后做同样的事情来开始这个问题，b以便有一些状态 q 1得到那些“ab”动作。但那怎么可能得到bb呢n-1？

我有一些我认为可行的东西，但我正在自学，所以也许有人可以告诉我在哪里n可以n-1正确完成。

编辑：

但现在应该是——

在此处输入图像描述

4

1 回答 1

1

其实很简单。每次读取“ab”时，都会在堆栈中存储一个标记。然后在阅读“c”之后，您从该令牌中取出一个。然后对于每个“bb”，您从堆栈中取出一个标记。当堆栈为空时，您接受。

对于 NPDA 本身，这取决于您如何定义接受度。a从您的问题中，我不明白“写一个，然后向右移动”是什么意思。您是否将 NPDA 与图灵机混淆了？NPDA 与 NFA（非确定性有限自动机）非常相似，只是它配备了一个堆栈，您可以在其中放置堆栈符号。在此处阅读更多信息：http ://www.cs.duke.edu/~rodger/courses/cps140/lects/sectnpdaH.pdf

下面是转换表，假设堆栈符号{A,Z}在哪里Z是初始堆栈符号。当我们处于唯一的接受状态 q a并且我们已经完成读取输入磁带时接受。假设每次转换总是消耗一个堆栈符号，并且如果在 NPDA 不处于接受状态时没有更多符号要消耗，则 NPDA 不会接受（或拒绝）该字符串。

在下表中，第一列代表我们当前所处的状态以及我们正在读取的堆栈符号。后续列表示在读取输入字符串中的特定字符（或根本不使用 ε 读取任何字符）时推入堆栈的新状态和堆栈符号

+--------++---------+--------+--------+--------+
| || 一个 | 乙 | c | ε |
+--------++---------+--------+--------+--------+
|(q 1 ,Z)|| (q 2 ,Z) | - | - | - |
+--------++---------+--------+--------+--------+
|(q 1 ,A)|| (q 2 ,A) | - | (q 3 ,ε) | - |
+--------++---------+--------+--------+--------+
|(q 2 ,Z)|| - |(q 1 ,ZA) | - | - |
+--------++---------+--------+--------+--------+
|(q 2 ,A)|| - |(q 1 ,AA) | - | - |
+--------++---------+--------+--------+--------+
|(q 3 ,Z)|| - | - | - |(q a ,ε) |
+--------++---------+--------+--------+--------+
|(q 3 ,A)|| - | (q 4 ,A) | - | - |
+--------++---------+--------+--------+--------+
|(q 4 ,A)|| - | (q 3 ,ε) | - | - |
+--------++---------+--------+--------+--------+

这里的关键思想是堆栈中 A 的数量表示短语“ab”在输入字符串中出现的次数。

您可以看到，在使用堆栈符号 Z 读取状态 q 1中的“a”时，我们将 Z 推回堆栈。这意味着仍然没有检测到“ab”。然后它将转到 q 2。

在 q 2中，我们只接受“b”，任何其他输入都会导致它挂起（并因此拒绝）。它将读入的状态推回堆栈，加上一个额外的 A，有效地将堆栈中的 A 数量增加 1，因为此转换表示输入字符串中的附加短语“ab”。

状态q 3表示成功读取“c”后的部分。请注意，从 q 1到 q 3的转换必须消耗 A，而不是 Z，因为我们有约束n >= 1。然后，在读取“b”时，它将进入状态 q 4以等待另一个“b”。稍后 q 4，在读取“b”时，将消耗堆栈符号 A，匹配

在状态 q 3我们还希望在到达堆栈符号 Z 后转换到接受状态 q a，指的是存在n“ab”n-1副本和“bb”副本的状态。

状态 q 4只接受带有堆栈符号 A 的输入字符串“b”，表示找到一个新短语“bb”应该匹配之前找到的一个短语“ab”。

希望这可以帮助！

于 2013-11-28T03:11:15.450 回答