3.4. Problémakörök

Az alábbiakban áttekintjük, hogy a jegyzetben a különböző típusú nyelvekkel kapcsolatban mi is érdekel minket. Általában adott nyelvosztályra illusztratív példát is adunk, valamint bizonyítjuk a Chomsky-féle hierarchia szigorúságát. Egyes nyelvosztályok tulajdonságai erősen különbözhetnek egymástól. Ebben a jegyzetben általában a következő tulajdonságokat fogjuk vizsgálni.

3.4.1. Normálformák (Normálalakok)

A monoton és a 0-típusú nyelvtanokban a terminális szimbólumokat is átírhatjuk, itt a terminális és nemterminális szimbólumoknak a megkülönböztetése inkább csak azért fontos, hogy lássuk, készen vagyunk-e a levezetéssel (csak terminálisokból áll az aktuális modatforma), vagy van benne nemterminális, ahol még szabályt kell alkalmaznunk ha be akarjuk fejezni a levezetést (az más kérdés, hogy nem feltétlenül lehet befejezeni minden levezetést). A továbbiakban belátjuk, hogy minden nyelvtannal van olyan ekvivalens, amiben terminális szimbólumokat nem írunk át, vagyis a terminális szimbólumok tényleg terminálisak, véglegesen ott maradnak a levezetésben, míg a változókat természetesen át kell írnunk egy termináló levezetés során.

Azt mondjuk, hogy egy nyelvtan (terminális) normális alakban van, ha a helyettesítési szabályokban terminális jelek csak A → a ( AN, aT) alakú szabályokban fordulnak elő.

5. Tétel. Minden G=(N, T, S, H) nyelvtanhoz megadható egy vele ekvivalens G '=(N ', T, S, H ') nyelvtan úgy, hogy az általuk generált nyelvek megegyeznek: L(G)=L(G '), továbbá minden H '- beli szabály, amely terminális jelet tartalmaz, A → a alakú, ahol AN, aT. Emellett G ' nyelvtan ugyanolyan típusú, mint G, kivéve, ha G reguláris, vagy lineáris.

Bizonyítás. Minden egyes aT terminális jelhez vezessünk be új D a N nemterminálist, és legyen N '=N∪{D a |aT}. A H '- beli szabályokat adjuk meg úgy, hogy a H szabályaiban minden nem A → a ( AN, aT) alakú szabályban az a terminális helyére a megfelelő D a változót írjuk. Ezenkívül a H '- beli szabályok közé még felvesszük az D a a alakú új szabályokat (minden aT esetén). Az így kapott H ' nyilván rendelkezik a kívánt tulajdonsággal.

