10. fejezet - Nyelvtanrendszerek (Grammatikarendszerek)

A klasszikus formális nyelvek és automaták elméletben a nyelvek és az automaták klasszikus számítási eszközöket modelleztek. Ezek központosítottak voltak – a számításokat egy központi ágens (egység) végezte. Így a klasszikus formális nyelvek elmélete szerint egy nyelvet egy grammatika készít, vagy egy automata ismer fel. A modern számítástudományban az elosztott számítások fontos szerepet játszanak. Az elosztott rendszerek megfigyelése számítógépes hálózatokban, elosztott adatbázisokban, stb., olyan fogalmakhoz vezetett, mint párhuzamosság, konkurencia és kommunikáció. A nyelvtanrendszerek elméletében vizsgált formális rendszerek az elosztott számítások szintaktikai modelljei, melyekben ezek a fogalmak értelmezhetőek és tanulmányozhatóak.

A nyelvtanrendszer nyelvtanok egy csoportja, amelyben a nyelvtanok meghatározott protokoll szerint közösen dolgoznak egyetlen nyelv létrehozásán. Több indok szól ilyen generatív mechanizmus létrehozása mellett, többek közt, az elosztás modellezése, a generáló erő növelése, a (leírási) bonyolultság csökkentése. A kritikus rész itt az együttműködési protokoll. A nyelvtanrendszerek elméletét tekinthetjük egyfajta formális együttműködési protokollok elméletének. A központi probléma a meghatározott protokollokat használó rendszerek működésének leírása, és a különböző protokollok a megfigyelt rendszerek különböző tulajdonságaira gyakorolt hatásának elemzése.

A nyelvtanrendszerek kétféle alapvető osztályba sorolhatóak: szekvenciálisak vagy párhuzamos működésűek, ezek alapján megkülönböztetjük a kooperatív elosztott (angolul: cooperating distributed, röviden CD) és a párhuzamos kommunikáló (angolul: parallel communicating, röviden PC) rendszereket. Ebben a fejezetben röviden ismertetjük ezen rendszereket.

10.1. Nyelvtanok kooperatív elosztott rendszerei – CD nyelvtanrendszerek

(Cooperating Distributed Grammar Systems – CD grammar systems)

A nyelvtanok kooperatív elosztott rendszere szekvenciális működésű: egymást követő lépéseken alapul. A rendszert alkotó összes nyelvtan egy adott, közös mondatformán dolgozik. Minden egyes időpillanatban csak egyetlen nyelvtan aktív, ami átírja az aktuális mondatformát. Azokat a kérdéseket, hogy melyik komponens lehet aktív egy adott pillanatban, és mikor válik inaktívvá egy aktív (műveleteket végző) nyelvtan – az aktuális mondatformát átadva a többi, a rendszert alkotó nyelvtan valamelyikének – az együttműködési protokoll határozza meg.

Példák megállási feltételekre (inaktívvá válásra). Egy lépés egy levezetési szabály alkalmazását jelenti.

  • Az aktív komponensnek pontosan k lépést kell végrehajtania.

  • Az aktív komponensnek legalább k lépést kell végrehajtania.

  • Az aktív komponensnek legfeljebb k lépést kell végrehajtania.

  • Az aktív komponensnek annyi lépést kell végrehajtania, amennyit tud.

  • Az aktív komponens tetszőleges számú lépést hajthat végre.

A rendszer által generált nyelv az így generált terminális szavak nyelve lesz.

A CD nyelvtanrendszerek felépítése egy iskolai tábla használatához hasonlítható, ha azt probléma-megoldáshoz használják. A közös mondatforma az iskolai tábla tartalma (a közös adatszerkezet, amely a megoldandó probléma aktuális állapotát tartalmazza). A nyelvtanok a tudásforrások (ágensek, feldolgozó egységek, eljárások, különböző képességű diákok, stb.) amelyek hozzájárulnak a probléma megoldásához azzal, hogy megváltoztatják a tábla tartalmát a képességeiknek megfelelően. Az együttműködési protokollban van kódolva a tudásforrások irányítása (például a sorrend, amelyben a tudásforrások hozzájárulhatnak a megoldáshoz).

25. Definíció. A (környezetfüggetlen) nyelvtanok kooperatív elosztott rendszere egy n rendű (n ≥ 1) rendszer, felépítése: C D=(N, T, S, H 1, …, H n ) Ahol N és T diszjunkt ábécék, V=NT, SN, és H 1, …, H n pedig környezetfüggetlen levezetési szabályok véges halmazai. Az N elemei a nemterminálisok, a T elemei a terminálisok; S a mondatszimbólum, H 1, …, H n pedig a rendszer komponensei. ★

Az iskolai tábla példájánál maradva a komponensek a táblánál a problémát megoldó ágenseknek felelnek meg. A szabályok megfeleltethetőek az ágensek által végrehajtott műveleteknek, ezek eredménye lehet a tábla tartalmának, vagyis a mondatformának a megváltoztatása.

  • Az S axióma a táblán található probléma kezdeti állapotának formális megfelelője.

  • A T ábécé tartalmazza azokat a betűket, amelyek megfelelnek az olyan tudás-részleteknek, amelyek elfogadhatóak megoldásként, illetve a megoldás részeiként.

  • A nemterminálisok "kérdésekként" értelmezhetőek, amelyekre választ keresünk. Egy komponens által feltett kérdések, és egy másik által átírtak felfoghatóak az egyik komponens által feltett kérdésnek, amelyre egy másik komponens válaszol. Így a komponensek kommunikálhatnak a megoldás pillanatnyi állapotába illesztett üzenetekkel, mintegy a mondatformába (a tábla tartalmába) kódolva.

