finite-automata - 给定的上下文无关语言是否是常规语言

Question

是否可以决定：

1. 给定的语法是上下文无关的？

2. 给定的递归语言是上下文无关的？

3. 给定的上下文无关语言是常规的吗？

Answer 1

给定的语法可以给我们语言，使用语言和 Pumping Lemma，我们可以很容易地确定给定的语法是否是上下文无关的

通过使用 Greibach 定理，我们可以证明上下文无关语言是否是常规语言是不可判定的。