问题标签 [pushdown-automaton]

在为我的期末考试练习时，我在J. Hopcroft、R. Motwani、J. Ullman 的 Automata Theory, Language and Computation中发现了这个问题，第 222 页。

PDA 应该接受其中 1 的数量是 0 数量的两倍的字符串，如果我没有误解这个问题，那么该字符串可以有不同的 0 和 1 序列，没有特定的模式或特定的顺序。

我解决这个问题的第一个方法是将问题分成两部分

1. PDA 用于以 0 开头的字符串。（例如 - 010111）
2. PDA 用于以 1 开头的字符串。（例如 - 110101）

但是划分问题似乎并没有降低问题的复杂性。

解决此类问题的方法应该是什么？

在人类语言中：由 'c's 分隔的单词列表（由 'a's 和 'b's 构成）并且在某个索引 i 中至少存在一个单词，其中包含更多字母 'a' 然后索引 i+2 中的单词

在我的 WinCE PDA 应用程序中，我正在将扫描的条形码值与数据库中的条形码值进行比较以生成一个表格。

我像这样构建查询：

并在这里使用它：

我已经构建了一个基于类的下推自动机有限状态机。上下文类（其内部状态正在被修改的类）具有一些只有状态才能访问的方法（增加/减少一些迭代器、推送/弹出状态、设置接受状态等）。现在它们是公开的，因为不同的州需要访问它们。

使方法受保护/私有并将状态定义为上下文的朋友会更好吗？

（nb4“基于意见！”）

假设我们有这个 PA：

-> q0 (e, e -> $) --> q1

在哪里：

q0是最终和初始状态； e是ε（空）；q1 是另一个状态。

如果自动机要读取这个e词，它可以转换到 q1 或停止在 q0。

那么，这个 PA 会是非确定性的吗？

我的老师说不会，因为实际上，自动机只有一条路径可以遵循：由于单词是空的，并且所有符号都已在 q0 中消耗掉，因此它不会进行任何转换；但是，我们不确定他是否正确（顺便说一句，他说，为了让 PA 识别一个单词，它不仅需要处于最终状态，而且还必须消耗掉该单词的所有符号）。

我正在尝试构建一个 PDA 或 CFG 来接受 E 是最常见字母的所有单词。例如，Cheese and tee 将使用该语言。我很确定这种语言是上下文无关的，但我似乎无法为它构建一个 PDA。这可能吗？

我想弄清楚如何在下推自动机中做算术表达式？（PDA）例如 L=W|W=An Bm Cn-m 我想做的是先推 As 然后 pop Bs 然后再 pop As with C 或 Bs 与 C 取决于剩下的内容。例如 aaabbc（推 aaa 然后用 Bs bba 弹出，然后用 C 弹出 A 或用 C 弹出 B，这取决于哪个更大。

我认为我的结构知识缺乏。我收到错误，例如：

1. pda.c:33:26: 错误: 'top' undeclared (first use in this function)
   if(pda.stack[top] == '\0')
2. pda.c:54:7: error: 'accepted' undeclared (first use in this function)
   if(accepted == 0)
3. pda.c：在函数'qX'中：
   pda.c:93:17：错误：'top'未声明（在此函数中首次使用）
   pda.stack[top] = input;

基本上我的全局结构中的变量没有被识别，我不知道为什么。这是我记录的代码：

有任何想法吗？谢谢。

所以我发现这个 PDA 可以接受语言为 {0,1}* 的回文。

但是，我无法理解它如何接受“1”或“0”。

在B其中可以读取 1 或 0 并将相同的符号推入堆栈，然后转到C. 但是，一旦它进入C，它就无处可去，因为要到达堆栈中的 $ 另一个符号需要被读取。

有人可以解释它是如何工作的吗？

我在想，为了接受单个符号，我们需要从Bto D=>转换1,$->ε | 0,$->ε。

我会是正确的吗？

谢谢 ：）

我有一个问题说：

构造一个接受语言 {a^ib^j | 的 PDA 0 <= 我 <= j}

这是给定的解决方案：

但据我了解，一个可能的输入字符串会以 b 开头，因为 i 可能是 0 而 a^i 可能是 1，而 j 可能是 1 而 b^j 可能是 b，这是否意味着应该有一行说的是：

δ (q0, b, z) = (q1, z) ?

还是我误解了什么？