问题标签 [pushdown-automaton]

我必须构建这个 PDA，但我对如何跟踪字符串索引 xi 和 yi 感到困惑？提前致谢

构造一个接受 { x#y | 的 PDA x, y in {0, 1}* 使得 x ≠ y 和 xi = yi 对于某些 i, 1 ≤ i ≤ min(|x|, |y|) }。

我正在使用 C#

我希望能够在我的正则表达式语言中调用特定字符的函数，并且想知道这是否可能。例如，如果我有我的模式，因为^[0-9]*$我想在foo()找到 7 时调用该函数。因此，如果我有字符串"0129384927377"，它将调用该函数foo三次。

有什么办法吗？

如果您需要上下文，我正在尝试尽可能简单地构建DPDA（确定性下推自动机），但不确定最好的方法。

A PDA (Pushdown Automaton) is said to be k-turn if, for any string w in its language, turn the direction of its stack at most for k times. Also it is well-known that the language L is linear iff accepted by a 1-turn PDA. Now, is it true that the regular languages are the languages which are accepted by a 0-turn PDA?

{WW} - 可判定但不是上下文无关
{WW^R} - 上下文无关，但不是正则
Σ* - 正则语言
你如何确定它们属于哪个类？

我相信这种语言不是上下文无关的，因为 PDA 不可能比较 2 个相同长度的 0 和 1 块并记住它的长度以供以后使用。

不幸的是，我不知道如何证明这一点。

我尝试使用抽水引理无济于事......

我还试图通过矛盾假设该语言是上下文无关的，并使用上下文无关语言与常规语言的交集也是上下文无关的事实（通过找到一些神秘的常规语言 L），并且令人惊讶地（或不是） - 我所有的努力都是徒劳的......

任何帮助，将不胜感激

虽然这是对此的重复，但我是在设计 PDA 方面进行讨论。

现在，我知道我错了，因为这是一个广为人知的例子，但我在下面的 PDA 设计中哪里出错了？

我想接受语言{a^n b^n c^n: n>=0}

1每次遇到一个a, 弹出一个 forb并弹出一个 for时，我都会在堆栈上压入两个，c并检查我是否有一个空堆栈。我将转换函数（最小）定义为：

(q0, a, Z) = (q0, 11Z)
(q0, a, 1) = (q0, 111)
(q0, b, 1) = (q1, delta)
(q1, c, 1) = (q2, delta)
(q2, delta, Z) = (q-Final, Z) (epsilon move)

Z is empty stack

这个PDA不接受这样的语言吗？

我最近被设置了一个任务来创建一个基于我之前创建的有限自动机的下推自动机。（我实际上并没有成功，这就是为什么我的导师给了我一份工作副本）

我无法理解两个图中都包含的部分。

“”第一个是当箭头与一个状态连接但只是指向它时，它的确切含义是什么，我是否认为这是检查预先输入的语言（在我的情况下为 0-9）是否正确（此箭头指向终端状态）""

我已经尝试过进行研究，但不幸的是，我没有想出任何可以用基本术语真正向我解释的东西，我什至尝试过“傻瓜有限自动机”，但仍然没有！我还检查了可能有我的答案但没有的问题。

如何在.Net上开发CASIO DTX30的应用程序？

As per the question, can a pushdown automata have zero final states?

如何编写可以对任何确定性下推自动机 (DPDA) 建模的程序 用户应输入状态数、转换函数、输入符号 程序应为请求的 pda 建模并测试用户输入的随机字符串的接受或拒绝

这是我到目前为止在 C++ 中所做的 - 我已经收集了状态、输入符号和输入符号的数量 - 我在转换函数上，但似乎无法更进一步，因为我无法概念化 DPDA 建模