ไวยากรณ์ดัชนี

ไวยากรณ์แบบมีดัชนีเป็นการขยายความของไวยากรณ์แบบไม่ขึ้นกับบริบทโดยที่สัญลักษณ์ที่ไม่ใช่เทอร์มินัลจะมีรายการของแฟล็กหรือสัญลักษณ์ดัชนีภาษาที่สร้างขึ้นโดยไวยากรณ์แบบมีดัชนีเรียกว่าภาษาแบบมีดัชนี

ในสิ่งพิมพ์ร่วมสมัยตาม Hopcroft และ Ullman (1979) ^{[ 2 ]} ไวยากรณ์ที่มีดัชนีจะถูกกำหนดอย่างเป็นทางการเป็น 5-tuple 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 } คือเซตของสตริงทั้งหมดของสัญลักษณ์เทอร์มินัลที่สามารถอนุมานได้จากสัญลักษณ์เริ่มต้น

ในทางประวัติศาสตร์ แนวคิดของไวยากรณ์ดัชนีได้รับการแนะนำครั้งแรกโดยAlfred Aho (1968) ^{[ 3 ]}โดยใช้รูปแบบที่แตกต่างออกไป Aho นิยามไวยากรณ์ดัชนีว่าเป็น 5-tuple ( N , T , F , P , S ) โดยที่

1. Nคือชุดตัวอักษร จำกัด ของตัวแปรหรือสัญลักษณ์ที่ไม่ใช่เทอ ร์มินัล
2. Tคือชุดตัวอักษรจำกัดของสัญลักษณ์เทอร์มินัล
3. F ⊆ 2 ^{N × ( N ∪ T ) *}คือเซตจำกัดของสิ่งที่เรียกว่าแฟล็ก (แต่ละแฟล็กเองก็เป็นเซตของสิ่งที่เรียกว่าการผลิตดัชนี )
4. P ⊆ N × ( NF ^* ∪ T ) ^*คือเซตจำกัดของการผลิต
5. S ∈ Nคือสัญลักษณ์เริ่มต้น

การคำนวณโดยตรงมีดังนี้:

• กฎการผลิตp = ( A → X η ... X η ) จากPจับคู่กับสัญลักษณ์ที่ไม่ใช่เทอร์มินัลA ∈ Nตามด้วยสตริงของแฟล็กζ ∈ F ^* (ซึ่งอาจว่างเปล่า) ในบริบทγ Aζ δผ่านpจะได้เป็นγ X θ ... X θ δโดยที่θ = η ζถ้าX เป็นสัญลักษณ์ที่ไม่ใช่เทอร์มินัล และเป็นคำว่างเปล่าในกรณีอื่น แฟล็กเดิมของAจึงถูกคัดลอกไปยังสัญลักษณ์ที่ไม่ใช่เทอร์มินัลใหม่แต่ละตัวที่สร้างขึ้นโดยpกฎการผลิตแต่ละข้อสามารถจำลองได้ด้วยกฎการผลิตประเภทที่ 1 และ 2 ที่เหมาะสมในรูปแบบ Hopcroft/Ullman
• กฎการผลิตดัชนีp = ( A → X ... X ) ∈ fจะจับคู่กับAfζ (แฟล็กfที่มาจากต้องตรงกับสัญลักษณ์แรกที่ตามหลังสัญลักษณ์ที่ไม่ใช่เทอร์มินัลA ) และคัดลอกสตริงดัชนีที่เหลือζไปยังสัญลักษณ์ที่ไม่ใช่เทอร์มินัลใหม่แต่ละตัว: γ Afζ δจะได้เป็นγ X θ ... X θ δโดยที่θ คือคำว่างเมื่อX เป็นเทอร์มินัล และζเมื่อเป็นสัญลักษณ์ที่ไม่ใช่เทอร์มินัล กฎการผลิตแต่ละข้อดังกล่าวจะสอดคล้องกับกฎการผลิตประเภทที่ 3 ในรูปแบบ Hopcroft/Ullman

รูปแบบดังกล่าวถูกใช้โดย Hayashi (1973, หน้า 65-66) ^{[ 4 ]}

