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 in 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然后我们需要可变数量的第三个符号才能显示在 upu或v

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

Answer 2

不存在这样的 PDA，因为这种语言不是上下文无关的。这是一个简短的证明。这依赖于上下文无关语言在逆同态下封闭的事实（如这些幻灯片中所述）。

给定语言 L = { A ⁿ B ²ⁿ C ⁿ | n 在 N } 中，考虑从定义的同态 h

• h(A) = A
• h(B) = BB
• h(C) = C

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

希望这可以帮助！