0

我将如何为 0^m 1^n 编写一个 pda，其中 |m| >= |n|; 0 的个数是否大于或等于 1 的个数？

我在想：

  • 如果看到 1 或 0，将其压入堆栈
  • 如果你看到另一个 0 或一堆 0，将其压入堆栈
  • 如果你看到一个 1，把它压入堆栈
  • 如果您在那之后看到另一个 1，则将其从堆栈中弹出

但是，我认为这是不对的。有人可以帮忙吗？

4

2 回答 2

2

考虑当你有相同数量的 0 和 1 的情况。

让我们轻松开始吧。您可以从 1 开始，也可以从 0 开始。这为我们提供了两种不同语言的联合，其中 0 的数量大于 1 的数量，反之亦然。

因此，空字符串也是有效的（这提供了第一个状态将是最终状态的线索）。

接下来，我们观察到我们最终可以有相同数量的 0 和 1 上下移动。

考虑字符串：

010101 或 101010。你注意到它总是回到空堆栈。这很容易处理。

基本上你有一个 PDA，其中 start start 也是接受状态。

我不确定你是否知道这个符号，所以我只是用简单的英文写下来。

你有 3 个状态，q0，q1，q2。

q0 是最终和初始的起始状态。

q0 -> q1 有 1 个转换 1，e -> $（读取一个 1，为空堆栈压入一个 $ 符号）。

q1 有一个 0, 1 -> e 和 1,e,1 的自循环（如果您读取 0，则弹出 1），（如果您读取 1，则推送 1）。

还有一个回到起始状态 q0 的转换。

q1 -> q0 0, $ -> e（读取一个 0，堆栈现在是空的）此时我们有相同数量的 0 和 1。

您对状态 q2 执行此操作，但推送和弹出 0 除外。所以一切都与 1 和 0 正好相反。

然后，您可以不确定地拥有任意数量的 0，我将由您决定。提示：您可以在某处创建 1 个自循环来处理此问题。实际上，您只需添加 1 个状态即可获得等于或大于 0 到 1 的数量

======================

因此，在简单的英语中，您需要考虑首先以 1 或 0 开头的两种情况。然后，如果您再次以空堆栈结束，请返回初始/最终状态并查看您是否再次获得 1 或 0。

例子：

10010011

先读一读。然后你读到一个 0，所以就像你从头开始一样，这次是字符串：

010011

这次读一个 0，读一个 1，从头开始：

0011

读取 0，读取 0，压入 0，读取 1，弹出 0，读取另一个 1（堆栈现在为空），返回初始/最终状态。

希望有帮助。

于 2011-11-13T06:07:33.497 回答
1

如果我正确理解了分配，那么您正在使这种方式变得复杂。0^m 1^n 表示一堆 0 后面跟着一堆 1，但是在你看到 1 之后没有合法的字符串为 0。首先你在堆栈上放一个符号，这样你就知道它什么时候是空的（通常这 ＃）。之后，您基本上需要计算 0（将它们推入堆栈），当您看到 1 时，从堆栈中弹出。输入完成后，您检查堆栈是否有任何 0 或您在开始时放入堆栈的符号。

于 2011-11-13T18:54:12.437 回答