什么时候说语言是上下文无关的？

Question

什么时候说一种语言是上下文无关的？

另外，上下文无关语言和上下文无关语法有什么区别？

Answer 1

上下文无关语言是一种可以由上下文无关语法生成的语言（即可能是无限的字符串集）。一般来说，也可以使用非上下文无关语法生成完全相同的语言，但这无关紧要：如果存在单个上下文无关语法生成该语言，则该语言是上下文无关的。

上下文无关语法是一种语法，其中每个产生式的左侧都有一个非终结符。它是上下文无关的，因为产生式中的非终结符可以在不考虑它出现的上下文的情况下进行扩展。上下文相关语法可能在产生式的左侧有多个符号，因此包括非终结符只有出现在正确的上下文中才能扩展的情况。