Az ekvivalencia bizonyításához először megmutatjuk, hogy L(G)⊆L(G '). Legyen w=a 1 a 2a k L(G). Ekkor a G ' nyelvtanban levezethető a megfelelő D 1 D 2D k nemterminális szó, és az D a a szabályok segítségével ebből a w- t megkaphatjuk. Ha továbbá λL(G), akkor a G- ben a megfelelő szabályok alkalmazásával ugyancsak megkapjuk λ- t.

Most lássuk be, hogy L(G ')⊆L(G). Legyen h:(N '∪T)* → (NT)* homomorf leképezés a következő módon értelmezve:

- h(D a )=a, (minden aT esetén) illetve

- h(r)=r, r∈(NT).

Ekkor bármely két p, q∈(N '∪T)* szóra a p G ' q relációból következik, hogy vagy h(p)=h(q), vagy h(p)⇒ G h(q). Ha ugyanis a G nyelvtanban a p- ből a q úgy adódik, hogy valamelyik D a a szabályt alkalmazzuk, akkor h(p)=h(q). Ha pedig H '- nek egy olyan szabályát alkalmazzuk, amelyet egy H- beli szabályból nyertünk, akkor nyilván h(p)⇒ G h(q). Tehát mindkét esetben p G ' q relációból a h(p)⇒ G h(q) következik. Legyen most pL(G '), akkor S G p, mert S=h(S)⇒ G ' h(p)=p, amivel a tételt bebizonyítottuk. ∎

A továbbiakban különböző típusú nyelvtanokhoz ennél jóval erősebb megkötéseket tartalmazó normálformákat is fogunk bemutatni. Az egyik fontos kérdés az lesz, hogy mennyi korlátozást tehetünk adott nyelvtanosztály szabályaira, ahhoz, hogy továbbra is generálhassuk a nyelvosztály üresszómentes nyelveit, azaz minden adott típusú nyelvtannal legyen ekvivalens amire a korlátozás fennáll.

3.4.2. Levezetések szerkezete

Mivel a levezetés központi fogalom egy nyelvtan által generált nyelv előállításában, érdemes megvizsgálnunk a lehetséges levezetések szerkezetét. A levezetéseket gráfokkal fogjuk ábrázolni, a levezetési gráf alakja (pl. fa) nemcsak szemléletes, de elméleti és gyakorlati fontossággal is bír. Mindez szorosan összefügg a következőkben ismertetendő szóproblémával is.

3.4.3. A szóprobléma és a szintaktikai elemzés

Ha adott egy nyelv (pl. nyelvtan segítségével definiálva), akkor annak eldöntését, hogy egy adott w szó benne van-e a (generált) nyelvben, az adott nyelvhez (nyeltanhoz) tartozó szóproblémának hívjuk. Általában nemcsak egy konkrét nyelv érdekel minket, hanem az hogy adott nyelvosztály esetén hogyan oldható meg (illetve megoldható-e egyáltalán) a szóprobléma. Ezt eldönteni, illetve erre hatékony algoritmust megadni érdekes és fontos része a formális nyelvek elméletének.

Ha nem csak igen/nem választ várunk el, hanem igen válasz esetén azt is hogy egy lehetséges levezetést is megadjon az algoritmus, akkor szintaktikai elemzésről beszélünk.

A mesterséges intelligenciában szokásos módon állapottér gráffal szemléltethetjük az összes lehetséges levezetést egy adott nyelvtanban: a gyökér csúcs címkéje az S mondatszimbólum, és bármely csúcsból úgy származtathatjuk annak "utódait", hogy a csúcs címkéjében levő mondatformára valamely levezetési szabályt alkalmazzuk valamely alkalmas helyen. Ilyenkor grafikusan irányított élt húzunk az adott csúcsból abba amelyben, mint címke, az új mondatforma található. Mivel bármely (véges) mondatforma esetén csak véges sok szabály és véges sok helyen alkalmazható, így felsorolhatjuk az összes olyan mondatformát, amaly létrejöhet a már meglevő mondatformákból egy lépésben. Ez alapján a gráf alapján kereshetünk választ a formális nyelvek elméletének egyik legfontosabb problémájára, a szóproblémára: Ezt a problémát a következő formában is megfogalmazhatjuk: egy adott L nyelv és egy adott w szó esetén milyen feltételek mellett dönthető el algoritmikusan az, hogy wL reláció teljesül-e vagy sem. Könnyű észrevenni, hogy végtelen nyelvek esetén a gráfnak végtelen sok levél eleme van, sőt azok mélysége (vagyis a legrövidebb, a gyökércsúcsból induló és az adott levélcsúcshoz tartó irányíott út, vagyis a legrövidebb levezetés, hossza) sem korlátos. A szóprobléma eldöntése ezeknek a levélelemeknek az egyenkénti megvizsgálását jelentené, ami általában algoritmikusan nem megoldható. Azonban speciális esetekben, például a szó hosszát nem csökkentő nyelvtanok (monoton nyelvtanok) esetén a levezetési gráfoknak csak egy véges részgráfját kell a vizsgálatunkba bevonni, ami garantálja a probléma algoritmikus eldönthetőségét.

3.4.4. Nyelvosztályok és automataosztályok kapcsolata

Egyik központi feladatunk a különböző nyelvosztályok elfogadására alkalmas automataosztályok feltérképezése, vagyis, hogy adott nyelvosztályba tartozó nyelveket milyen automatákkal lehet elfogadni. Néhány nyelvosztály esetén egyéb speciális, alternatív, a nyelvosztálynak megfelelő leírást is fogunk adni a benne szereplő nyelvekre.

3.4.5. Nyelvosztályok tulajdonságai

Az, hogy egy adott formális nyelv milyen nyelvosztályba tartozik, nem dönthető el minden egyes nyelv esetén könnyen. Néhány nyelvosztály esetén segítséget jelenthet, ha olyan tulajdonságot tudunk, ami a nyelvosztály minden egyes nyelvére teljesül. Ha sikerül bizonyítani, hogy az adott nyelvre ez a tulajdonság nem teljesül, akkor nem tartozhat az adott nyelvcsaládhoz.

Egy adott nyelvosztály tulajdonságait vizsgálva érdekes információt hordoznak a zártsági tulajdonságok.

Azt mondjuk, hogy egy nyelvosztály zárt egy nyelvműveletre nézve, vagyis a művelet nem vezet ki az adott nyelvosztályból, ha bármely a nyelvosztályhoz tartozó (ugyanazon ábécé felett értelmezett) nyelvekre a műveletet elvégezve az így létrejött (új) nyelv ugyancsak az adott nyelvcsaládhoz tartozik. Ha vannak olyan nyelvei az adott nyelvosztálynak, amikre a létrejövő nyelv már nem eleme az adott osztálynak, akkor a nyelvosztály nem zárt az adott műveletre nézve, úgy is mondhatjuk, hogy az adott művelet kivezet az adott nyelvosztályból. Fontos kérdés, hogy egy adott nyelvosztály zárt-e egyes nyelvműveletekre nézve.

Minden nyelvosztálynál fogjuk vizsgálni a konkatenáció, Kleene-csillag, unió, metszet és komplementerképzés műveleteket.

3.4.6. Speciális alosztályok

Több fontos nyelvosztály esetén speciális alosztályokat is be fogunk mutatni, amelyek általában speciálisan megszorított nyelvtanokkal generálhatóak, vagy speciálisan megszorított automatákkal fogadtathatóak el.