问题标签 [pushdown-automaton]

一些编程问题不需要图灵机的全部能力来解决。他们可以用更少的力量来解决。我正在寻找一种功能较弱的编程语言。

是否存在仅限于支持这些功能的高级编程语言：

1. 具有将值压入堆栈和将值从堆栈中弹出的操作的堆栈。

2. 一个有限状态机 (FSM) 用于输入值、从一个状态移动到另一个状态、与堆栈交互并输出结果。

我意识到我可以使用 Java 或 C 或 Python（等）并通过编写仅使用堆栈和 FSM 的程序来限制语言。但是，我正在寻找一种仅具有这些功能的编程语言，仅此而已。

换句话说，我不想使用图灵完备的编程语言来解决只需要确定性下推自动机功能的问题。我想使用一种仅具有确定性下推自动机功能的编程语言。

我在部署阶段从 Visual Studio 收到以下错误消息到移动设备：

唯一有效的解决方案是从Program Files设备上删除整个应用程序文件夹 - 在http://mobileworld.appamundi.com/blogs/petevickers/archive/2010/06/30/vs2008-an-operation-was-attempted-中描述on-something-that-is-not-a-socket.aspx。

任何人都可以提出更好的解决方案，因为删除-重新部署会损害生产力。

细节：

• 视觉工作室 2008 (9.0.30729)
• 设备是运行 Windows Mobile 6.5 的 PDA、PSION EP10
• 正常部署一段时间后突然出现问题

我发现的另一个相关线程没有帮助 - http://social.msdn.microsoft.com/Forums/en-US/windowsmobiledev/thread/18e06e4f-f5b3-4e6f-a5a6-ff2ba26c69d7/

2 堆栈 PDA 和多磁带图灵机的优点是什么？

2 堆栈：可以像图灵机一样工作，使用一个堆栈作为左侧磁带，一个作为右侧磁带可以获取上下文感知数据

2 Tape：分离输入和计算

还有吗？

我想知道是否有人可以简单地解释这两个术语之间的关系，因为我对术语感到非常困惑。

有没有办法将确定性下推自动机转换为图灵机？我想把堆栈放在磁带上输入之后，在它们之间加上“#”。但要正式证明它似乎是不可能的。

你有什么建议吗？有人已经这样做了吗？

谢谢

我正在研究 ac# 正则表达式，它可以匹配嵌套结构（在这种情况下是括号）以及任意运算符（在这种情况下是 '|' 字符）。

我已经开始使用这里描述的下推自动机。

到目前为止我所拥有的：

产生以下结果：

期望的结果：

注意：组之间可能有也可能没有任何运算符。例如，源可能看起来像“((Name1|Name2) Blah) (Name3 (Blah | Blah))”

i have another pda device. android phone and pda are connected to same wireless router. i can read files from pda if i know the filename. Now there is a folder called "reports" on pda. i need to show all files in report folder so user clicks on report generated on pda will open in webview.

Let say i have http://192.168.0.3/reports. I have tried few thing with File class in android that doesnot seem to work.

Please help if you can. Thanks

我想知道是否可以（使用 JAVA）识别用于发出请求的计算机类型，例如：服务器、台式机、PDA（平板电脑、手机等）？

谢谢！

我有许多参考文献，我想用文本中更下方的锚点的链接替换。链接有一个非常规则的形式，所以它应该是非常可行的 - 至少有一个脚本：

引用“[44]”应替换为以下 html 代码：[<a href="ref44">44</a>].

那很容易。使用反向引用进行简单替换。但是是否有一个正则表达式（vim 方言、python 或 ... perl，如果必须的话。太恐怖了！）可以将以下内容转换为类似的链接：[44,45,77,91]？也就是说，每个数字一个链接，其中链接组被一对方括号包围。

由于这涉及（理论上是无界的）内存，它不会与 FSM 1:1 映射，因此应该由某种下推自动机处理，而不是正则表达式，但有些方言更强大，所以 . ..

我不明白 PDA 图中的箭头...

我有一个 PDA，它接受所有带有嵌套的括号的字符串，如((((())))),(())等((()))。它有两个状态，第一个状态有一个循环的箭头，它的行为被描述为(,ε/(。

就我所见，(如果堆栈顶部有 ε，则此描述将接受符号，如果有，ε则将替换为(。

因此，如果堆栈一开始看起来像这样：
ε

现在看起来像这样：
(ε

(即使ε不再位于堆栈顶部，如何让这个循环箭头继续接受每个符号？