5.2. Nyelvek generálása

Most tekintsük a DNS-dominókkal történő molekulahalmazok (nyelvek) generálását. Az előző fejezetben a felhasznált egyszálú DNS-dominóknak egyedi helyük volt, ahova beilleszthetőek voltak a memóriaegységekben. Ezzel szemben ebben a fejezetben a dominók alakja összetettebb ennél.

A formális leíráshoz általánosan tekintsünk egy V ábécét, és egy azon értelmezett ρV × V szimmetrikus relációt, amit komplementaritási relációnak fogunk hívni. Bár a reláció szimmetrikusságát nem fogjuk kihasználni, de mivel az eredeti modellben a V = {A,C,G,T} ábécé a nukleotidokat tartalmazza, és a rajtuk értelmezett Watson-Crick reláció szimmetrikus, ezért mi is csak szimmetrikus relációkat tekintünk. (Sőt, mivel a Watson-Crick reláció egy a V halmaz önmagával vett bijekciója, van amikor csak olyan relációt tekintünk, ami nemcsak szimmetrikus, de egyben bijekció is: vagyis minden elemnek egyértelműen definiált komplementere van.) A V* feletti sztringek helyett, most V* × V* feletti sztringpárokkal fogunk dolgozni. Ez kb. annak felel meg, hogy egy adott DNS molekula felső, illetve alsó láncát mi(lyen sztring) alkotja. A DNS molekulák elrendezése miatt a sztringpárokat a alakba fogjuk írni, ahol u, vV*. Ennek megfelelően két pár konkatenációját: alakba írjuk, és a V* × V* helyett is a jelölést fogjuk használni. A duplasztringek esetén a konkatenáció egységeleme a amit, ha nem megtévesztő, egyszerűen λ-ként írunk. Azokat a sztringpárokat, almelyekben a két sztringet olyan betűk alkotják, amelyek megfelelő sorrendben éppen egymás komplementerei, formálisan

teljes duplaszálaknak (vagy röviden csak duplaszálaknak, esetleg molekuláknak) hívjuk. A Watson-Crick domént pedig jelöljük, ami az adott V ábécével és a rajta értelmezett ρ komplementaritással definiált. A Watson-Crick domén duplasztringjeit: formában is írhatjuk, ahol u=a1a2...an és v=b1b2...bn. Azt a tulajdonságot, hogy a 2 sztring pontosan egymás komplementere a speciális zárójellel mutatjuk az általános, bármilyen sztringpárt megengedő esethez képest. A sztringpárok és a duplaszálak esetén is használjuk a felső- és alsósztring kifejezést a felső (leírásunkban eddig pl. az u) és az alsó szálon található sztringekre (eddig pl. v).

A Watson-Crick domén definíciója szerint a is megengedett molekula, bár sokszor, mivel biokémiailag nem reprezentál semmit, nem szoktuk annak tekinteni. Ezen üres molekula elkerülésére vezessük be a jelölést. Matematikailag a Watson-Crick domén monoid (egységelemes szabad félcsoport), vagyis bármely két molekula konkatenációja is molekula: A molekulákkal szemben általában az -vel jelölt sztringpároknál semmilyen összefüggést nem feltételezünk a felső- és az alsósztring között. Ezzel szemben tehát, még egyszer kiemelve, a molekulák olyan speciális sztringpárok, amelyek:

Ahogy az Adleman kísérletében is láttuk, sokszor nem csak teljes duplasztringekkel reprezentált molekuláink vannak, azok egyik, vagy mindkét végén az egyik szál túlnyúlhat a másik szálon, ezzel ún. ragadós véget alkotva, amihez a komplementaritásnak megfelelően egyszálú, vagy más az eredetihez hasonlóan ragadós véggel rendelkező molekulák tapadhatnak hozzá. Emiatt a modellben a dominók olyan kettős sztringek, amelyek nem teljes molekulákat jelenítenek meg, ennek megfelelően nem mindkét szálon van meg végig a molekula. Ezek alapján a 5.4. ábrán bemutatott alakú dominókat engedjük meg (néha a polyominó elnevezés lenne helytállóbb szigorú értelemben).

5.4. ábra - A DNS-dominók lehetséges alakja nyelvgeneráláshoz.

A DNS-dominók lehetséges alakja nyelvgeneráláshoz.

A ragadós végek jelölésére bevezetjük az jelölést. Ekkor

L(V) = S(V) WKρ(V)

R(V) = WKρ(V) S(V),

valamint

