automata - 在 PDA 和 CFL 中抽取引理

Question

我有一个引理问题，我完全坚持...

L = {w ∈ {a, b, c}∗ : na (w) < nb (w) < nc (w)}

是不是节能灯？

我要求它不是 CFL，因为只有一个堆栈来记住所有这些条件是不够的。你可以记住 na (w) < nb (w) 或 na (w)< nc (w),nb (w) < nc (w) 但不是 na (w) < nb (w) < nc (w)。另外，我认为如果语言是 a^pb^2pc^3p 而不是我打气 |vy| p 次 L 不是 CF 但是你有可能抽 p 次吗？

或者对解决方案有什么想法？

Answer 1

请注意，抽水引理要求L中的每个字符串在抽水后都留在L中。因此，即使对于L中某些特定形式的字符串，也足以产生矛盾。

a ^p b ^2p c ^3p是一个很好的例子，但我建议尝试一个较短的例子： a ^p b ^p+1 c ^p+2。

推理与维基百科文章中的几乎相同：Pumping lemma:Usage。您将有相同的五个案例，并且很容易在每个案例中产生矛盾。