ในทางปฏิบัติ ชุดดัชนีสามารถนับและจดจำได้ว่ามีการใช้กฎใดบ้างและเรียงลำดับอย่างไร ตัวอย่างเช่น ไวยากรณ์แบบมีดัชนีสามารถอธิบายภาษาที่ไวต่อบริบทของกลุ่มคำสามคำ { www  : w ∈ { a , b } ^* }:

S [ σ ]	→	S [ fσ ]	ที [ เอฟโอซี ]	→	a T [ σ ]
S [ σ ]	→	S [ gσ ]	ที [ จีโอซี ]	→	b T [ σ ]
S [ σ ]	→	T [ σ ] T [ σ ] T [ σ ]	ที []	→	ε

อนุพันธ์ของ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σ ]	A [ fσ ] → a A [ σ ]	A [ gσ ] → a
T [ σ ] → T [ fσ ]	B [ fσ ] → b B [ σ ]	B [ gσ ] → b
T [ σ ] → A [ σ ] B [ σ ] C [ σ ]	C [ fσ ] → c C [ σ ]	C [ gσ ] → c

ตัวอย่างของการพิสูจน์คือ

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 .

ภาษาตัวอย่างทั้งสองภาษาไม่ใช่ภาษาไร้บริบทตามทฤษฎีบท ปั๊ม

HopcroftและUllmanมีแนวโน้มที่จะพิจารณาภาษาที่มีดัชนีเป็นคลาส "ธรรมชาติ" เนื่องจากภาษาเหล่านี้ถูกสร้างขึ้นโดยรูปแบบอื่นนอกเหนือจากไวยากรณ์ที่มีดัชนี เช่น^{[ 5 ]}

• ออโตมาตาซ้อนซ้อนทางเดียวของAho ^{[ 6 ]}
• ไวยากรณ์มาโครของฟิชเชอร์^{[ 7 ]}
• ออโตมาตาของเกรบาค ที่มีสแต็กซ้อนสแต็ก ^{[ 8 ]}
• ลักษณะเฉพาะทางพีชคณิตของMaibaum ^{[ 9 ]}

Hayashi ^{[ 4 ]}ได้ขยายเลมมาการสูบฉีดไปยังไวยากรณ์ดัชนี ในทางกลับกัน Gilman ^{[ 10 ] [ 11 ]}ได้ให้ "เลมมาการหดตัว" สำหรับภาษาดัชนี

Gerald Gazdarได้กำหนดคลาสที่สอง คือไวยากรณ์ดัชนีเชิงเส้น ( LIG ) ^{[ 14 ]}โดยกำหนดให้ระบุสัญลักษณ์ที่ไม่ใช่เทอร์มินัลอย่างมากที่สุดหนึ่งตัวในแต่ละกฎการผลิตให้รับสแต็ก^{[หมายเหตุ 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 ]}ได้ดังนี้

S [ σ ]	→	a S [ fσ ] c
S [ σ ]	→	ที [ σ ]
ที [ เอฟโอซี ]	→	ที [ σ ] บี
ที []	→	ε

ในการสร้างสตริง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 จะมีลักษณะคล้ายกับโดยตัดส่วน push/pop ของกฎการเขียนใหม่ออกไป สัญลักษณ์และแทนสตริงของสัญลักษณ์เทอร์มินัลและ/หรือสัญลักษณ์ที่ไม่ใช่เทอร์มินัล และสัญลักษณ์ที่ไม่ใช่เทอร์มินัลใดๆ ใน จะต้องมีสแต็กว่าง ตามคำจำกัดความของ 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 }[]\ถึง Y[]}$

เราสามารถนำหลักการนี้ไปใช้โดยทั่วไปเพื่อสร้าง IG จาก LIG ได้ ตัวอย่างเช่น หาก 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[]\ถึง d~|~dV[]}$

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

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

${\displaystyle U[]\ถึง \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 }[]\ถึง V[]}$

${\displaystyle V[]\ถึง d~|~dV[]}$

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

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

${\displaystyle U[]\ถึง \epsilon }$

