8.2. Beszúró-törlő rendszerek formális leírása

Az előző alfejezetben megismert műveletek, a beszúrás és törlés segítségével, azokat formálisan megadva, most a DNS számítások egy újabb modelljét írjuk le.

18. Definíció. Egy beszúró-törlő rendszer egy B = (V, T, A, I, D) rendezett ötös, ahol

Az beszúró és törlő szabályokat a következőképpen alkalmazhatjuk:

Legyen x, wV*. Azt mondjuk, hogy xw, ha w beszúró vagy törlő szabály használatával megkapható x-ből. Formálisan:

  1. x = x1uvx2, w = x1uyvx2, ahol (u,y,v) ∈ I és x1, x2V*, illetve

  2. x = x1uyvx2, w = x1uvx2, ahol (u,y,v) ∈ D és x1, x2V*.

Tehát az (u,y,v) ∈ I beszúró szabály jelentése a következő: az y sztring beszúrható u és v közé (ha azok közvetlenül egymás után következnek ilyen sorrendben). Hasonlóan az (u, y, v) ∈ D törlő szabály jelentése: az y részszó törölhető az (u, v) (sztring)környezetből, vagyis ha pontosan u részszó előzi meg és v részszó követi.

Figyeljük meg, hogy egy (u,y,v) beszúró szabály megfelel a uvuyv átírási (helyettesítési) szabálynak, míg egy (u,y,v) törlő szabály a uyvuv szabálynak felel meg.

A szokásos módon a ⇒ reláció tranzitív és reflexív lezártját ⇒* jelöli.

19. Definíció. A B beszúró-törlő rendszer az

L(B) = {wT*x ⇒* w, valamely xA-ra}

nyelvet definiálja.

Tehát kiindulva valamelyik axiómából véges sok beszúró és törlő művelet után azokat a sztringeket tekintjük, amelyek csak terminális szimbólumokat tartalmaznak (hasonlóan a generatív nyelvtanokhoz).

A beszúró-törlő rendszerek bonyolultságát a szabályaik bonyolultsága (a bennük szereplő szavak hossza) szabja meg.

20. Definíció. Azt mondjuk, hogy a B = (V, T, A, I, D) beszúró-törlő rendszer (n,m;p,q) súlyú, ha

A beszúró-törlő rendszereket az angol terminológiának megfelelően INSDEL-nek hívjuk. Az előző jelölésnek megfelelően a következőképpen definiáljuk az előállított nyelvcsaládokat:

Az n, m, p, q ≥ 0 esetén jelölje azon nyelvek családját, amelyek definiálhatóak maximum (n,m;p,q) súlyú beszúró-törlő rendszerrel, vagyis pontosabban ha van olyan (n’,m’;p’,q’) súlyú B beszúró-törlő rendszer, hogy L = L(B) valamely n’n, m’m, p’p, és q’q értékekre. Ha az n, m, p, q paraméterek valamelyikére nincs korlátozás (vagyis az bármilyen nagy pozitív egészet felvehet), azt * jellel jelöljük. jelöli tehát az összes beszúró-törlő rendszer által definiált nyelvcsaládot.

32. Példa. Az jelenti azt a nyelvcsaládot, amibe beletartozik minden olyan nyelv, amelyet a következő alakú beszúró-törlő rendszerekkel hozhatunk létre:

Természetesen, minden egyes L nyelvhez, ha akkor van olyan B beszúró-törlő rendszer, amelyre L(B) = L, és a B rendszer véges sok szabálya alapján megadhatunk olyan konkrét n, m, p, q ∈ ℕ értékeket, amikre is teljesül.

Mivel az üresszó beszúrása, illetve törlése igazából nem változtat az adott szón, feltesszük, hogy n = 0 esetén m = 0 is fennáll, és hasonlóan p = 0 esetén q = 0 is teljesül. Ha n = 0, akkor csak max. 0 hosszúságú szót szúrhatunk be, vagyis effektíve nincs beszúró műveletünk, tehát ha a nyelvcsaládot definiáló INSDEL első részének indexei 0-k: akkor azzal azt jelezzük, hogy a tekintett rendszerekben nem használunk beszúrást (I = ∅). Hasonlóan az elnevezésben a rész, a törlő szabályok hiányára utal.

