context-free-grammar - 这个语法上下文是免费的吗？

Question

G:    S ---> aSb
      S ---> λ

正如我所说的，第一个生产规则是无上下文的（因为左侧小于右侧），但对于第二个生产规则，它不是（因为左侧长度等于右侧）。

好吧，我们可以在这个陈述中对这个语法说些什么。它是否与上下文无关？

Answer 1

它是上下文无关的。

“无上下文”是指在产生式规则的左侧存在上下文。
右手边同样长并不重要；重要的是左侧由单个非终结符组成。
当产生式规则的左侧由单个非终结符组成时，该规则可以应用于该非终结符出现的任何地方，而不管它出现的上下文。

例如，如果规则是 ，aS ---> λ那么它将是上下文相关的；它只能用于非终结符S前面有终结符的地方a；当它在被a.

为了完整起见，语法只有在其所有生产规则都是上下文无关的情况下才是上下文无关的。