问题标签 [pushdown-automaton]

从关于 PDA 的 Wiki 文章的这一部分，我大致了解了从给定 CFG 构建 PDA 的过程。本文没有说明的是，当单个 non-terminal 有多个生产规则时所需的步骤。

例如，假设我们有一个形式为 的语法：

显然，这个语法可以识别所有x(ab)*y形式的字符串[巧合的是，它也是一种常规语言]。

在这里，由于这两条规则，我在从这个语法构建 PDA 时遇到了问题

也就是说，在扩展阶段使用这两条规则中的哪一条，同时向下推入堆栈？

我被困在一个PDA问题上。问题如下：

求以下语言的下推自动机： L={xcy : x, y ∈ (a+b)*, y is not the reverse of x, c is literal}

我已经构建了以下机器：http: //i.imgur.com/EPeofGA.jpg

我的机器不接受xc形式的字符串（其中 y 是空字符串），或xcy 形式的任何字符串，|y| < |x|, y 不是 x 的反转。

当输入结束时，我需要让机器从 q1 转换到 q2 ，但堆栈不是空的......但是添加从 q1 到 q2 的空输入转换会导致我的机器接受所有形式的字符串xcy，无论是否y 是 x 的反转。

任何见解都值得赞赏。

我记得如何对 FSM 进行正式描述，但是为 PDA 进行描述看起来有点不同。任何人都可以帮助解释圈出的部分吗？我通常会记好笔记，但似乎在我的笔记本或其他任何地方都找不到关于此的任何内容。任何帮助表示赞赏。

我知道如何弄清楚开始状态、接受状态、输入字母表以及所有这些东西。但是你如何开发PDA的过渡关系呢？对于 FSM，(q0,a),q1) 意味着如果您从 q0 开始并获得 a，则您过渡到 q1。但是 (S,a,e),(S,a) 是什么意思？（S 是开始状态，e 是 epsilon）

我的老师对 PDA 使用了奇怪的格式，有人可以向我解释这个符号吗

转换函数如下：

[q,a,λ, s,B]

[s,a,λ,s,λ]

[s,b,B,s,λ]

任何人都可以解释这个转换函数符号吗？

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

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

编辑：

但现在应该是——

如何将下一个 CFG 转换为 PDA？

假设我们要绘制具有接受该语言 L 的 NPDA 的两个状态的转换图。并且我们还假设这个 NPDA 将有两个状态。我对此的想法是在第一个状态下做所有事情，然后使用第二个状态作为压轴。像这样：

但是我不确定 lambda 转换是否会导致q1或者是否有更好的方法来做到这一点，这可能是一种更好的方法，因为我正试图自学这一点。也许有人可以让我回到正轨？

我刚刚了解到，Regular Grammars有它们对应Finite State Acceptors的将对应Regular Expressions。

是否有等效的转换Context Free Grammars？据我所知，上下文无关语法可以用Push Down Automatawhich 来表示，而后者又对应于什么？

感谢任何能让我摆脱这种想法的人。

假设我们有以下 PDA：M=<Q, {0,1},{X,$},transition,q0, $, F>

我的解决方案是L(P)={w ϵ (0,1)* / 1^n 0 1^n 0 }......但还有另一个是1^n 0 1^n

哪个是最佳的？...考虑到两者之间的唯一区别是清除 PDA 的第一个输入，即 $

谢谢