语言是:{ An B(2n) Cn |其中 n>=0 }
我认为它有,因为你可以这样处理它:压入 A,压入 B,对于每个 C 从堆栈弹出 3 次,如果没有 C 并且堆栈为空,则返回 true,否则返回 false。
最佳答案
使用泵引理证明这不是上下文无关语言。
考虑 s = ap b2p cp
然后我们考虑vxy
, |vxy|<=p, |vy|>0
和 uvixyiz 在 L
我们有可能
- vxy = aj, j<=p
- vxy = aj bk, j+k<=p
- vxy = bj, j<=p
- vxy = bj ck, j+k<=p
- vxy = cj, j <=p
无论如何,没有常量u
和 v
英石。字符串在L中,因为vxy
中只能有两个符号然后我们需要可变数量的三分之一来显示 u
或 v
您提议的自动机在 AAAC 上失败,返回 true。它并不能保证 B 的数量是 A 的两倍。
关于context-free-grammar - 这种语言有下推自动机(PDA)吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16491361/