8.7. A környezetfüggő nyelvek tulajdonságai

A környezetfüggő nyelvek halmaza tartalmaz több olyan nyelvet is, amely nem tesz eleget a konstansnövekmény elvének: pl. : {a p | p prímszám }, {a k | k négyzetszám } vagy {a k | k=2 i valamely i természetes számra }. A környezetfüggő nyelvek osztályában szereplő nyelvekre így nincs általános pumpáló/iterációs lemma.

8.7.1. A szóprobléma

A környezetfüggő nyelvekre a szóprobléma eldönthető, vagyis meg lehet adni olyan algoritmust, ami véges idő alatt eldönti, hogy egy adott szó szerepel-e az adott monoton nyelvtan által generált nyelvben. Mivel a mondatforma hossza egy levezetés során nem csökkenhet, adott hosszig generálható, és így felsorolható az összes generálható mondatforma. Így ha az adott w szó hossza n, akkor n+1 hosszig felsorolva (levezetve) az összes levezethető szót eldönthető, hogy w eleme-e a generált nyelvnek, formálisan tehát:

68. Tétel. Bármely G=(N, T, S, H) környezetfüggő grammatikáról és tetszőleges wT * szóról eldönthető, hogy wL(G) fennáll-e.

Bizonyítás. Vegyük észre, hogy tetszőleges 1-típusú G=(N, T, S, H) nyelvtan esetén az esetleges S → λ szabálytól eltekintve minden egyes szabály baloldalának hossza legfeljebb akkora mint a jobboldalé. Ráadásul, tekintettel arra, hogy az S → λ szabály fellépésekor S nem fordulhat elő egyetlen szabály jobboldalán sem, minden olyan esetben, amikor egy SW 1⇒…⇒W t w levezetés első lépésében nem az S → λ szabályt alkalmazzuk, az S → λ szabályt egyetlen további lépésben sem tudjuk alkalmazni. Tehát egy SW 1⇒…⇒W t w levezetés vagy Sλ alakú, vagy pedig |S| ≤ |W 1| ≤ … ≤ |W t | ≤ |w| fenn fog állni. Tehát a levezetés egyetlen lépése sem eredményezhet |w|- nél hosszabb (NT)*- beli szót (mondatformát). Nyilvánvaló, hogy ha egy szó G- ben levezethető, akkor levezethető oly módon, hogy a levezetés során nincs ismétlődő mondatforma. Képletben, ha (S=)W 0W 1⇒…⇒W t w mellett W i =W j telesül valamely 0 ≤ i<j ≤ t párra (a levezetés utolsó lépéseként adódó T *- beli szó a levezetés definíciója értelmében nem ismétlődhet), akkor (S=)W 0⇒…⇒W i W j+1⇒…⇒W t w is fennáll (ahol j=t esetén a W j+1⇒…⇒W t lépések értelemszerüen elmaradnak). Az ilyen ismétlődéseket nem tartalmazó levezetések száma véges. Nevezetesen, (eltekintve az egy lépéses Sλ esettől) nem nagyobb mint a NT ábécé feletti, |w|- nél nem hosszabb szavakból álló ismétlődés nélküli szósorozatok hossza, vagyis Vagyis, ha el akarjuk dönteni a wL(G) kérdést, w=λ esetén meg kell vizsgálnunk, hogy S → λ szerepel-e a szabályok között, wλ esetén pedig meg kell vizsgálnunk azt, hogy az ismétlődés nélküli, |w|- nél hosszabb szavakat nem tartalmazó (véges sok, -nál nem nagyobb számú) levezetések közt van-e olyan, melynek az utolsó lépéseként w adódik. Ha igen, wL(G), különben pedig wL(G). Ezzel bizonyításunk végéhez értünk. ∎

