context-free-grammar - 这种语言有下推自动机(PDA)吗？

Question

语言是:{ Aⁿ B⁽²ⁿ⁾ Cⁿ |其中 n>=0 }

我认为它有，因为你可以这样处理它:压入 A，压入 B，对于每个 C 从堆栈弹出 3 次，如果没有 C 并且堆栈为空，则返回 true，否则返回 false。

Answer 1

使用泵引理证明这不是上下文无关语言。

考虑 s = a^p b^2p c^p
然后我们考虑vxy , |vxy|<=p, |vy|>0和 uvⁱxyⁱz 在 L
我们有可能

1. vxy = a^j, j<=p
2. vxy = a^j b^k, j+k<=p
3. vxy = b^j, j<=p
4. vxy = b^j c^k, j+k<=p
5. vxy = c^j, j <=p

无论如何，没有常量u和 v英石。字符串在L中，因为vxy中只能有两个符号然后我们需要可变数量的三分之一来显示 u或 v

您提议的自动机在 AAAC 上失败，返回 true。它并不能保证 B 的数量是 A 的两倍。