Ha konkrétan olyan grammatikát akarunk definiálni, ami egy CD nyelvtanrendszer része, akkor felírhatjuk a C D- t ilyen formában: C D=(N, T, S, G 1, …, G n ), ahol G i =(N, T, S, H i ), 1 ≤ i ≤ n.

26. Definíció. Legyen C D=(N, T, S, H 1, …, H n ) egy CD nyelvtanrendszer. Ekkor

  1. Minden egyes i∈{1, …, n}- re az i- edik komponens * módbeli levezetését ⇒ i *- gal jelöljük, és a következőképpen definiáljuk: p i * q akkor és csakis akkor, ha p G i * q.

  2. Minden egyes i∈{1, …, n}- re az i- edik komponens termináló levezetését ⇒ i t - vel jelöljük, és a következőképpen definiáljuk: p i t q akkor és csakis akkor, ha p i * q és nincs olyan r∈(NT)* amire q i r (rq).

  3. Minden egyes i∈{1, …, n}- re az i- edik komponens k lépéses levezetését p i =k q- val jelöljük, és a következőképpen definiáljuk: p i =k q akkor és csakis akkor, ha van olyan r 1, …, r k+1∈(NT)* amely p=r 1, q=r k+1, és minden egyes j- re ( 1 ≤ j ≤ k ), r j i r j+1.

  4. Minden egyes i∈{1, …, n}- re az i- edik komponens legfeljebb k lépéses levezetését p i  ≤ k q- val jelöljük, és a következőképpen definiáljuk: p i  ≤ k q akkor és csakis akkor, ha p i =j q valamely j ≤ k értékre.

  5. Minden egyes i∈{1, …, n}- re az i- edik komponens legalább k lépéses levezetését p i  ≥ k q- val jelöljük, és a következőképpen definiáljuk: p i  ≥ k q akkor és csakis akkor, ha p i =j q valamely j ≥ k értékre.

A *- módbeli levezetés, p i * q, olyan működési formát jelöl, amelyben az ágensek addig dolgoznak a táblánál, ameddig akarnak. A t- módbeli levezetés annak a stratégiának felel meg, amelyben egy ágensnek addig kell hozzájárulnia a megoldási folyamathoz a táblánál, ameddig csak tud (maximálisan kihasználva a hatáskörét). Akkor beszélünk =k levezetési módról, ha k egymást követő közvetlen levezetési lépésben használjuk fel az i- edik komponens szabályait, ez k műveletet jelent egy ágens számára a táblánál. A  ≥ k levezetési mód időkorlátnak felel meg, mivel egy ágens maximum k- lépést hajthat végre. A  ≥ k levezetési módban legalább k lépést kell végrehajtania az ágensnek. A levezetési módok a fentiek alapján feltételeznek bizonyos minimális kompetenciát az ágensek részéről.

Legyen D={*, t}∪{ ≥ k, =k, ≥ k | k pozitív egész}.

27. Definíció. Egy C D=(N, T, S, H 1, …, H n ) nyelvtanrendszer által generált nyelv valamely fD levezetési módban: L f (C D)={wT * | S i 1 f p 1 i 2 f p 2…⇒ i m f p m =w, m ≥ 1, 1 ≤ i j  ≤ n, 1 ≤ j ≤ m}. ★

Az előző definícióval számos nyelvet társítottunk egy CD-rendszerhez, felhasználva a különböző D- beli megállási feltételeket. A H i egy komponense elkezdhet dolgozni (futása engedélyezett lesz) egy p mondatformán, amikor p tartalmazza egy H i - beli szabály baloldalát. Az, hogy melyik engedélyezett komponens kapja meg az éppen aktuális mondatformát, egy nemdeterminisztikus választás alapján dől el. Elképzelhetünk különböző kezdőfeltételeket is, például, ha egy komponens csak akkor lesz engedélyezett egy mondatformán való munkára, ha bizonyos feltételek teljesülnek, esetleg egy külső vezérlő egység (például egy gráf, vagy verem meghatározva a komponensek engedélyezési sorrendjét) irányít.

10.1. példa - CD nyelvtanrendszer

Legyen C D=({S, A, B, C, D}, {a, b, c}, S, {S → S, SA C}, {Aa B b, Cc D}, {Ba A b, Dc C}, {Aa b, Ba b, Cc, Dc}). Könnyen belátható, hogy ez a nyelvtanrendszer =2,  ≥ 2 és t-módban az {a n b n c n |n>0} nyelvet, míg  ≤ k (bármely k ≥ 1 esetén), =1 és * módban a {a n b n c m |n, m>0} nyelvet generálja; ha pedig k>2 akkor  ≥ k módban az üres nyelv az eredmény. ★


10.2. példa - CD nyelvtanrendszer

Legyen C D=({S, A}, {a}, S, {SA A}, {AS S}, {A  → a, Sa}). Könnyen belátható, hogy ez a nyelvtanrendszer t- módban a {a 2 n |n ≥ 0} nyelvet generálja. ★


Ahogy az előző példákban láthattuk a környezetfüggetlen nyelvtanok generáló ereje megnő, ha őket CD-rendszerben használjuk: sem a {a n b n c n |n>0}, sem a {a 2 n |n ≥ 0} nyelv nem környezetfüggetlen, sőt a második nyelv nem is konstansnövekményű (nem szemilineáris).

10.3. példa - CD nyelvtanrendszerek - Gyakorló feladat


Adjunk meg olyan CD-rendszert, amely valamilyen módban a {w w|w∈{a, b}*} nyelvet tudja generálni. ★