Itt hívjuk fel a figyelmet, hogy a rekurzió-mentes normálformájú nyelvtanok esetén eleve kizárható, hogy ismétlődő mondatforma lépjen fel egy levezetés során. Ha a lehetséges levezetéseket a mesterséges intelligenciában állapottér gráfnak nevezett gráffal reprezentáljuk, akkor a rekurzió-mentes normálforma esetén a gráf tehát körmentes lesz, így akár egy visszalépéses kereső, aminek lépésszámkorlátja a mondatforma hosszának függvénye, is képes a szóprobléma eldöntésére. A szóproblémára a környezetfüggő esetben nincs (nem ismert) hatékony algoritmus, a probléma, hogy tetszőleges környezetfüggő nyelvet generáló (akár valamely ismertetett normálformában levő) nyelvtan generál-e egy adott szót általánosan PSPACE-teljes probléma (vagyis hiába elég legfeljebb négyzetes tár a determinisztikus, illetve lineáris tár a nemdeterminisztikus esetben, a probléma a legbonyolultabb problémák közt van, melyek megoldásához polinomiális tárra van szükség (lásd Bonyolultsági osztályok)).

8.7.2. Zártsági tulajdonságok

69. Tétel. A környezetfüggő nyelvek osztálya zárt a reguláris műveletekre.

Bizonyítás. Konstruktív: legyen adott L 1 és L 2 környezetfüggő nyelvek. Legyen adva (N 1, T, S 1, H 1) és (N 2, T, S 2, H 2) két Kuroda normálformájú nyelvtan, amely L 1 és L 2 üresszómentes részét generálja, ahol N 1 és N 2 diszjunktak.

Konstruáljuk meg a (N 1N 2∪{S}, T, S, H) nyelvtant, ahol S új szimbólum, nem szerepel sem N 1, sem N 2 elemei közt, H pedig a következőképpen definiált: H=H 1H 2∪{S  → S 1, S  → S 2}, illetve legyen S → λ benne a H- ban pontosan akkor ha az L 1 és L 2 nyelvek legalább egyike tartalmazza az üresszót. Könnyen belátható, hogy az új nyelvtan megfelel a monoton nyelvtan definíciójának és éppen L 1 és L 2 unióját generálja.

Tekintsük most a (N 1N 2∪{S}, T, S, H) nyelvtant, ahol S új szimbólum, nem szerepel sem N 1, sem N 2 elemei közt, H pedig a következőképpen definiált:

H=H 1H 2∪{SS 1 S 2}, ha sem L 1 sem L 2 nem tartalmazza az üresszót,

H=H 1H 2∪{SS 1 S 2, SS 1} ha L 2 tartalmazza az üresszót, de L 1 nem,

H=H 1H 2∪{SS 1 S 2, SS 2} ha L 1 tartalmazza az üresszót és L 2 nem,

H=H 1H 2∪{SS 1 S 2, SS 1, S  → S 2, S  → λ} ha az L 1 és L 2 nyelvek mindegyike tartalmazza az üresszót.

Könnyen belátható, hogy az új nyelvtan megfelel a monoton nyelvtan definíciójának és éppen L 1 és L 2 konkatenációját generálja. Legyen most L környezetfüggő nyelv és legyen adva (N 1, T, S 1, H 1) és (N 2, T, S 2, H 2) két Kuroda normálformájú nyelvtan, amelyek L üresszómentes részét generálják, ahol N 1 és N 2 diszjunktak.

Tekintsük most a (N 1N 2∪{S, S '}, T, S, H) nyelvtant, ahol S és S ' új szimbólumok, egyikük sem szerepel sem N 1, sem N 2 elemei közt, és H=H 1H 2∪{S  → λ, SS 1, SS 1 S 2, SS 1 S 2 S ', S ' → S 1, S ' → S 1 S 2, S ' → S 1 S 2 S '}. Az így megkonstruált nyelvtan monoton és az L * nyelvet generálja. ∎

70. Tétel. A környezetfüggő nyelvek osztálya zárt a halmazműveletekre: az unió műveleten kívül a metszet és komplementer műveletekre nézve is.