แต่ละกฎในขณะนี้ตรงตามคำจำกัดความของไวยากรณ์แบบดัชนี (IG) ซึ่งสัญลักษณ์ที่ไม่ใช่เทอร์มินัลทั้งหมดทางด้านขวามือของกฎการเขียนใหม่จะได้รับสำเนาของสแต็กสัญลักษณ์ที่เขียนใหม่ ดังนั้นไวยากรณ์แบบดัชนีจึงสามารถอธิบายภาษาทั้งหมดที่ไวยากรณ์แบบดัชนีเชิงเส้นสามารถอธิบายได้

Vijay-Shanker และ Weir (1994) ^{[ 18 ]}แสดงให้เห็นว่าไวยากรณ์ดัชนีเชิงเส้น ไวยากรณ์เชิงหมวดหมู่แบบผสมผสาน ไวยากรณ์ที่เชื่อมต่อต้นไม้และ ไวยากรณ์ หัว ล้วนกำหนดคลาสเดียวกันของภาษาสตริง คำจำกัดความอย่างเป็นทางการของไวยากรณ์ดัชนีเชิงเส้น^{[ 19 ]}แตกต่างจากข้าง ต้น

LIGs (และรูปแบบที่เทียบเท่ากันอย่างอ่อน ) มีความสามารถในการแสดงออกน้อยกว่าอย่างเคร่งครัด (หมายความว่าพวกมันสร้างชุดย่อยที่เหมาะสม) เมื่อเทียบกับภาษาที่สร้างขึ้นโดยตระกูลรูปแบบที่เทียบเท่ากันอย่างอ่อนอีกตระกูลหนึ่ง ซึ่งรวมถึง: LCFRS , MCTAG , MCFGและไวยากรณ์แบบมินิมัลลิสต์ (MGs) ตระกูลหลังนี้สามารถแยกวิเคราะห์ได้ในเวลาพหุนามเช่น กัน ^{[ 20 ]}

ไวยากรณ์แบบดัชนีอีกรูปแบบหนึ่งที่ Staudacher (1993) แนะนำ^{[ 12 ]}คือคลาสของไวยากรณ์แบบดัชนีแบบกระจาย (DIGs) สิ่งที่ทำให้ DIGs แตกต่างจากไวยากรณ์แบบดัชนีของ Aho คือการแพร่กระจายของดัชนี ซึ่งแตกต่างจาก IGs ของ Aho ที่กระจายสแต็กสัญลักษณ์ทั้งหมดไปยังไม่ใช่เทอร์มินัลทั้งหมดในระหว่างการดำเนินการเขียนใหม่ DIGs จะแบ่งสแต็กออกเป็นสแต็กย่อยและกระจายสแต็กย่อยไปยังไม่ใช่เทอร์มินัลที่เลือกไว้

โครงร่างกฎทั่วไปสำหรับกฎการแจกแจงแบบไบนารีของ DIG มีรูปแบบดังนี้

X [ f ... f f ... f ] → α Y [f ... f ] β Z [ f ... f ] γ

โดยที่ α, β และ γ เป็นสตริงเทอร์มินัลใดๆ สำหรับสตริงที่กระจายแบบไตรภาค:

X [ f ... f f ... f f ... f ] → α Y [f ... f ] β Z [ f ... f ] γ W [ f ... f ] η

และเป็นเช่นนี้ต่อไปสำหรับจำนวนที่ไม่ใช่เทอร์มินัลที่มากขึ้นในด้านขวามือของกฎการเขียนใหม่ โดยทั่วไป หากมีที่ไม่ใช่เทอร์มินัลm ตัวในด้านขวามือของกฎการเขียนใหม่ สแต็กจะถูกแบ่งออกเป็น mส่วนและกระจายไปยังที่ไม่ใช่เทอร์มินัลใหม่เหล่านั้น โปรดสังเกตว่ามีกรณีพิเศษที่ส่วนแบ่งว่างเปล่า ซึ่งทำให้กฎนั้นเป็นกฎ LIG อย่างมีประสิทธิภาพ ดังนั้น ภาษาที่มีดัชนีแบบกระจายจึงเป็นซูเปอร์เซตของภาษาที่มีดัชนีเชิงเส้น

• ลำดับชั้นของชอมสกี

• บทที่ว่าด้วยไวยากรณ์และภาษาที่มีดัชนีในหนังสือ "NLP ใน Prolog"