automata - PDA 和 CFL 中的泵送引理

Question

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

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

是否是 CFL？

我认为它不是 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，但是是否有可能 tu 泵浦 p 次？

或者有什么解决方案吗？

Answer 1

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

a^pb^2pc^3p 是一个很好的示例，但我建议尝试更短的示例:a^pb^p+1c^p+2。

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