context-free-grammar - この文法は文脈自由ですか?

Question

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

私が教えてくれたように、最初のプロダクション ルールはコンテキスト フリーです (左側が右側よりも小さいため) が、2 番目のプロダクション ルールではそうではありません (左側の長さが右側と等しいため)。

さて、このステートメントでこの文法について何が言えるでしょうか。それは文脈自由ですか？

Answer 1

コンテキストフリーです。

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

たとえば、ルールが であった場合、aS ---> λそれは状況依存になります。S非終端記号の前に終端記号がある場所にのみ適用できaます。が先行するコンテキストにあったときa。

完全を期すために、文法はすべての生成規則が文脈自由である場合にのみ文脈自由です。