Abban az esetben, ha m = 0 és q = 0, vagyis környezet ellenőrzése nélküliek a beszúró, illetve a törlő szabályaink, környezetfüggetlen beszúró-törlő rendszerről beszélünk. (Megjegyezzük, hogy matematikai értelemben ezek nagyon érdekes rendszerek, de biológiai szempontból inkább tűnik hihetőbbnek a beszúrási és törlési művelet végrehajthatósága, ha megfelelően hosszú u és v környezet-szakaszok tudnak részt venni az összetapadásban....)

Ezt fejezetet néhány példával és feladattal zárjuk.

33. Példa. Legyen B = ({a,b}, {a,b}, {ab}, {(a,ab,b)}, ∅). Ekkor kiindulva az egyetlen axiómából a következő szósorozat állítható elő:

a b ⇒ a a b b ⇒ aa a b bb ⇒ aaa a b bbb ⇒ aaa a ab b bbb ...

Minden egyes lépésben az a-k és a b-k közé történhet csak a beszúrás. Ennek megfelelően ezzel a rendszerrel definiált nyelv: L(B) = {anbnn ≥ 1}. Ez egy lineáris, de nem reguláris nyelv. Ezek alapján azt mondhatjuk, hogy

Ha nem használunk környezetet a beszúráshoz, akkor egy másik fontos nyelvet állíthatunk elő, az előző módhoz hasonlóan:

40. Feladat. Mutassuk meg, hogy a B = ({a,b}, {a,b}, {λ}, {(λ, ab, λ)}, ∅) rendszer a helyes zárójelpárok nyelvét generálja (,a' felel meg a nyitó, ,b' a záró jelnek). Ez a nem lineáris, de környezetfüggetlen nyelv a következőképpen jellemezhető:

Ezzel szemben a 33. példa nyelvét is lehet definiálni környezetfüggetlen beszúró-törlő rendszerrel, bár így bővebb munkaábécére, és ennek megfelelően törlő szabályra is szükség van:

34. Példa. Legyen B = ({S, B}, {a,b}, {S}, {(λ, BaSb, λ), (λ, Bab, λ)}, {λ, SB, λ}). Mivel a definiált nyelvbe csak azok a szavak számítanak, amik csak terminális betűket (itt a és b) tartalmaznak, az egyéb szimbólumokat az egyetlen törlő szabállyal kell kitörölni. Ez azt jelenti, hogy a B-t mindig közvetlenül egy S után kell beszúrni a beszúró szabály alkalmazásakor, terminális szó előállítása csak így lehetséges. Eredetileg S-ből indulunk ki. Tegyük fel, hogy aktuálisan w1Sw2-nél tartunk (kezdetben tehát w1 = λ és w2 = λ). Ekkor a (λ, BaSb, λ) beszúró szabállyal, hogy a B megfelelő helyre kerüljön:

w1S w2w1S BaSb w2.

Ebből a törlő szabály alkalmazásával w1aSbw2 áll elő, és a folyamat megismételhető... Egy terminális szó előállításához a w1Sw2 alakú aktuális szóra a (λ, Bab, λ) beszúró szabályt alkalmazva, hogy a B megfelelően pont az S után kerüljön: w1SBabw2 áll elő, amire a törlő szabály alkalmazható, és w1abw2 szót állít elő. Ez, ha már az első lépésben a (λ, Bab, λ) beszúró szabályt alkalmazzuk, éppen az ab szó lesz, egyébként pedig egy hosszabb, de anbn alakú szó. Tehát L(B) = {anbnn ≥ 1}.

41. Feladat. Adjon meg egy környezetfüggetlen beszúró-törlő rendszert, ami előző példához hasonló módszerrel a palindromák nyelvét definiálja.