索引文法

インデックス文法は、非終端記号にフラグのリスト、つまりインデックス記号が備わっている点で、文脈自由文法を一般化したものです。インデックス文法によって生成される言語は、インデックス言語と呼ばれます。

ホップクロフトとウルマン（1979）に続く現代の出版物 ^[2]では、 インデックス文法は5組G = ⟨ N、T、F、P、S ⟩として正式に定義されており、ここで

• Nは変数または非終端記号の集合であり、
• Tは終端記号の集合（「アルファベット」）であり、
• Fは、いわゆるインデックス記号、またはインデックスの集合である。
• S ∈ N は開始記号であり、
• P は生成規則の有限集合です。

生成規則およびインデックス文法の導出では、インデックス記号の文字列（「スタック」）σ ∈ F ^*がすべての非終端記号A ∈ Nに付加され、A [ σ ] と表記されます。^{[注 1]} 終端記号の後にインデックス スタックが続くことはできません。インデックス スタックσ ∈ F ^*と、非終端記号と終端記号の文字列α ∈ ( N ∪ T ) ^{*の場合、} α [ σ ] はαのすべての非終端記号に[ σ ]を付加した結果を表します。たとえば、αがa B C d Eに等しく、 a、d ∈ Tが終端で、B、C、E ∈ Nが非終端記号である場合、 α [ σ ] はa B [ σ ] C [ σ ] d E [ σ ] を表します。この表記法を使用すると、 P の各生成規則は次の形式になります。

1. A [σ] → α[σ]、
2. A [σ] → B [ f σ]、または
3. A [ f σ] → α[σ],

ここで、A、B ∈ Nは非終端記号、f ∈ Fはインデックス、σ ∈ F ^*はインデックス記号の文字列、α ∈ ( N ∪ T ) ^{* は非終端記号と終端記号の文字列です。著者によっては、生成規則のインデックス スタックに「} σ」ではなく「..」と記述する人もいます。その場合、タイプ 1、2、3 の規則はそれぞれA [..]→ α [..]、   A [..]→ B [ f ..]、A [ f ..]→ α [..]となります。

導出は、各非終端記号にインデックス スタックが付加されることを除いて、文脈自由文法の導出と似ています。たとえば、 A [ σ ] → B [ σ ] C [ σ ] のような生成規則が適用されると、Aのインデックス スタックがBとC の両方にコピーされます。さらに、ルールはスタックにインデックス シンボルをプッシュしたり、その「一番上の」(つまり、一番左の) インデックス シンボルをポップしたりできます。

正式には、関係 ⇒ (「直接導出」) は、「文形式」の 集合 ( N [ F ^* ]∪ T ) ^{*上で次のように定義されます。}

1. A [ σ ] → α [ σ ] がタイプ 1 の生成規則である場合、上記の定義を使用して、 β A [ φ ] γ ⇒ β α [ φ ] γとなります。つまり、規則の左側のインデックス スタックφが右側の各非終端記号にコピーされます。
2. A [ σ ] → B [ fσ ] がタイプ2の生成である場合、 β A [ φ ] γ ⇒ β B [ fφ ] γとなる。つまり、右側のインデックススタックは、左側のスタックφにf をプッシュすることで取得されます。
3. A [ fσ ] → α [ σ ] がタイプ 3 の生成規則である場合、 β A [ fφ ] γ ⇒ β α [ φ ] γとなり、ここでもα [ σ ]の定義が使用されます。つまり、最初のインデックスf が左側のスタックからポップされ、右側の各非終端記号に分配されます。

いつものように、導出関係∗⇒は直接導出の反射的推移閉包として定義される⇒。言語L ( G ) = { w ∈ T ^* : S ∗⇒ w } は、開始記号から導出可能なすべての終端記号の文字列の集合です。

歴史的に、インデックス文法の概念は、アルフレッド・エイホ（1968）^{[3]によって異なる形式論を用いて初めて導入された。エイホは、インデックス文法を5組（} N、T、F、P、S） として定義した。ここで

1. Nは変数または非終端記号の有限のアルファベットである
2. Tは終端記号の有限のアルファベットである
3. F ⊆ 2 ^{N × ( N ∪ T ) *}は、いわゆるフラグの有限集合である（各フラグは、いわゆるインデックス生成集合である）。
4. P ⊆ N × ( NF ^* ∪ T ) ^{* は}生成規則の有限集合である。
5. S ∈ Nは開始記号である

直接的な導出は次のとおりです。

• Pからの生成p = ( A → X ₁ η ₁ … X _k η _k ) は、非終端記号A ∈ Nとその (空の可能性のある) フラグ文字列ζ ∈ F ^*に一致します。コンテキストでは、γ Aζ δ はpを介してγ X ₁ θ ₁ … X _k θ _k δに導出されます。ここで、X _iが非終端記号の場合はθ _i = η _i ζで、それ以外の場合は空語です。したがって、Aの古いフラグは、 pによって生成された新しい非終端記号ごとにコピーされます。このような各生成は、ホップクロフト/ウルマン形式におけるタイプ 1 および 2 の適切な生成によってシミュレートできます。
• インデックス生成規則p = ( A → X ₁ … X _k ) ∈ f はAfζに一致し（フラグfは非終端記号Aに続く最初の記号に一致する必要があります）、残りのインデックス文字列ζをそれぞれの新しい非終端記号にコピーします。γ Afζ δはγ X 1 θ ₁ … X _k θ _k δに派生します。ここで、θ _{i は}X _iが終端記号の場合は空語、非終端記号の場合は ζ です_。このような生成規則はそれぞれ、ホップクロフト/ウルマン形式におけるタイプ 3 の生成規則に対応します。

