重複の可能性:
文脈依存文法と文脈自由文法
私の教科書では、これら2つの用語の説明は次のとおりです。
文脈依存文法:
文法は、w1 → w2 の形式の生成を持つことができます。ここで、w1 = lAr および w2 = lwr です。ここで、A は非終端記号であり、l および r は 0 個以上の終端または非終端記号の文字列であり、w は終端または非終端記号の空でない文字列です。非終端記号。また、S が他のプロダクションの右辺に現れない限り、プロダクション S → λ を持つこともできます。
文脈自由文法:
文法は、w1 → w2 の形式の生成のみを持つことができます。ここで、w1 は、終端記号ではない単一の記号です。タイプ 3 文法は、w1 = A および w2 = aB または w2 = a (A と B が非終端記号で a が終端記号)、または w1 = S と w2 = λ。
私の教科書では、著者は次のように述べています。 CSG は CFG の特殊なケースです。しかし、私はこの点を理解していません。CSGでは、lAr -> lwrだからです。l と r は、0個以上の終端または非終端の文字列にすることができます。つまり、ゼロの文字列の場合 (長さ = 0 を意味します)。lAr を A と書くことができます。したがって、CSG は CFG になります。だから、CSGはCFGです
私が理解していることは間違っていますか?私のためにそれを修正してください。
ありがとう :)