问题标签 [pushdown-automaton]

我很确定我确实有一个，但它有 42 条构造规则并且不能很好地概括。我怎样才能用更少的构造规则来做到这一点？

语言是 {a,b}*，其中 a 的数量是 b 的数量的五倍。

我知道对于一种语言 {a^n (concatenate) b^m; m = 5n} 它只是

S = aSbbbbb | λ

但是当角色可以按任何顺序排列时，我就迷路了。

有什么东西比有限自动机更强大，但比确定性下推自动机更弱？

制作 PDA 以识别以下语言：a 多于 b 的字符串语言

我已经为这个问题苦苦挣扎了好几天了，我似乎已经完全陷入了精神障碍。任何人都可以为我如何解决这个问题提供一些指导或指导吗？

我有一个引理问题，我完全坚持...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

是不是节能灯？

我要求它不是 CFL，因为只有一个堆栈来记住所有这些条件是不够的。你可以记住 na (w) < nb (w) 或 na (w)< nc (w),nb (w) < nc (w) 但不是 na (w) < nb (w) < nc (w)。另外，我认为如果语言是 a^pb^2pc^3p 而不是我打气 |vy| p 次 L 不是 CF 但是你有可能抽 p 次吗？

或者对解决方案有什么想法？

我正在寻找一些有限自动机、下推自动机和图灵机任务示例的良好来源（用于手动解决）。

我四处寻找，但没有发现什么特别的东西，所以我想知道是否有人有一些很好的例子。提前致谢。

给出一个上下文无关的语法

{ w | w是 {a, b, c, d}* 的元素，使得 # of a+ # of b = # of c + # of D}

我该如何处理这个问题......？

假设我们有上下文无关语言 L={0^n0^n, n>=0}。

对于 PDA：Μ = {A, Q, H, δ, q0, h0, F} 我们有：

这是我的解决方案，但它有一个问题。自动机必须接受诸如 00、ε、0000 之类的字符串，而不接受 0 或 000。通常接受具有偶数个 0 的字符串。

让我们尝试 2 个示例：

不应接受最后一个字符串。我不知道如何在识别字符串之前检查弹出次数以选择是否接受它。有没有人有任何想法，有什么线索可以触发我？

我必须为具有完美嵌套的括号和括号的语法制作一个 CFG 和 PDA。

不确定这是否正确，或者如何从中制作 PDA？

我将如何设计一个接受平衡括号和括号的 PDA，例如 ([][])，我很难开始。我需要帮助为这个问题编写转换函数。任何帮助表示赞赏

我正在做一个理论作业，这个问题真的让我思考。问题是：证明任何下推自动机都可以由队列自动机模拟。现在，最初我认为这很简单，但后来我想到了 L = {WW^R | W = {a, b}*} （W^R 是 W 的倒数）这很容易以下推自动机的一般形式创建，但我想不出任何方法以一般形式队列自动机。我不认为我们可以为此设计一个（有限的）一般情况。我可能也想多了，因为我可能只是误解了模拟的含义。无论如何，我比问题更可能是错误的，但是对于我提到的情况，它是如何工作的？

感谢您提供的任何帮助！