この形式主義は例えば林（1973、p.65-66）によって使用されている。^[4]

実際には、インデックスのスタックは、どのルールがどの順序で適用されたかを数えて記憶することができます。たとえば、インデックス付き文法は、単語のトリプル { www  : w ∈ { a , b } ^* } のコンテキスト依存言語を記述できます。

abbabbabbの派生語は

S [] ⇒ S [ g ] ⇒ S [ gg ] ⇒ S [ fgg ] ⇒ T [ fgg ] T [ fgg ] T [ fgg ] ⇒ a T [ gg ] T [ fgg ] T [ fgg ] ⇒ ab T [ g ] T [ fgg ] T [ fgg ] ⇒ abb T [] T [ fgg ] T [ fgg ] ⇒ abb T [ fgg ] T [ fgg ] ⇒ ... ⇒ abb abb T [ fgg ] ⇒ ... ⇒ abb abb abb .

別の例として、文法G = ⟨ { S , T , A , B , C }, { a , b , c }, { f , g }, P , S ⟩は言語{ a ⁿ b ⁿ c ⁿ : n ≥ 1 }を生成する。ここで、生成集合Pは以下で構成される。

導出例は以下の通りである。

S [] ⇒ T [ g ] ⇒ T [ fg ] ⇒ A [ fg ] B [ fg ] C [ fg ] ⇒ aA [ g ] B [ fg ] C [ fg ] ⇒ aA [ g ] bB [ g ] C [ fg ] ⇒ aA [ g ] bB [ g ] cC [ g ] ⇒ aa bB [ g ] cC [ g ] ⇒ aa bb cC [ g ] ⇒ aa bb cc .

両方の例の言語は、ポンピング補題により文脈自由ではありません。

ホップクロフトとウルマンは、インデックス言語はインデックス文法以外のいくつかの形式主義によって生成されるため、「自然な」クラスであると考える傾向がある。^[5]

• アホの一方向ネストスタックオートマトン^[6]
• フィッシャーのマクロ文法^[7]
• 積み重ねられたスタックを持つグライバッハのオートマトン^[8]
• マイバウムの代数的特徴付け^[9]

林^[4]はポンピング補題をインデックス文法に一般化した。逆に、ギルマン^{[10] [11]}はインデックス言語に対して「縮小補題」を与えている。

ジェラルド・ガズダーは、2番目のクラスである線形インデックス文法（LIG）を定義しました。^[14]これは、各生成規則で最大1つの非終端記号がスタックを受け取るように指定することを要求します。^{[注 2]} 一方、通常のインデックス文法では、すべての非終端記号がスタックのコピーを受け取ります。正式には、線形インデックス文法は通常のインデックス文法と同様に定義されますが、生成規則の形式要件は次のように変更されます。

1. A [ σ ] → α [] B [ σ ] β []、
2. A [ σ ] → α [] B [ fσ ] β []、
3. A [ fσ ] → α [] B [ σ ] β []、

ここで、A、B、f、σ、αは上記のように使用され、β ∈ ( N ∪ T ) ^*はαのような非終端記号と終端記号の文字列です。^{[注 3]また、直接導出関係 ⇒ も上記と同様に定義されます。この新しい文法のクラスは、}軽度文脈依存クラス に属する厳密に小さい言語のクラスを定義します^[15]。

言語 { www  : w ∈ { a , b } ^* } はインデックス文法では生成可能ですが、線形インデックス文法では生成できません。一方、 { ww  : w ∈ { a , b } ^* } と { a ⁿ b ⁿ c ⁿ  : n ≥ 1 } はどちらも線形インデックス文法で生成可能です。

元の生成規則と修正された生成規則の両方が認められる場合、言語クラスは索引言語のままである。^[16]

σを任意のスタックシンボルの列とすると、言語L = { a ⁿ b ⁿ c ⁿ | n ≥ 1 } ^[注4]の文法を次のように 定義できる。

文字列abc を導出するには、次の手順に従います。

S [] ⇒ aS [ f ] c ⇒ aT [ f ] c ⇒ aT [] bc ⇒ abc

同様に:

S [ ] ⇒ aS [ f ] c ⇒ aaS [ ff ] cc ⇒ aaT [ ff ] cc ⇒ aaT [ f ] bcc ⇒ aaT [ ] bbcc ⇒ aabbcc

