问题标签 [pushdown-automaton]

我知道 Y 是左递归的，但为什么 Z 不是左递归的？

对于Y，我得到了

然后因式分解

其中“e”为空

使用任何技术（替换、因式分解、左递归删除），构造一个接受与 G 相同语言的 LL(1) 文法。

到目前为止，我这样做了：

X 是左递归的，所以：

我还需要做什么来构造一个 LL(1)，我可以考虑 Y 吗？

我试图了解 PDA 的工作原理。在下图中，我了解了转换函数的工作原理以及堆栈必须如何更新。但是我唯一的问题是为什么开始状态也是接受状态？而 PDA 用于 L = {on1n | n ≥ 0}，表示它不能接受空字符串。有人可以解释一下使 start 处于接受状态的原因吗？

在构造确定性下推自动机时，每个状态都可以是最终状态吗？

我在构建一个接受以下语言的 DPDA 时遇到了麻烦：

L = { 0 ⁿ 1 ^m | n ≥ m }

我的方法是使初始状态成为最终状态，可以将 0 推入堆栈以获取输入 0，然后转换到另一个最终状态，该最终状态可以从堆栈中弹出 0 以获取输入 1。我相信这个解决方案是正确的，但是每个状态都是最终状态似乎不寻常，我想验证我的方法是否有效。

这是正确的方法吗？我可以将两种状态都作为最终状态吗？这是我的 DPDA 的确切转换函数 δ。

δ(q ₀ , 0, Z ₀ ) = { (q ₀ , 0 Z ₀ ) }

δ(q ₀ , 0, 0) = { (q ₀ , 0 0) }

δ(q ₀ , 1, 0) = { (q ₁ , ε) }

δ(q ₁ , 1, 0) = { (q ₁ , ε) }

我有一个关于为该语言设计下推自动机的问题：

换句话说，'s in 的数量是b'sw数量的2 倍和's 数量a的3 倍之间a。

我对这个问题感到困惑：我知道（希望如此！）当 's 的数量分别b等于 's 数量的两倍a或 's 数量的 3 倍时，如何设计 PDA 以接受该语言a。

这种语言似乎是它们的交集，但我认为没有一种简单的方法可以使用这些交集来创建 PDA。我们如何结合数字可以介于两个值之间的事实。

任何帮助深表感谢...

PS如果您还可以提供上下文无关的语法（以及解释），那也将非常有帮助。

PPS：另外，如果有人可以提供一个链接以某种方式展示如何逐步构建无上下文语法，我真的需要它。（我找到了正则表达式的正则文法的链接，但是对于上下文无关文法，当我尝试跟踪变量并看到一个变量转到自身，或者转到另一个变量时，该变量又返回到初始变量，我真的很困惑。）

我看到一个关于自动机理论的注释：

考虑以下语言：

L={xy : x,y in {a,b}*}

并考虑以下约束：

1) x=y

2) x != y

3) x=(y) 反向

4) x 的数量不等于 y 的数量

我读了一种带有约束 2,3,4 的语言是上下文无关的。高度赞赏 1 到 3 的任何提示或教程。

我想知道下推自动机堆栈是否与所有其他状态共享？

举个例子：

假设我想设计一个 PDA 来识别字母表 {1,0} 上所有非回文字符串的语言。如果我设计一个 PDA 可以识别 {1,0} 上所有回文字符串的语言，然后将所有接受状态交换为失败状态，反之亦然，我会得到所需的 PDA 吗？

编辑：无论哪种方式都有一个简单的正式证明吗？

证明包含相等数量的 01 和 10 的集合 L 是规则的；[提示：L = {'', 0,00..,1,11...,010,101,...}，考虑两个分支；一个以 0 开头，另一个以 1 开头。] 为 L 编写 CFG 和 PDA。

我一直在试图找到一个超级简单的下推自动机解释。到目前为止，这是我想出的：

1. PDA 具有三个操作：

   • 压栈；给定输入状态、输入符号和栈顶符号
   • 从堆栈中弹出；给定输入状态、输入符号和栈顶符号
   • 一个“切换”操作，用另一个符号替换栈顶；给定输入状态、输入符号和栈顶符号

2. PDA 有两种接受形式：

   • 堆栈已被清空的操作
   • 使堆栈返回到起始符号并处于可接受的最终状态的操作。

我想知道我的第二点是否正确。这是 PDA 接受字符串的仅有的两种方式吗？这些方式是否正确？我找到了大量的例子，但没有对这个想法进行超级简单的解释。