もうひとつの定義
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/06 05:50 UTC 版)
文脈依存文法の別の定義として、P 内の生成規則に次のような制限を与えたものがある。各生成規則は α -> β という形式で、| α | ≤ | β | という制限に従う。ここで | α | は α の長さである。この文法では生成規則を適用したときに文字列の長さが減ることがないので、「単調文法」（Monotonic Grammar）とか「非縮小文法」（Noncontracting Grammar）などと呼ばれる。 非縮小文法と文脈依存文法は異なるが、同じ言語クラスを定義できるという意味でほぼ等価である（違いは、非縮小文法では空の文字列 ε を含む言語を生成できない点である）。文脈依存文法で記述された言語 L に対して、非縮小文法は L - {ε} を記述できるし、その逆も真である。
※この「もうひとつの定義」の解説は、「文脈依存文法」の解説の一部です。
「もうひとつの定義」を含む「文脈依存文法」の記事については、「文脈依存文法」の概要を参照ください。
ウィキペディア小見出し辞書の「もうひとつの定義」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- もうひとつの定義のページへのリンク
