非縮約文法

形式言語理論では、文法のすべての生成規則 α → β (α と β は非終端記号と終端記号の文字列) に対して、|α| ≤ |β|が成り立つ場合、つまり β には少なくともαと同じ数の記号がある場合、その文法は非縮約的 (または単調) です。文法が本質的に非縮約的であるのは、1 つの例外、つまり規則 S → ε (ここでSは開始記号、ε は空文字列)があり、さらにS がどの規則の右側にも現れない場合です。

文脈依存文法は、すべての規則が αAβ → αγβ の形式である非縮約文法です。ここで、A は非終端記号であり、γ は非終端記号および/または終端記号の空でない文字列です。

しかし、一部の著者は、文脈依存文法という用語を非縮約文法一般を指すために使用している。^[1]

すべての規則に対して |α| < |β| となる非縮約文法は、成長文脈依存文法と呼ばれます。

チョムスキー（1959）はチョムスキー階層を導入した。この階層では文脈依存文法は「タイプ1」文法として出現し、一般的な非縮約文法は出現しない。^[2]

チョムスキー（1963）は、非縮約文法を「タイプ1文法」、文脈依存文法を「タイプ2文法」と呼び、前者から後者への変換を提示することで、2つが弱等価であることを証明した。^[3]

黒田（1964）は、すべての非縮約文法を変換できる黒田標準形を導入した。^[4]

この文法は、開始記号Sを使用して、言語 { a ⁿ b ⁿ c ⁿ  : n ≥ 1}を生成しますが、^[5]これはポンピング補題により文脈自由 ではありません。

同じ言語の文脈依存文法を以下に示します。

すべての文脈依存文法は非縮約文法です。

簡単な手順があります

• 非縮約文法を黒田標準形に置き換えると、^{[4] [6]}となり、
• 黒田標準形の非縮約文法を文脈依存文法に変換します。

したがって、これら 3 種類の文法は表現力が同等であり、すべて空の文字列を含まない文脈依存言語を正確に記述します。本質的に非縮約的な文法は、文脈依存言語のセットを正確に記述します。

黒田正規形を避けて文脈依存文法に直接変換する:

任意の非縮約文法 ( N、Σ、P、S ) に対して、文脈依存文法 ( N '、Σ、P '、S ) を次のように構築します。

1. すべての終端記号a∈Σに対して、新しい非終端記号[ a ]∈N 'と新​​しい規則([ a ]→ a ) ∈P 'を導入します。
2. Pの規則では、すべての終端記号aを対応する非終端記号 [ a ] に置き換えます。その結果、これらの規則はすべて、非終端記号X _i、Y _j、およびm ≤ nに対してX ₁ ... X _m → Y ₁ ... Y _nという形式になります。
3. m >1の各規則X ₁ ... X _m → Y ₁ ... Y _nを2 m個の規則に置き換える: ^{[注 1]}

ここで各Z _i ∈ N 'は他には現れない新しい非終端記号である。^{[7] [8]}

たとえば、{ a ⁿ b ⁿ c ⁿ | n ≥ 1 } の上記の非縮約文法は、同じ言語に対して 次の文脈依存文法（開始記号Sを使用）につながります。

• 文脈依存文法
• 文脈依存文法の発展
• 黒田正規形

• Book, RV (1973). 「文脈依存文法の構造について」. International Journal of Computer & Information Sciences . 2 (2): 129–139. doi :10.1007/BF00976059. hdl : 2060/19710024701 . S2CID  31699138.
• マテスク、アレクサンドル。サロマー、アルト (1997)。 「第 4 章: 古典言語理論の側面」。グジェゴシュのローゼンベルクにて。サロマー、アルト (編)。形式言語のハンドブック。第 1 巻: 単語、言語、文法。スプリンガー・フェルラーク。 175–252ページ。ISBN 3-540-61486-9。