问题标签 [pushdown-automaton]

我的朋友问我一个关于下推自动机的问题。蕉麻。我正在研究一些类似的问题，但所有问题都包含偶数，就像 0^a 1^a 但现在我有 3 个值。我找到了一个例子，但我无法将我的问题转换为这个。

我怎样才能转换蕉麻？

我正在阅读有关如何实现 DPDA 并在以下 Internet 地址中找到此代码：http ://code.zhoubot.com/ ，此 c 文件实现了一个简单的下推自动机。自动机将读入它们的转换函数和输入的描述，对输入执行计算，然后打印它们的输出。

输入格式如：e01:e0$:000111:a:ad:aeeb$:b0eb0:b10ce:c10ce:ce$de 输入用分号“:”隔开，第一部分是“输入字母”，第二部分是“堆栈字母表”，然后是“输入”和最后一整串是转换函数。

尝试编译时，编译器告诉我以下错误：

由于我试图理解代码，我该如何解决这个错误？

明天考试，教授让我们知道一个问题:)。

在该图的上下文中，L 是 epsilon（空字符串），Z0 是堆栈空符号。

我在确定有关该语言生成的单词的一些规则方面取得了一些进展，但无法确定整个语言。

谢谢！

我编写了以下程序来检查字符串是否平衡括号：

以下是一些示例数据：

由于这个程序只使用了最基本的显式递归构建块，我想知道是否有一种更短、更高级的方法涉及我还不知道的语言设施。

好的，我从几个答案和评论（以及我自己的想法）中提炼出以下解决方案：

我试图弄清楚如何推断 PDA 识别的语言，并且感觉我很接近，但我仍然错过了。以下面的 PDA 为例。我可以制作一个转换图来弄清楚我的增量（转换）是什么，但我从那里开始迷失了。这不是家庭作业，只是书中的一个例子。这是问题和转换表：

我将如何为 0^m 1^n 编写一个 pda，其中 |m| >= |n|; 0 的个数是否大于或等于 1 的个数？

我在想：

• 如果看到 1 或 0，将其压入堆栈
• 如果你看到另一个 0 或一堆 0，将其压入堆栈
• 如果你看到一个 1，把它压入堆栈
• 如果您在那之后看到另一个 1，则将其从堆栈中弹出

但是，我认为这是不对的。有人可以帮忙吗？

PDA接受哪些类型的语言，其中堆栈大小限制为 20 个项目？

在我看来，它仍然应该是CFL，因为有一个临时内存要存储。

我正在为我的考试自动机和正式语言学习，我必须设计一个识别语言的 PDA：

一个 ^ib ^2i 使得 i>= 1

我认为解决方案是：

从磁带上读取的每个“a”我堆叠两个 X 然后，如果我在磁带上得到一个“b”并且我在堆栈顶部有一个 X，我从堆栈中弹出一个 X，最后，如果我读到空磁带，我有 Zo（堆栈标记的底部），字符串被接受。我的问题是：我可以在一个计算步骤中堆叠两个连续的 X 吗？

我正在为我的考试自动机和正式语言学习，我必须设计一个识别语言的 PDA：

我有一个小想法，但我坚持这一点：

首先想到处理所有的“a”，每个“a”推一个“A”

所以我想到了解决方案，但我认为是不正确的，我做错了什么？

我需要将生成的 CFG 写入以下自动机。

我知道这样的过渡：

es 代表空字符串。

但我不知道如何处理像“c，a; a”这样的规则。任何人都可以给我任何帮助吗？谢谢你。

http://tonguim.free.fr/divers/automata.jpg