这个文法上下文是否自由？

Question

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

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

嗯，对于这个语句中的这个语法，我们能说些什么呢。是否上下文无关？

Answer 1

它是上下文无关的。

"Context free"指的是产生式规则左侧存在上下文。
右侧的长度是否相同并不重要；唯一重要的是左侧由一个非终结符组成。
当产生式规则的左侧由一个非终结符组成时，该规则可以应用于该非终结符出现的任何地方，而不管它出现的上下文。

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

为了完整起见，如果一个文法的所有产生式规则都是上下文无关的。