Továbbá bevezetjük a Wρ(V) = L(V) ∪ R(V) ∪ LR(V) jelölést mint a nem teljes molekulák halmazát (vagyis ezek a ragadós végű molekulák, amelyeket e modellben használni fogunk a számítás során). Ahogy látható, az L(V) elemeiben a baloldalon van (lehet) egyszálú ún. ragadós vég, amíg az R(V) elemeiben a jobboldalon.

Ezekben a dominókban a kétszálú rész (x) hossza akár 0 is lehet (az ilyen molekulák, mind az L(V), mind az R(V) csoportba beletartoznak, ahogy ez az ábránkon is látszik). Ezzel szemben az LR(V) elemeiben mindkét oldalon van (lehet) ragadós vég, és ennek megfelelően középen nem 0 hosszúságú duplaszál található. A teljes molekula felépítéséhez olyan „molekulából" kell kiindulnunk, melyben legalább egy helyen bázispár található, a Wρ(V) ilyen molekuláit kezdőmolekulának hívjuk, utalva arra, hogy belőlük kezdődhet/folytatódhat a számítás, a molekula felépítése. Mivel az LR(V)-beli molekulákban biztosan van egy bázispár, ezeket tekintjük kezdőmolekuláknak a rendszerben. Ha már van ilyen kezdőmolekulánk, akkor a folyamat úgy mehet, hogy más dominók ehhez ragadhatnak jobb, illetve bal oldalon, a ragadós végnek megfelelően (a gyakorlatban a folyamatban a ligáz enzim is szerepet játszik a molekula gerincének összeragasztásában, vagyis a foszfodiészter-kötés létrehozásában).

Ez alapján a dominók lehetséges összeragasztása (a „sticking" művelet) a 5.5. ábrán látható módon megy ezekben a rendszerekben. Ennek megfelelően balról jobbra épülhetnek fel a teljes molekulák a dominókból, ahogy az y-nal jelzett dominó rész hozzátapad a már meglevő x-ekkel jelölt (részben sárga színnel jelzett) ragadós végű molekulához.

5.5. ábra - A DNS-dominók lehetséges összeragasztása molekula képzéshez: molekulaépítés jobb oldali irányban.

A DNS-dominók lehetséges összeragasztása molekula képzéshez: molekulaépítés jobb oldali irányban.

Ezen műveleteket a következőképpen írhatjuk le formálisan: Legyen x,yWρ(V), ahol x = x1x2x3 kezdőmolekula amiben x2 rész teljes duplasztring, x3S(V) pedig ragadós vég. Ekkor az x-hez jobbról az y dominó hozzáragasztása, jelekkel: μ(x,y), a következőképpen definiált:

Ugyanígy írható le a μ(y,x) művelet is, amiben az y dominót pont a másik irányból ragasztjuk az x kezdőmolekulához. (Ne tévesszen meg senkit, a kezdőmolekula elnevezést nemcsak azokra a molekulákra használjuk, amik a folyamat legelső lépéséhez szükségesek, hanem minden létrejött molekulára is, hiszen azokban is van kétszálú rész, és kezdőmolekulák lehetnek a folyamat további lépéseiben.)

Itt jegyezzük meg, hogy nem feltétlenül szükséges a két irányú ragasztó operátort mindkettőt definiálni, hiszen minden ragasztásnál az egyik molekula bal, a másik a jobboldalon van (a modellünkben), arra viszont mindenképpen figyelni kell, hogy csak olyan dominókat ragaszthatunk össze, amik közül legalább az egyik kezdőmolekula. Ugyancsak megjegyezzük, hogy a fenti ragasztó operátorok elvileg definiálva vannak p = 0 esetre is, amikor a valódi ragadós vég hiányzik, vagyis „tompavéghez" is engedélyezett a ragasztás.

A ragasztó műveletek olyanok, hogy megtartják a kezdőmolekulákat kezdőmolekulának, vagyis továbbra is van a molekulában (nem feltétlenül hosszabb részen ugyan, de van) kétszálú rész. Továbbra a létrejött új molekula ugyancsak eleme az LR(V) halmaznak. A cél az, hogy végül teljes kétszálú molekula jöjjön létre.

Figyeljük meg, hogy az első két ragasztó műveletben valójában nem használjuk a ρ relációt, nincs igazából ragasztás a komplementaritás által, csak a ligáz kapcsolja össze az új molekulát. A korlátozott ragasztó rendszerekben ezek a műveletek nem megengedettek.

Formálisan a következőképpen definiálhatjuk ezeket a nyelvgeneráló rendszereket:

1. Definíció. Egy kétirányú ragasztórendszer (bidirectional sticker system) formálisan egy rendezett négyes (V, ρ, P, A), ahol

A rendszerben a közvetlen, vagy egy lépésben való felépítés (a számítás egy lépése) a következő reláció:

xw pontosan akkor, ha van olyan (y,z) ∈ P, hogy w = μ(y,x), z).

