8.4. Levezetési gráfok, levezetési fák a környezetfüggő nyelvtanokhoz

A környezetfüggő nyelvek esetén is ábrázolhatjuk a megfelelő nyelvtanokban a levezetéseket gráfok segítségével. Monoton esetben vegyük a következő példát:

8.9. példa - Levezetési gráf monoton esetben

Legyen ({S, A, B, C, D, E, F, G}, {a, b}, S, H) egy monoton nyelvtan, ahol H={SD A B E, SD A B E F, F → G G, FG G F, G → b, a GG a, B Ea a, A aa a, D aa a, A BB A A, D BD C, C AA A C, C EB E}. A következő ábrán egy példaleveztést láthatunk: az a a a b a a b b a a b b b szó levezetési gráfja:


A monoton nyelvtanok esetén a levezetési gráf páros gráf, kétféle csúcstípussal: a levezetési fáknál szokásos betűcímkézett (nemterminális, terminális, illetve csak az üresszó levezetése esetén a λ ); illetve szabálycímkézett csúcsok (itt a címkéket általában elhagyhatjuk, hiszen a befutó és kifutó élek által mutatott csúcsok címkéiből egyértelműen felírható az alkalmazott levezetési szabály).

Környezetfüggő nyelvtan esetén ez a gráf nagyon redundáns, ugyanis az összes környezetszimbólum megismétlésre kerül. Ezen segíthetünk, ha nem ismételjük meg őket, hanem speciális "környezet-élek" (illetve környezetdoboz) segítségével jelöljük meg a gráfban, hogy az adott nemterminális azért helyettesíthető a megadott módon, mert a megfelelő környezet rendelkezésre áll. Ily módon csak a hagyományos levezetési fáknál megszokott csúcstípusra van szükségünk, viszont kétféle éltípusra. Példaként az A B C DA B S B D szabály kétféle ábrázolása látható a következő ábrán:

8.10. példa - Levezetési gráf környezetfüggő nyelvtanban

Legyen adott a G=({S, A, B, C, D, E, F, G, I, J, K, L, M, O, P}, {a, b, c}, S, H) környezetfüggő nyelvtan, ahol a H szabályhalmaz:


H={Sa S A, Sb S B, a b Sa b C E, b a S Ab a D F A, E AE G, E GI G, I GI E, I EA E, E BE J, E JK J, K JK E, K EB E, F AF L, F LM L, M LM F, M FA F, F BF O, F OP O, P OP F, P FB F, C AC E, C BC F, D AD E, D BD F, Ca, D → b, E → a, F  → b}.

A következő ábrán egy levezetést láthatunk.

Még speciálisabb a helyzet, ha csak Penttonen normálformájú nyelvtant engedünk meg, ekkor a környezet mindig csak egy baloldali szomszédos nemterminális lehet. Erre az esetre definiáljuk formálisan a környezetfüggő "levezetési fát":

20. Definíció. Legyen G=(N, T, S, H) Penttonen normálformájú nyelvtan. Egy q mondatformához a levezetési fát a következőképpen írhatjuk le: irányított csúcscímkézett (a címkék az (NT) halmazbeliek) gráf. A levezetési élek (folytonosak az ábrán) hagyományos értelemben vett fa szerkezetet adnak a gráfnak (pontosan ahogyan a környezetfüggetlen esetben). A gyökér címkéje S. Minden nem levél elem címkéje nemterminális. A levélelemek címkéit balról jobbra összeolvasva q- t kapjuk. Legyen A egy nem levélelem címkéje és legyen r a gyerekeinek a címkéi balról jobbra összeolvasva. Ekkor a következő feltételeknek kell teljesülnie:

- Ha környezetél (az ábrán szaggatott) nem érkezik be az adott A címkéjű csúcsba, akkor A → r alakú leveztési szabályt tartalmaz a G nyelvtan H szabályrendszere.

- Ha pontosan egy környezetél érkezik az adott A címkéjű csúcsba, akkor legyen annak a balszomszéd ágon levő csúcsnak ahonnan a környezetél indul a címkéje C, ekkor C AC rH. ★

