context-free-grammar - 满足常规语言的抽水引理的语言是否与上下文无关？

Question

当一种语言满足常规语言的泵引理时，并不总是意味着它是一种常规语言。那么它至少是一种上下文无关的语言吗？或者介于两者之间？

Answer 1

无论如何，这不是一个编程问题。来自维基百科：“请注意，虽然抽水引理指出所有常规语言都满足上述条件，但此陈述的反面并不正确：满足这些条件的语言可能仍然是非常规的。换句话说，原始语言而抽水引理的一般版本为语言是规则的提供了必要但非充分的条件。”

因此，为了解决您的问题：如果一种语言满足常规语言的抽水引理，那么它至少是一种常规语言。