A ⇒ reflexív és tranzitív lezártja a ⇒*, amit felépítésnek (vagy számításnak) hívunk. Egy számítás befejezett, ha a végén előállt v molekula teljes (). Ez alapján, a rendszer által generált (molekulahalmaz, vagy molekula)nyelv:

Szokás csak a felsőszálon előállított sztringnyelvet tekinteni a számítás eredményének, így a generált (sztring)nyelv:

Egy L nyelvről akkor mondjuk, hogy ragasztónyelv, ha van olyan ragasztórendszer, ami L-et generálja.

Egy kétirányú ragasztórendszerben a levezetés (molekulaépítés) az A halmaz egy tetszőleges axiómájából kiindulva a P elempárjával lépésenként történik, egy lépésben az (y,z) ∈ P pár tagjait ragasztjuk az aktuális kezdőmolekulához, az y-t balról, a z-t pedig jobbról. Ezekből a lépésekből álló számítás eredménye egy teljes kétszálú molekula lehet, amely eleme az előállított (molekula)nyelvnek.

Nagyon érdekes a következő normálforma jellegű eredmény.

1. Lemma. Minden egyes R = (V, ρ, P, A) kétirányú ragasztórendszerhez van olyan R' = (V, id, P', A') kétirányú ragasztórendszer, hogy az általuk generált sztringnyelvek megegyeznek: L(R) = L(R') és id az identitási reláció, vagyis id = {(a,a)∣aV}.

Bizonyítás: Csak a bizonyítás ötletét mutatjuk be.

Tegyük fel, hogy xL(R). Ekkor van olyan y szó, hogy

Mivel a ρ reláció szimmetrikus, minden axiómában és dominópárban kicserélhetjük az ott előforduló alsó sztringet, z-t az ott levő eredeti sztring komplementer sztringjére (v-re, ha

az eredeti ρ reláció szerint). Ezáltal a felső sztringen generált nyelv nem változik meg, ha az új rendszerben az id relációt használjuk.

QED.

Az előző tétel a felső szálon definiált nyelvről szólt, a rendszer által definiált molekulanyelv viszont szinte biztosan meg fog változni, ha megváltozik a használt „komplementaritási" reláció (az identitási relációra).

A számítást primitívnek nevezzük, ha nem folytatódhat teljes kétszálú láncból, mint kezdőmolekulából, vagyis ha egy ilyet előállítottunk, akkor az adott számítás véget ér.

2. Definíció Egy (V, ρ, P, A) (kétirányú) ragasztórendszer

Ha minden lépésben csak az egyik oldalon bővítjük (építjük) a molekulát, akkor tehát egyoldalú a rendszer, ha mindig csak jobbra bővítünk, ami az előbbinél is jóval speciálisabb eset, akkor reguláris ragasztórendszerről beszélünk.

Amennyiben csak olyan dominókat használhatunk a molekula felépítéséhez (hozzáragasztásához), amelyek alsó-, vagy felsőszála a λ, vagyis csak egyszálú (ún. egyszerű) dominóink vannak, akkor a ragasztó műveletek közül az utolsó kettő nem fordulhat elő, lásd 5.5. ábrán is, (B-1) és (B-2) esetek.

A reguláris egyszerű rendszerek esetén így a definíciót is átírhatjuk a következő, egyszerűbb alakba:

3.Definíció Egy egyszerű reguláris ragasztórendszer (simple regular sticker system) formálisan (V, ρ, Du, Dl, A), ahol

Az egyszerű reguláris ragasztórendszerek által generált nyelvek családját SRSL-el jelöljük.

Lássunk egy példát egy ilyen rendszerre:

15. példa. Legyen R =({a,b}, id, Du, Dl, A), ahol

Du = {a, bb}, Dl = {aa, b}, és

Könnyen bizonyítható, hogy L = (aa + bb)+.

Az eddigi definíciókban, ragaszkodva az eredeti DNS molekulákkal való megvalósíthatóságra, mindig csak olyan axiómából indulhattunk ki, amely tartalmaz kettős láncrészt.

Formálisan azonban megengedhetjük olyan rendszerek felírását is amelyekben eltekintünk ettől a feltételtől, és bármilyen, akár egyszálú sztring, vagy az üres sztring is lehet axióma.