線形インデックス言語はインデックス言語のサブセットであるため、すべての LIG を IG として再コード化することができ、LIG は厳密には IG よりも強力ではありません。LIG から IG への変換は比較的簡単です。^[17] LIG 規則は一般に、書き換え規則のプッシュ/ポップ部分を法として、 とほぼ似ています。記号と は、終端記号および/または非終端記号の文字列を表し、LIG の定義により、いずれの非終端記号もスタックが空でなければなりません。これは、もちろん、IG の定義方法に反しています。IG では、スタックがプッシュまたはポップされない非終端記号は、書き換えられた非終端記号とまったく同じスタックを持っている必要があります。したがって、何らかの方法で、 と の非終端記号が、スタックが空でないにもかかわらず、スタックが空であるかのように動作する必要があります。 ${\displaystyle X[\sigma ]\to \alpha Y[\sigma ]\beta }$${\displaystyle \alpha}$${\displaystyle \beta}$${\displaystyle \alpha}$${\displaystyle \beta}$

ルールを例として考えてみましょう。これを IG に変換する場合、 の置き換えは、が何であるかに関係なく とまったく同じように動作するものでなければなりません。これを実現するには、 が空でない任意の を受け取り、スタックからシンボルをポップするルールのペアを用意するだけです。スタックが空のときは、 と書き直すことができます。 ${\displaystyle X[\sigma ]\to Y[]Z[\sigma f]}$${\displaystyle Y[]}$${\displaystyle Y^{\prime }[\sigma ]}$${\displaystyle Y[]}$${\displaystyle \sigma}$${\displaystyle Y^{\prime }[\sigma ]}$${\displaystyle \sigma}$${\displaystyle Y[]}$

${\displaystyle Y^{\prime }[\sigma f]\to Y^{\prime }[\sigma ]}$

${\displaystyle Y^{\prime }[]\to Y[]}$

これを一般に適用して、LIG から IG を導出することができます。たとえば、言語の LIG が次のようになっているとします。 ${\displaystyle \{a^{n}b^{n}c^{n}d^{m}|n\geq 1,m\geq 1\}}$

${\displaystyle S[\sigma ]\to T[\sigma ]V[]}$

${\displaystyle V[]\to d~|~dV[]}$

${\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}$

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

ここでの文法規則は IG 規則ではありませんが、上記の変換アルゴリズムを使用して、 の新しい規則を定義し、文法を次のように変更できます。 ${\displaystyle V^{\prime}}$

${\displaystyle S[\sigma ]\to T[\sigma ]V^{\prime }[\sigma ]}$

${\displaystyle V^{\prime }[\sigma f]\to V^{\prime }[\sigma ]}$

${\displaystyle V^{\prime }[]\to V[]}$

${\displaystyle V[]\to d~|~dV[]}$

${\displaystyle T[\sigma ]\to aT[\sigma f]c~|~U[\sigma ]}$

${\displaystyle U[\sigma f]\to bU[\sigma ]}$

${\displaystyle U[]\to \epsilon }$

各ルールは IG の定義に適合するようになり、書き換えルールの右側にあるすべての非終端記号は、書き換えられたシンボルのスタックのコピーを受け取ります。したがって、インデックス付き文法は、線形インデックス付き文法が記述できるすべての言語を記述できます。

Vijay-ShankerとWeir (1994) ^[18]は、線形索引文法、組み合わせカテゴリ文法、木結合文法、ヘッド文法がすべて同じクラスの文字列言語を定義していることを示しています。彼らの線形索引文法の正式な定義^[19]は上記とは異なります。^{[説明が必要]}

LIG（およびそれらの弱同値言語）は、 LCFRS、MCTAG、MCFG、および最小文法（MG）を含む他の弱同値言語ファミリーによって生成される言語よりも厳密に表現力が劣ります（つまり、適切なサブセットを生成します）。後者のファミリーは（また）多項式時間で解析できます。^[20]

^{Staudacher (1993) [12]}が導入した別の形式のインデックス文法は、分散インデックス文法 (DIG) のクラスです。DIG と Aho のインデックス文法の違いは、インデックスの伝播です。書き換え操作中にシンボル スタック全体をすべての非終端に配布する Aho の IG とは異なり、DIG はスタックをサブスタックに分割し、サブスタックを選択した非終端に配布します。

DIGのバイナリ配布ルールの一般的なルールスキーマは次の形式です。

X [ f ₁ ... f _i f _{i +1} ... f _n ] → α Y [ f ₁ ... f _i ] β Z [ f _{i +1} ... f _n ] γ

ここで、α、β、γは任意の終端文字列です。3元分布文字列の場合:

X [ f ₁ ... f _i f _{i +1} ... f _j f _{j +1} ... f _n ] → α Y [ f ₁ ... f _i ] β Z [ f _{i +1} ... f _j ] γ W [ f _{j +1} ... f _n ] η

書き換え規則の右側にある非終端の数が多い場合も同様です。一般に、書き換え規則の右側にm個の非終端がある場合、スタックはm方向に分割され、新しい非終端の間で分散されます。パーティションが空である特殊なケースがあり、その場合、規則は事実上 LIG 規則になります。したがって、分散インデックス言語は線形インデックス言語のスーパーセットです。

• チョムスキー階層

• 「Prolog における NLP」のインデックス付き文法と言語に関する章