Minden környezetél két szomszédos ágat köt össze (balról jobbra), vagyis pontosan akkor mehet egy α (C címkéjű) csúcsból környezetél egy β (A címkéjű) csúcsba, ha a levezetési fában γ az a legalacsonyabban levő csúcs, amely mind az α, mind a β csúcsot dominálja (a legutolsó közös őse mindkettőnek); α a γ baloldali részfájának legjobboldali ágán van, míg β a γ jobboldali részfájának legbalodali ágán helyezkedik el (lásd a következő ábrát is). Ezen kívül a következő feltételnek is teljesülnie kell: a δ csúcs egyik őséből sem indulhat környezetél az ε csúcs egyik leszármazottjához sem, ha δ csúcsból indul környezetél az ε csúcsba. Egy csúcsból több környzezetél is indulhat, de maximum egy érkezhet.

8.11. példa - Környezetfüggő levezetési fa

Legyen adott a ({S, A, B, C, D, E, F, G, I, J, K, L, M, O}, {a, b, c}, S, H) környezetfüggő nyelvtan Penttonen normálformában:


H={SA G, GB C, AI J, JD E, E BE E, E CE K, KF L, DI M, MA B, B EB B, B FB O, OC L, Aa, B → b, C → c, D  → a, Eb, F → c, I → a, L  → c}.

Egy példalevezetést láthatunk a következő ábrán.

Figyeljük meg hogy a levezetési gráf szerkezete milyen egyszerű, a struktúrája az ebben a fejezetben korábban ismertetett gráfoknál tényleg sokkal közelebb áll a fához.

Az előzőek alapján, kicsit pongyolán, a következő feltételt mondhatjuk a környezetélekre: egy környezetél nem metszhet semmilyen más élt a gráfban.

Úgy is felfoghatjuk, hogy egy adott ágon levő csúcsra a balszomszéd ág "árnyékot" vet, azok a nemterminálisok jöhetnek szóba környezetél indítására egy adott csúcsba, melyeknek ott lehet az árnyéka. Egy levezetési fát befejezettnek nevezünk, ha minden levéleleme terminális.

8.4.1. Legbaloldalibb levezetés és átfogalmazása

Mint ahogy a környezetfüggetlen nyelvtanok esetén láttuk a legbalodali levezetés létezése fontos szerepet játszott, hiszen a veremautomata egy adott levezetési fa legbalodali levezetését szimulálta. A legbaloldalibb levezetést ott mondatformára definiáltuk, mindig a benne szereplő első (vagyis legbalodali) nemterminálisra alkalmaztunk egy alkalmazható levezetési szabályt. A környezetfügetlen esetben ez a definíció egybeesik azzal, hogy a levezetési fában mindig a legbaloldalibb még be nem fejezett ágon folytatjuk a levezetést, vagyis a fa továbbépítését.

Ismert, hogy bármilyen generatív nyelvtan (tehát bármilyen 0. típusú nyelvtan) esetén, ha csak legbaloldalibb levezetést engedünk meg (vagyis mindig csak olyan szabályt alkalmazhatunk, ami a legelső szereplő nemterminálisnál alkalmazható, és ott alkalmazzuk), akkor a generált nyelv környezetfüggetlen lesz.

Ezek alapján tehát ahhoz, hogy a generáló ereje egy (nem környezetfüggetlen) nyelvtannak ne csökkenjen, szükséges a legbalodali levezetés fogalmának általánosítása (átfogalmazása).

21. Definíció. Legbaloldalibb levezetésnek (vagy legbalodali konstrukciónak) nevezzük környezetfüggő esetben a (Penttonen normálformájú nyelvtan esetén a) levezetési fa felépítésének legbalodali módját: minden lépésben a legbalodali levélelemnél folytatjuk a leveztést (a levezetési fa megkonstruálását) innen induló levezetési él(ek) bevezetésével, esetlegesen felhasználva egy a gráfban már jelenlevő baloldali szomszédos csúcsot környezetél segítségével (a korábbiakban leírt feltételek betartásával). ★

65. Tétel. Legyen adott egy G=(N, T, S, H) Penttonen normálformájú nyelvtan. Egy w szóhoz pontosan akkor létezik befejezett levezetési fa, illetve legbaloldalibb levezetés, ha wL(G).