Indexovaná gramatika - Indexed grammar

Indexované gramatiky jsou zobecněním bezkontextové gramatiky v tomto neterminály jsou vybaveny seznamy vlajkynebo indexové symbolyJazyk produkovaný indexovanou gramatikou se nazývá indexovaný jazyk.

Definice

Moderní definice od Hopcrofta a Ullmana

V současných publikacích následujících po Hopcroftu a Ullmanovi (1979),^[2]indexovaná gramatika je formálně definována jako n-tice G = ⟨N,T,F,P,S⟩ Kde

• N je sada proměnných nebo neterminální symboly,
• T je sada („abeceda ") koncových symbolů,
• F je sada tzv indexové symbolynebo indexy,
• S ∈ N je počáteční symbol, a
• P je konečná sada produkce.

V produkcích i v derivacích indexovaných gramatik řetězec („stack“) σ ∈ F^* indexových symbolů je připojen ke každému neterminálnímu symbolu A ∈ N, označeno A[σ].^{[poznámka 1]}Za koncovými symboly nemusí následovat zásobníky indexů σ ∈ F^* a řetězec α ∈ (N ∪ T)^* neterminálních a koncových symbolů, α[σ] označuje výsledek připojení [σ] každému neterminálu v α; například pokud α rovná se A B C d E s A,d ∈ T terminál a B,C,E ∈ N tedy neterminální symboly α[σ] označuje A B[σ] C[σ] d E[σ].Pomocí této notace každá produkce v P musí mít formu

1. A[σ] → α [σ],
2. A[σ] → B[Fσ] nebo
3. A[Fσ] → α [σ],

kde A, B ∈ N jsou neterminální symboly, F ∈ F je index, σ ∈ F^* je řetězec indexových symbolů a α ∈ (N ∪ T)^* je řetězec neterminálních a koncových symbolů. Někteří autoři píší „..“ místo „σ"pro zásobník indexů v produkčních pravidlech; pak se načte pravidlo typu 1, 2 a 3 A[..]→α[..],   A[..]→B[F..], a A[F..]→α[..], resp.

Derivace jsou podobné jako v a bezkontextová gramatika kromě indexového zásobníku připojeného ke každému neterminálnímu symbolu. Když produkce jako např. A[σ] → B[σ]C[σ], indexový zásobník z A je zkopírován do obou B a CPravidlo navíc může vložit indexový symbol do zásobníku nebo vyskočit jeho indexový symbol „nahoře“ (tj. Úplně vlevo).

Formálně je vztah ⇒ („přímá derivace“) definován na množině (N[F^*]∪T)^* „sentenciálních formulářů“ takto:

1. Li A[σ] → α[σ] je výroba typu 1, pak β A[φ] y ⇒ β α[φ] ypomocí výše uvedené definice. To znamená, že indexový zásobník na levé straně pravidla φ je zkopírován do každého neterminálu na pravé straně.
2. Li A[σ] → B[fσ] je tedy výroba typu 2 β A[φ] y ⇒ β B[fφ] y. To znamená, že indexový zásobník na pravé straně je získán ze zásobníku na levé straně φ tlačením F na to.
3. Li A[fσ] → α[σ] je tedy výroba typu 3 β A[fφ] y ⇒ β α[φ] y, opět pomocí definice α[σ]. To je první index F je vyskočeno ze zásobníku na levé straně, který je poté distribuován každému neterminálu na pravé straně.

Jako obvykle derivační vztah ∗⇒ je definován jako reflexní přechodné uzavření přímé derivace ⇒ jazyk L(G) = { w ∈ T^*: S ∗⇒ w } je sada všech řetězců koncových symbolů odvozitelných od počátečního symbolu.

Původní definice Aho

Historicky byl koncept indexovaných gramatik poprvé představen Alfred Aho (1968)^[3] Aho definoval indexovanou gramatiku jako n-tici (N,T,F,P,S) kde

1. N je konečný abeceda proměnných nebo neterminální symboly
2. T je konečná abeceda terminálních symbolů
3. F ⊆ 2^{N × (N ∪ T)*} je konečná množina tzv vlajky (každý příznak je sám o sobě souborem tzv indexové produkce)
4. P ⊆ N × (NF^* ∪ T)^* je konečná množina produkce
5. S ∈ N je počáteční symbol

Přímé derivace byly následující:

• Produkce p = (A → X₁η₁…X_kη_k) z P odpovídá neterminálu A ∈ N následuje jeho (případně prázdný) řetězec příznaků ζ ∈ F^*. V souvislosti s, y Aζ δ, přes p, odvozuje se od y X₁θ₁…X_kθ_k δ, kde θ_i = η_iζ -li X_i byl neterminál a prázdné slovo jinak. Staré vlajky A jsou tedy zkopírován ke každému novému terminálu produkovanému p. Každou takovou produkci lze simulovat příslušnými produkcemi typu 1 a 2 ve formálním formalismu Hopcroft / Ullman.
• Produkce indexu p = (A → X₁…X_k) ∈ F zápasy Afζ (vlajka F pochází z musí odpovídat prvnímu symbolu následujícímu za terminálem A) a zkopíruje zbývající řetězec indexu ζ každému novému terminálovi: y Afζ δ odvozuje se do y X₁θ₁…X_kθ_k δ, kde θ_i je prázdné slovo, když X_i je terminál a ζ když je to terminál. Každá taková výroba odpovídá produkci typu 3 v Hopcroftově / Ullmanově formalismu.

Tento formalismus je např. používá Hayashi (1973, s. 65-66).^[4]

Příklady

V praxi mohou hromady indexů počítat a pamatovat si, jaká pravidla byla použita a v jakém pořadí. Například indexované gramatiky mohou popsat kontextový jazyk slovních trojic { www : w ∈ {A,b}^* }:

S[σ]	→	S[fσ]	T[fσ]	→	A T[σ]
S[σ]	→	S[gσ]	T[gσ]	→	b T[σ]
S[σ]	→	T[σ] T[σ] T[σ]	T[]	→	ε

Odvození abbabbabb je tedy

S[] ⇒ S[G] ⇒ S[např] ⇒ S[fgg] ⇒ T[fgg] T[fgg] T[fgg] ⇒ A T[např] 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.

Jako další příklad lze uvést gramatiku G = ⟨ {S,T,A,B,C}, {A,b,C}, {F,G}, P, S ⟩ Vytváří jazyk { AⁿbⁿCⁿ: n ≥ 1}, kde je výrobní sada P skládá se z

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

Příkladem odvození je

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.

Oba příklady jazyků nejsou čerpací lemma.

Vlastnosti

Hopcroft a Ullman mají tendenci považovat indexované jazyky za „přirozenou“ třídu, protože jsou generovány několika formalizmy jinými než indexovanými gramatikami, viz.^[5]

• Aho je jednosměrný vnořené automaty zásobníku^[6]
• Fischer makro gramatiky^[7]
• Greibach automaty s hromadami hromádek^[8]
• Maibaum algebraická charakterizace^[9]

Hayashi^[4] zobecnil čerpací lemma naopak indexované gramatiky. Naopak Gilman^[10][11] dává "zmenšující se lemma" pro indexované jazyky.

Lineární indexované gramatiky

Gerald Gazdar definoval druhou třídu, lineární indexované gramatiky (LIG),^[14] tím, že bude vyžadováno, aby byl v každé produkci uveden nejvýše jeden neterminál jako příjem zásobníku,^{[poznámka 2]}vzhledem k tomu, že v běžné indexované gramatice dostávají všichni terminálové kopie zásobníku. Formálně je lineární indexovaná gramatika definována podobně jako běžná indexovaná gramatika, ale požadavky na formu produkce jsou upraveny tak, aby:

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

kde A, B, F, σ, α se používají jako výše, a β ∈ (N ∪ T)^* je řetězec neterminálních a koncových symbolů jako α.^{[Poznámka 3]} Rovněž přímý derivační vztah ⇒ je definován podobně jako výše. Tato nová třída gramatik definuje přísně menší třídu jazyků,^[15] který patří k mírně kontextově citlivé třídy.

Jazyk { www : w ∈ {A,b}^* } je generovatelný indexovanou gramatikou, ale ne lineární indexovanou gramatikou, zatímco oba { ww : w ∈ {A,b}^* } a { Aⁿ bⁿ Cⁿ : n ≥ 1} jsou generovatelné lineární indexovanou gramatikou.

Pokud jsou přijata původní i upravená produkční pravidla, zůstane jazyková třída indexovanými jazyky.^[16]

Příklad

Necháme-li σ označovat libovolnou sbírku symbolů zásobníku, můžeme definovat gramatiku pro jazyk L = {Aⁿ bⁿ Cⁿ | n ≥ 1 }^{[poznámka 4]} tak jako

S[σ]	→	tak jako[fσ] C
S[σ]	→	T[σ]
T[fσ]	→	T[σ] b
T[]	→	ε

K odvození řetězce abc máme kroky:

S[] ⇒ tak jako[F]C ⇒ v[F]C ⇒ v[]před naším letopočtem ⇒ abc

Podobně:

S[] ⇒ tak jako[F]C ⇒ aaS[ff]cc ⇒ aaT[ff]cc ⇒ aaT[F]bcc ⇒ aaT[]bbcc ⇒ aabbcc

Výpočtová síla

Lineárně indexované jazyky jsou podmnožinou indexovaných jazyků, a proto mohou být všechny LIG překódovány jako IG, čímž jsou LIG přísně méně výkonné než IG. Konverze z LIG na IG je relativně jednoduchá.^[17] Pravidla LIG obecně vypadají přibližně jako ${displaystyle X [sigma] o alfa Y [sigma] eta}$, modulovat push / pop část pravidla přepsání. Symboly ${displaystyle alpha}$ a ${displaystyle eta}$ představují řetězce terminálních a / nebo nekoncových znaků a jakýkoli jiný než koncový symbol v obou musí mít podle definice LIG prázdný zásobník. To je samozřejmě v rozporu s tím, jak jsou definovány IG: v IG musí mít non-terminály, jejichž zásobníky nejsou tlačeny nebo vysunuty z, přesně stejný zásobník jako přepsaný non-terminál. Nějak tedy musíme mít dovnitř neterminály ${displaystyle alpha}$ a ${displaystyle eta}$ které se navzdory neprázdným zásobníkům chovají, jako by měly prázdné zásobníky.

Zvažte pravidlo ${displaystyle X [sigma] o Y [] Z [sigma f]}$ jako příklad. Při převodu na IG je náhrada za ${displaystyle Y []}$ musí být nějaké ${displaystyle Y ^ {prime} [sigma]}$ který se chová přesně jako ${displaystyle Y []}$ bez ohledu na to, co ${displaystyle sigma}$ je. Abychom toho dosáhli, můžeme jednoduše mít dvojici pravidel, která platí jakákoli ${displaystyle Y ^ {prime} [sigma]}$ kde ${displaystyle sigma}$ není prázdný a vysunuje symboly ze zásobníku. Když je pak zásobník prázdný, lze jej přepsat na ${displaystyle Y []}$.

${displaystyle Y ^ {prime} [sigma f] o Y ^ {prime} [sigma]}$

${displaystyle Y ^ {prime} [] o Y []}$

Obecně to můžeme použít k odvození IG z LIG. Takže například pokud LIG pro jazyk ${displaystyle {a ^ {n} b ^ {n} c ^ {n} d ^ {m} | ngeq 1, mgeq 1}}$ je následující:

${displaystyle S [sigma] o T [sigma] V []}$

${displaystyle V [] o d ~ | ~ dV []}$

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

${displaystyle U [sigma f] o bU [sigma]}$

${displaystyle U [] o epsilon}$

Senciální pravidlo zde není pravidlem IG, ale pomocí výše uvedeného algoritmu převodu můžeme definovat nová pravidla pro ${displaystyle V ^ {prime}}$, změna gramatiky na:

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

${displaystyle V ^ {prime} [sigma f] o V ^ {prime} [sigma]}$

${displaystyle V ^ {prime} [] o V []}$

${displaystyle V [] o d ~ | ~ dV []}$

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

${displaystyle U [sigma f] o bU [sigma]}$

${displaystyle U [] o epsilon}$

Každé pravidlo nyní odpovídá definici IG, ve které všechny terminály na pravé straně pravidla přepisu obdrží kopii zásobníku přepsaného symbolu. Indexované gramatiky jsou proto schopné popsat všechny jazyky, které mohou lineárně indexované gramatiky popsat.

Vztah k jinému formalizmu

Vijay-Shanker a Weir (1994)^[18] ukazuje, že lineární indexované gramatiky, Kombinované kategoriální gramatiky, Stromové gramatiky, a Vedoucí gramatiky všichni definují stejnou třídu řetězcových jazyků. Jejich formální definice lineárních indexovaných gramatik^[19] se liší od výše.^{[je zapotřebí objasnění ]}

LIG (a jejich slabě ekvivalenty ) jsou přísně méně expresivní (což znamená, že vytvářejí vlastní podmnožinu) než jazyky generované jinou rodinou slabě ekvivalentního formalismu, mezi něž patří: LCFRS, MCTAG, MCFG a minimalistické gramatiky (MG). Druhá rodina může být (také) analyzována polynomiální čas.^[20]

Distribuované indexové gramatiky

Další forma indexovaných gramatik zavedená Staudacherem (1993),^[12] je třída gramatik s distribuovaným indexem (DIG). To, co odlišuje DIG od Aho's Indexed Grammars, je šíření indexů. Na rozdíl od Aho IG, které během operace přepisování distribuují celý zásobník symbolů na všechny neterminály, DIG rozdělují stack na subacky a distribuují subacky na vybrané non-terminály.

Obecné schéma pravidel pro binarně distribuující pravidlo DIG je forma

X[F₁...F_iF_i+1...F_n] → α Y[F₁...F_i] β Z[F_i+1...F_n] γ

Kde α, β a γ jsou libovolné koncové řetězce. Pro ternárně distribuující řetězec:

X[F₁...F_iF_i+1...F_jF_j+1...F_n] → α Y[F₁...F_i] β Z[F_i+1...F_j] y Ž[F_j+1...F_n] η

A tak dále pro vyšší počet neterminálů na pravé straně pravidla přepsání. Obecně platí, že pokud existují m non-terminály na pravé straně pravidla přepsání je zásobník rozdělen m způsoby a distribuovány mezi nové neterminály. Všimněte si, že existuje speciální případ, kdy je oddíl prázdný, což z pravidla dělá pravidlo LIG. Jazyky distribuovaného indexu jsou proto nadmnožinou jazyků s lineárním indexem.

Viz také

• Chomského hierarchie
• Indexovaný jazyk

Poznámky

Reference

externí odkazy

• Kapitola „NLP v Prologu“ o indexovaných gramatikách a jazycích