这种语言是否有下推自动机（PDA）？

Question

语言是：{A ⁿ B ^（2n） C ⁿ |其中n> = 0}

我认为它已经存在了，因为你可以像这样处理它：如果没有C并且堆栈为空，则push A，push B，为堆栈中的每个C弹出三次，返回true ，否则返回false。

Answer 1

使用抽象引理来证明这不是一个上下文无关的语言。

考虑S =一^p b ^2PÇ^p
然后考虑vxy，|vxy|<=p, |vy|>0和UV ^我 XY ^我ž以L
我们准备

1. vxy = a ^j，j < = P
2. vxy =一个^Ĵ b ^ķ，J + K < = P
3. vxy = B ^Ĵ，J < = P
4. vxy = B ^ĴÇ^ķ ，J + K < = p
5. vxy = C ^Ĵ，J < = p

在任何情况下，没有常数u和v s.t.字符串是L，因为只能在vxy两个符号，然后我们就需要第三个数量可变的展现在了u或v

你提出的自动机上AAAC失败，返回true。这并不能保证你的B的数量是A的两倍。

Answer 2

没有这样的PDA存在，因为这种语言没有上下文。这是一个简短的证明。这依赖于上下文无关语言在逆同态下被关闭的事实（as mentioned in these slides）。

鉴于语言L = {A ^Ñ乙^2n个Ç^Ñ | n的N}，考虑从

• H（A）所定义的同态H = A
• H（B）= BB
• H（C）= C

的逆应用于L的这种同态是语言h ^-1（L）= {x in Σ * | h（x）∈ L}。查看h的选择，这是语言{A ⁿ B ⁿ C ⁿ | n in N}。这种语言是非上下文无关语言的典型例子。但是，CFL在逆同态下是封闭的，所以因为h不是上下文无关的，所以L不能无上下文。因此，它没有PDA。

希望这会有所帮助！