将 CFG 转换为 NDPA 的规则？

Question

我必须使用这个语法来定义一个 FA:

S -> aSb
S -> c
S -> dA
A -> Sd

如何管理第一条规则和最后一条规则？ 对于第二个，我认为我必须创建另一个状态（最后一个）和 link S 以及这个新状态。对于第三个，我想我必须通过传递 "d".

来创建状态 "A" 和 link 到 S

Answer 1

您可以使用一些算法从 CFG 获取 PDA：例如，查看自上而下和自下而上的解析器。我认为 PDA 接受 CFG 生成的语言，反之亦然的通常证明，使用了这样的结构。

另一种方法是理解语法生成的语言，并直接为其设计PDA。这不太机械，但有可能产生更简洁的 PDA。如果你想走这条路，我们可以首先通过识别非终结符 A 可以安全地用它唯一产生式的 RHS 替换来简化语法：

S -> aSb
S -> c
S -> dSd    // removed A -> Sd and replaced here

这个语法是如何工作的？

1. 你在第二个生产的中间有 c;
2. 您在 c;
的左侧和右侧有匹配的 d
3. 您的左侧 a 匹配 c 右侧的 b。

PDA 应按如下方式工作：

1. 阅读 a 和 d，直到您看到 c。边走边推堆栈上的所有内容。当你看到 c 时，转到下一个状态，但不要推 c.
2. 读取 bs 和 ds，从堆栈中弹出 as 和 ds，直到：
   • 栈顶符号与输入不匹配；崩溃。
   • 您 运行 输入结束，符号仍在堆栈中；崩溃。
   • 您 运行 堆栈符号用尽，剩余输入；崩溃。
   • 你运行出栈同时输入；接受。

这是一个过渡 table:

q    s      x    q'   s'
------------------------------
q0   a,d,Z  a    q0   aa,ad,aZ
q0   a,d,Z  d    q0   da,dd,dZ
q0   a,d,Z  c    q1   a,d,Z
q1   a      b    q1   -
q1   d      d    q1   -

如果我们在 q1 中接受空栈，这些转换就足够了。如果我们想通过空堆栈或接受状态接受，我们可以添加一个像 f(q1, Z, -) = (q2, Z) 这样的转换并使 q2 接受； PDA 会不确定地过渡到那里并会崩溃，除非输入也用完了。