context-free-grammar - 您如何将语言分类为常规、上下文无关和短语结构？

Question

如果给你一种语言，你如何判断它是正规的、CF 但不是正规的，还是短语结构而不是 CF？有没有解决这个问题的好方法？我可以随意尝试制作 FA 或 PDA，但我觉得有更好的方法来做。

经典例子：

L = { a^nb^nc^n | n >= 0 }

从哪里开始？谢谢。

Answer 1

你有点对它们进行分类的感觉。我不知道一个非常有条理的方法。由于语言通常是彼此的子集和超集，因此您估计它在该层次结构中的位置并表明它不能是常规语言，但它可能是 CFL。