问题标签 [pushdown-automaton]

{0 ⁱ 1 ^j 2 ^k | 0 <= i <= j <= k }

是否可以为这种语言设计 PDA？

我认为答案是否定的，它只能使用至少一个上下文无关语法来定义。

但是，我不知道为什么。我需要对此进行一些讨论和解释。

最近我遇到了先查找并关注的问题

在这里，我对 A 中的第一个感到困惑，其中一个是正确的 {a} ， {empty,a} 因为在 A 的生产中存在左递归。我很困惑是否在 A 的第一个中包含空字符串 任何帮助将不胜感激。-------------编辑---------------

什么将是第一个和后面的，这是我见过的如此令人困惑的语法

我需要使用解析表证明此语法不在 LL(1) 中，但由于我没有在单个单元格中获得 2 个条目而无法做到。

我正在使用带有 Windows 嵌入式句柄（基于 windows mobile 6.5）的 Pidion BP 6000 PDA 大部分系统语言是韩语，一些是英语。怎么把系统语言改成英文？

p/s：奇怪的是，查看系统信息->软件->语言，上面写着“英语”，但整个系统都是韩语专业的。

谢谢

我正在做一个项目，该项目需要我比较两个 PDA 以检查它们是否接受相同的语言。我已将这些 PDA 转换为相应的上下文无关语言，但我不知道如何进一步进行。

因此，我正在为一项关于下推自动机和无上下文语言的测试而学习，我被困在这个结构上。

除了我将在下面解释的一部分外，我让这个自动机的每一部分都完美地工作。

它需要识别的语言是：{ x#y#z#w | x, y, z, w in {0, 1}+ 其中 x ≠ w 和 y ≠ z }。

所以我遇到的问题是将 Xi 与 Wi 进行比较，因为在自动机处理 W 时，Wi 的元素是未知的，就像我设计的那样。

如果我存储 X 的内容，当需要弹出并将每个元素与 W 的元素进行比较时，它们将以相反的顺序弹出，因此认为 000111 和 111000 是相同的字符串，PDA 会拒绝，什么时候应该明确接受（它们是不同的字符串）。这只是一个例子，这也会导致其他输入被错误地分析。

如果有办法将 X 的内容以相反的顺序推入堆栈，它们将以原始形式弹出，使我能够正确比较字符串的内容。

如果有办法在正常推送后反转堆栈的内容，这也将使我得出解决方案。

任何帮助将不胜感激。谢谢。

我正在尝试编写一个接受 a^2n b^n, n>0 的 pda 下推自动机，但我不确定最后一部分是否正确

http://wiki.apidesign.org/wiki/Impossible

我看了一下这个，我不明白为什么这个问题似乎是不可能的。给“机器”的字符串总是有限的吧？

因此，即使我有 10 亿个零和 10 亿个零，也可以轻松编写一个脚本，为该字符串返回 true 或 false（它将是 true/接受）。

另一个输入可能是“00011”，这使其无效。

我可能在这里不明白什么，但这个问题对我来说似乎是“可编码的”。

我正在尝试将以下 CFG 转换为下推自动机：

我不太确定如何解决这个问题，或者一般来说 CFG->PDA 的问题。

我在处理以下问题时遇到问题。

给出以下语言的上下文无关文法：

解决这个问题的最佳方法是什么？目前我只是用直觉来解决这些问题，但有没有有用的技术？即你能想到这种语言的 PDA 会是什么样子，然后从中推导出语法吗？有没有使用语法 A 和 B 找到语法 G = A 和 B 的方法？

我正在努力寻找如何解决这个问题，所以任何帮助都将不胜感激。

谢谢。

这曾经是一个家庭作业，但我现在将它用于修订目的；但是这个问题没有解决方案。任何建议将不胜感激。

问题是：“假设 k-PDA 是一个可以访问 k 个堆栈的下推自动机。1-PDA 是标准 PDA，您已经看到 2-PDA 可以识别任何图灵可识别的语言。证明，对于任何k ≥ 0，任何被识别为 k-PDA 的语言都是图灵可识别的。”

直接复制粘贴，有大神帮忙解决下这个问题吗？另外，我觉得这写得不正确，但我不确定什么是正确的。