Azokat a speciális eseteket, amikor egyetlen axióma van csak és az éppen az üressztring, vagyis

egyszerűen axiómanélküli ragasztórendszereknek fogjuk hívni, ezzel is utalva arra, hogy a molekulák felépítésében csak a dominók vesznek részt.

23. Feladat. Adjunk meg olyan axiómanélküli egyszerű reguláris ragasztórendszert, ami az előző példában megadott nyelvet generálja (ha eltekintünk az üres molekulától).

A speciális ragasztórendszerek által generált nyelvosztályok egymáshoz való viszonyáról a következőt mondhatjuk:

1. Tétel. A ragasztórendszerekkel definiált nyelvcsaládok és a Chomsky hierachia nyelvcsaládjai között fennállnak a következő relációk.

Ezen eredmények bizonyítását itt nem mutatjuk be, megtalálhatóak pl. a [Păun et al.] könyvben.

Ahhoz, hogy a generált nyelvcsaládokat a hagyományos, Chomsky-féle nyelvcsaládokkal jobban összeköthessük szükség van néhány széles körben ismert elméleti fogalomra, melyek segítségével pl. különböző ábécéken definiált nyelvek között teremthetünk kapcsolatot.

4. Definíció. Tekintsük a következő fogalmakat:

Vegyük észre, hogy egy morfizmus teljesen definiált, ha az ábécé betűin megadjuk. A kódolás nemtörlő, és betűhöz betűt rendel, míg a gyenge kód esetén előfordulhat, hogy néhány betű törlésre kerül...

Bizonyítás nélkül közöljük a következő tételt, amely a reguláris nyelvek ragasztórendszerek általi jellemzéséről szól.

2. Tétel Minden SRSL nyelv reguláris (Chomsky 3. típusú). Minden egyes reguláris nyelv felírható valamely SRSL nyelv gyenge kódjaként.

5. Definíció. Legyen (V, ρ, Du, Dl, A) egy egyszerű reguláris ragasztórendszer. Legyen T egy véges ábécé, és legyen u : Du → T, valamint ℓ : Dl → T két leképezés a T-re. Tekintsünk egy befejezett számítást. Ekkor a felsőszálon a számítás során felhasznált dominók sorozatához az u segítségével rendeljük a wuT* sztringet. Hasonlóan, az alsószálon a számítás során felhasznált dominók sorozatához az ℓ segítségével rendeljük a wlT* sztringet. Egy számítást

Ennek megfelelően az R egyszerű reguláris ragasztórendszer által

Jelölje SRSL(f), illetve SRSL(k) az egyszerű reguláris ragasztórendszerek által fair, illetve koherens módon generált nyelvek halmazát.

Fair tehát egy számítás, ha ugyanannyi dominót használunk a felső szálon, mint az alsón. A koherens módnál ennél erősebb feltételnek is teljesülnie kell: a dominók sorrendje a megadott címkék szerint meg kell hogy egyezzen a két szálon. Így a definíció alapján látható, hogy ha egy egyszerű reguláris ragasztórendszer számítása koherens, akkor egyben fair is.

24. Feladat. Legyen R = ({a,b}, id, Du, Dl, A), ahol

Du = {a, bb}, Dl = {aa, b}, és

Mutassuk meg, hogy a rendszer által fair módon generált nyelv nem reguláris.

Az SRSL(f) nyelvek az ún. vak egyszámláló automatákkal jellemezhetőek [Hoogeboom, Vugt], melyek olyan véges automaták, amik egy számlálóval vannak kiegészítve. Ennek a számlálónak az értéke kezdetben 0, és az input feldolgozása során minden lépésben eggyel nőhet az értéke, maradhat változatlanul, vagy eggyel csökkenhet. Az automata vak, vagyis az átmenetfüggvénye nem függ a számláló állásától. Viszont elfogadni csak akkor fogad el egy inputot, ha az input végére érve, nemcsak végállapotba kerül az automata, de a számláló értéke is éppen 0.

A fejezetet a következő, az RE osztályt jellemző tételekkel zárjuk, melyeket bizonyítás nélkül közlünk.

3. Tétel. Minden egyes rekurzívan felsorolható nyelv megadható egy SRSL(k) nyelv kódjaként.

4. Tétel. Minden egyes rekurzívan felsorolható nyelv megadható egy olyan L' nyelv gyenge kódjaként, amely egyszerű ragasztórendszerrel generálható és egyszerű ragasztórendszerrel primitív számításokkal is generálható.