この文法コンテキストは無料ですか？

Question

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

最初のプロダクションルールは文脈自由（左辺が右辺より小さいため）ですが、2番目のプロダクションルールでは（左辺の長さが右辺と等しいので）そうではありません。

この文章では、この文法について何が言えるでしょうか。文脈自由であるかどうか？

Answer 1

文脈自由です。

"コンテキストフリー"は、プロダクションルールの左側にコンテキストが存在することを示します。
右側が等しく長いことは問題ではありません。左手側が単一の非終端子で構成されていることだけが重要です。
プロダクションルールの左端が単一の非終端記号で構成されている場合、表示されるコンテキストに関係なく、その非終端記号が現れるすべての場所に規則を適用できます。

ルールがたとえばaS ---> λの場合は、コンテキストに依存します。非終端記号Sの前に端末記号aが置かれた場所にのみ適用できます。 の文脈にあったときの前にaがある。

完全性のために、文法はすべてのプロダクションルールが文脈自由であるだけです。