6. fejezet - Watson-Crick automaták

Tartalom

6.1. Hagyományos WK-automaták
6.1.1. Speciális változatok - hierarchia eredmények
6.2. 5'→3' WK-automaták
6.2.1. Biológiai motiváció
6.2.2. Formális leírás
6.2.3. 5'→3' WK-automata nyelvosztályok
6.2.4. 2detLIN nyelvek
6.2.5. Végigolvasó és többször végigolvasó (nem érzékeny) 5'→3' WK-automaták

Ebben a fejezetben a hagyományos véges automaták olyan „kiterjesztéseit" fogjuk részletesen tárgyalni, amik a hagyományos inputszalag helyett DNS molekulákat olvasnak (dolgoznak fel) és fogadnak el. A Watson-Crick automatákat a DNS két felfedezőjének a tiszteletére nevezték el, és a nevük első, illetve utolsó betűje alapján alapján (Watson-CricK) röviden WK-automatáknak nevezik.

A véges elfogadó automaták és a reguláris nyelvek leírása megtalálható a Függelékben.

A Watson-Crick automaták a teljes kétszálú DNS láncokon, mint Watson-Crick szalagon dolgozó automaták, azt is mondhatjuk, hogy a Watson-Crick doménen, vagyis -beli molekulákon dolgoznak. Mivel a DNS molekulák duplaláncot alkotnak, ennek megfelelően a fő különbség a hagyományos véges automata és a WK-automata közt, hogy ennek az utóbbinak két olvasófeje van, mindkét lánchoz egy-egy. Ily módon a WK-automaták a többfejű automaták közé sorolhatók (ezekkel kapcsolatban ajánljuk pl. a magyarul is elérhető [Herendi, Nagy] könyvet).

Az első fej a felső, míg a második fej az alsó láncot olvassa a feldolgozás során. Formálisan a következőképpen definiáljuk őket:

6. Definíció Az M = (V, ρ, Q, q0, F, δ) rendezett hatost WK-(véges) automatának nevezzük, ahol

Egy Watson-Crick automata vázlatát mutatja a 6.1. ábra.

6.1. ábra - Egy Watson-Crick automata.

Egy Watson-Crick automata.

Szokás a WK-automatáknak speciális alosztályait tekinteni a következő lehetséges megszorítások alapján.

A megszorítások tehát egyrészt az egy átmenetben mozgó fejek számára, illetve az olvasott sztringek hosszára vonatkozhatnak, másrészt viszont az állapothalmazra: vannak-e nem végállapotok a rendszerben, illetve van-e egyáltalán a kezdőállapoton kívül másik állapot. Itt jegyezzük meg, hogy sokszor az egyállapotú automatákat szokás állapotnélkülinek tekinteni, ugyanis ezek az állapotukkal nem tudnak információt tárolni, az állapotuk nem változhat meg, ezért akár az le is spórolható a leírásukból. Az adott típusok rövidítése az angol nevek alapján (S: Simple, 1: 1-limited, F: all-Final, N: stateless - No state) érthető. Láthatjuk, hogy egyszerű automata esetén, minden lépésben maximum az egyik fej lép, míg 1-korlátos automata esetén ez a fej pontosan egy betűt olvas az adott átmenetben. Így világos, hogy az 1-korlátos WK-automaták az egyszerű WK-automaták speciális esetei, ahogy az egyállapotú automaták a minden állapot elfogadó típusba is tartoznak. Ezzel szemben az első két megszorítás (ami az átmenetfüggvényre vonatkozik) független a második kettőtől (ami az állapothalmazra vonatkozik), aminek megfelelően ezek különböző kombinációi is érdekes alosztályokat definiálnak, tehát az SF, SN, az 1F és az 1N is mind szokásos speciális WK-automata osztályok.

A definícióban szándékosan nem interpretáltuk a δ átmeneti függvényt, illetve nem definiáltuk az automata kiinduló konfigurációját, nem írtuk le a működését. Ezt többféleképpen is megtehetjük, ez alapján különböztethetjük meg pl. a hagyományos és az 5'→3' WK-automatákat. A következőkben előbb a hagyományos modellt ismertetjük.

6.1. Hagyományos WK-automaták

A hagyományos WK-automatákban a két fej a feldogozandó DNS molekulának ugyanarról a végéről indul.

7. Definíció A hagyományos WK-automata egy konfigurációján egy (,q) rendezett hármast értünk, ahol u, vV* az inputnak az első (felső szál), illetve a második fej (alsó szál) által még nem olvasott része, qQ pedig az aktuális állapot. A kezdőkonfiguráció (,q0), ahol w az input szó ( pedig a Watson-Crick komplementere, tehát kezdetben még a teljes molekula feldolgozandó). Akkor mondjuk, hogy egy (,q) konfigurációból közvetlenül elérhető egy (,p) konfiguráció (jelekkel: (),q)⊢(,p), ha p ∈δ(q,). A közvetlen elérhetőség reflexív és tranzitív lezárásával kapjuk az elérhetőség (jelekkel:*) fogalmát. Az automata elfogad egy molekulát, vagyis egy w szót, ha (,q0) ⊢* (,p) valamely pF állapotra. Az elfogadott szavak halmaza adja az automata által elfogadott (vagy felismert) molekulahalmazt (nyelvet). Általában az elfogadott nyelvet vagy a molekulahalmazon, vagy azokból a felső szál által definiált szavak halmazán értjük.

Itt jegyezzük meg, hogy az üres-molekulát általában nem tarjuk molekulának, így nem foglalkozunk vele, az nem lehet eleme WK-automatával elfogadott nyelvnek. Emiatt a WK-automaták vizsgálatakor üresszómentes nyelvekre szorítkozunk: ha az eredeti L nyelv tartalmazta az üresszót (vagyis λ ∈ L), akkor annak az üresszó nélküli: L \ {λ} részére).

Ha egy DNS-dominó rendszert úgy tekintünk, mint amivel előállíthatjuk a DNS molekulák egy halmazát (vagyis generálhatjuk az adott DNS-nyelvet), akkor ezen rendszerek elfogadópárjainak is tekinthetőek a hagyományos WK-automaták a következő eredmény szerint.

5. Tétel. Ha egy L DNS nyelv generálható egyszerű reguláris ragasztórendszerrel (DNS-dominókkal) koherens módon (vagyis L egy SRSL(k) nyelv), akkor van olyan WK-automata, ami elfogadja.

Ráadásul, ha L generálható axiómanélküli ragasztórendszerrel koherens módon, akkor L-et állapotnélküli WK-automata is elfogadja.

Bizonyítás: A bizonyítás konstruktív. Legyen adott a (V, ρ, Du, Dl, A) egyszerű reguláris ragasztórendszer, ami L-et generálja koherens módon az u : DuT és : DlT leképezések segítségével valamilyen T ábécé felhasználásával.

Ekkor legyen M = (V, ρ, Q, q0, F, δ), ahol Q = F = {q0, q}; a δ átmenetfüggvény pedig a következőképpen definiált:

axiómára (x' = λ vagy y' = λ minden elemre); és

párra, ha u(x) = (y).

Láthatjuk, hogy a megkonstruált automata csak végállapotokkal rendelkezik, a kezdőállapotra csak valamely axiómából való kiinduláshoz van szükség. Emiatt, ha a megadott ragasztórendszer axiómanélküli, akkor a q0 állapot és a hozzá tartozó átmenet törlésével egy állapotnélküli automatát kapunk (ennek megfelelően q1 lesz ennek a kezdőállapota is).

Mivel a konstrukciónak köszönhetően, a dominókkal történő koherens módon történő generálás lépéseinek éppen megfelelnek az elfogadó WK-automata lépései, könnyen belátható, hogy pontosan azokat a DNS-molekulákat/szavakat, és ez alapján éppen azt a (felsőszálon olvasott) nyelvet fogadja el az automata, amit a DNS-dominókkal generálhatunk az adott ragasztórendszerrel.

QED.

Itt merülhet fel a kérdés, hogy, ha a DNS molekuláknak nem egy elejük van, vagyis bármelyik száluk tekinthető felsőszálnak, akkor az elfogadott molekulák alapján, a másik szálon 5'→3' irányban olvasott szót is fel kellene vennünk az elfogadott nyelvbe. Viszont ezt könnyen elvethetjük, és tarthatjuk magunkat az eredeti definícióhoz a következőképpen: használjunk különböző betűket az alsó és a felső szálon, pl., az eredeti nukleinsavaknál maradva, a felső szálon csak A és C, míg az alsó szálon, ennek megfelelően csak T és G használatával így könnyen megkülönböztethető lesz az a nyelv amivel foglalkozni akarunk, itt pl. csak a {A,C}+-beli egyszeres láncok, amiket az elfogadott molekulákból denaturálással kaphatunk.

Két WK-automatát (ahogy általában is szoktuk automaták esetén) ekvivalensnek tekintünk, ha ugyanazt a nyelvet fogadják el. Igazából meg lehet különböztetni molekulanyelvi ekvivalenciát és felső szálon értelmezett nyelv alapján történő ekvivalenciát. Amennyiben ugyanazt a ρ relációt használja mindkét automata, ekkor, mind a molekulanyelv, mint a felsőszálon értelmezett sztringnyelv egybeesik ekvivalens automaták esetén. A következőkben, ha az ekvivalencia szót használjuk WK-automaták között feltételezzük, hogy ugyanazt a ρ relációt használja mindkét automata.

A WK-automaták valódi kiterjesztései a hagyományos véges automatáknak: minden reguláris nyelv elfogadható velük. Ha mindkét fej mindig egyszerre lép (ugyanazt a betűt, illetve annak a komplementerét olvasva), akkor pontosan a hagyományos véges automata működését szimulálhatjuk. Igaz viszont, hogy ha a feldolgozás során bármely inputra, a 2 fej távolsága csak egy adott korláton belül marad, akkor az elfogadott nyelv reguláris (a véges sok lehetőséget, ami a két fej közötti szakaszon lehetséges, véges sok állapottal szimulálni tudjuk)...

Ahogy a hagyományos automatákat megadhatjuk gráfjuk segítségével, úgy a WK-automatákat is, azzal a különbséggel, hogy a gráf éleire, rendezett párként mindkét fej által olvasott szót (u és v) odaírjuk.

A következő példákkal megmutatjuk, hogy ezek az automaták jóval nagyobb elfogadó erővel bírnak, mint a hagyományos véges automaták: a következő példákon nem reguláris, sőt nem környezetfüggetlen nyelveket fogunk hagyományos WK-automatákkal elfogadni.

16. Példa (a másolat nyelv). Legyen

, ahol δ a következőképpen definiált:

és nincs egyéb definiált átmenet (vagyis pl. stb.). Ekkor az automata működése: az első fej elmegy amíg egy c-t nem talál, az automata eddig végig a kezdőállapotban maradt, ekkor megy át p állapotba. Ebben az állapotban a két fej egyszerre ugyanazt a betűt, illetve komplementerét olvashatja, így folytatva az input feldolgozását, végül az első fej helyben maradása mellett a második fej egy -t olvashat, ezzel az automata q állapotba kerül. Ebben az állapotban, a végállapotban az első fej már nem olvashat, a második fej viszont -kat és -ket is olvasva befejezheti az input szó feldolgozását. Tehát az elfogadott nyelv a nem környezetfüggetlen L(M) = {wcww ∈ {a,b}*} nyelv a felső szálat tekintve. A 6.2. ábra grafikusan is mutatja az automatát.

6.2. ábra - A {wcw ∣ w∈{a,b}*} nyelvet elfogadó WK-automata.

A {wcw ∣ w∈{a,b}*} nyelvet elfogadó WK-automata.

17. Példa (a többszörös megfelelés nyelve) Legyen

ahol δ a következőképpen definiált:

és nincs definiált átmenet egyéb esetre. Ekkor az automata működése: az első fej addig olvas a-kat amíg egy b-hez nem ér, az automata eddig végig a kezdőállapotban maradt, ekkor megy át p állapotba, úgy, hogy miközben az első fej b-t olvas addig a második fej egy -t. Ebben az állapotban a két fej egyszerre olvashatja a b-ket, illetve az -kat, így folytatva az input feldolgozását. Ezután, amikor az első fej egy c-t olvas, miközben a második fej egy -t, az automata r állapotba megy át. Ebben az állapotban a két fej egyszerre olvashatja a c-ket, illetve a -ket. Végül az első fej helyben maradása mellett a második fej egy -t olvashat, így az automata q végállapotba kerül. Ekkor az első fej már nem olvashat, a második fej viszont -ket olvasva befejezheti az input szó feldolgozását. Így az elfogadott nyelv a nem környezetfüggetlen L(M) = {anbncnn > 0} nyelv a felső szálat tekintve. A 6.3. ábra grafikusan is mutatja az automatát.

6.3. ábra - Az {anbncnn > 0} nyelvet elfogadó WK-automata.

Az {anbncn∣n > 0} nyelvet elfogadó WK-automata.

18. Példa (a keresztfüggőségek nyelve). Legyen

ahol δ a következőképpen definiált:

és nincs definiált átmenet egyéb esetre. Ekkor az automata működése: az első fej elolvas a-kat és b-ket amíg egy c-hez nem ér, az automata eddig végig a kezdőállapotban maradt, ekkor megy át p állapotba, úgy, hogy miközben az első fej c-t olvas addig a második fej egy -t. Ebben az állapotban a két fej egyszerre olvashatja a c-ket, illetve az -kat, így folytatva az input feldolgozását. Ezután, amikor az első fej egy d-t olvas, miközben a második fej egy -t, az automata r állapotba megy át. Ebben az állapotban a két fej egyszerre olvashatja a d-ket, illetve a -ket. Végül az első fej helyben maradása mellett a második fej egy -t olvashat, így az automata q végállapotba kerül. Ekkor az első fej már nem olvashat, a második fej viszont -ket és -ket is olvasva befejezheti az input szó feldolgozását. Így az elfogadott nyelv a nem környezetfüggetlen L(M) = {anbmcndmn,m > 0} nyelv a felső szálon. A 6.4. ábra grafikusan is mutatja az automatát.

6.4. ábra - Az {anbmcndmn,m > 0} nyelvet elfogadó WK-automata.

Az {anbmcndm∣n,m > 0} nyelvet elfogadó WK-automata.

Amint láthattuk a WK-automatákkal nem környezetfüggetlen nyelveket is el tudunk fogadni. Figyeljük meg, hogy ezekben a példákban a két fej távolságára nem tudunk az input szótól független korlátot megadni. Eddigi példáink szemilineárisak voltak, de van nem szemilineáris nyelv is amelyet WK-automaták el tudnak fogadni.

19. Példa. A 6.5. ábrán mutatott WK-automata által elfogadott szavak hosszai éppen a négyzetszámok, vagyis a megadott automata egy nem szemilineáris nyelvet fogad el.

6.5. ábra - Egy nem szemilineáris nyelvet elfogadó WK-automata.

Egy nem szemilineáris nyelvet elfogadó WK-automata.

Az automata működése a következő:

Az felső fej elolvas egy c-t, amivel az automata q állapotba kerül. A q állapotban három dolog történhet:

  • vagy csak az alsó fej olvas egy c-t amivel az automata a qf végállapotba kerül, amiben az alsó fej páros számú betűt olvashat ezzel „utolérve" a másik fejet elfogadó futás esetén. Végállapotban a felső fej már nem olvashat, annak már előtte el kellett érnie a molekula végét.

  • ha még nem érte el a felső fej az input molekula végét, és mindkét fejnek c (vagyis az alsó fejnek, az ennek megfelelő ) következik, akkor ezt elolvasva az automata az r állapotba kerül. Innen az első fejjel aa elolvasásával kerülünk vissza a q állapotba.

  • ha mindkét fejnek aa (illetve alul ) következik, akkor azt elolvassák, és marad az automata q állapotban, amíg ez folyamatosan fennáll.

A működés megértéséhez nézzük meg az első néhány molekulát, amit az automata elfogad (a felső szálon található sztringek szerepelnek a listán, ellenőrizzük őket(!)):

c, ccaa, ccaacaaaa, ccaacaaaacaaaaaa, ...

Ellenőrizhető, hogy minden további elfogadott szó egy c(aa)* résszel bővül, amiben az a-k száma, mindig kettővel több, mint az előző ugyanilyen alakú blokkban. Ezek alapján pedig az automata által elfogadott szavak hossza éppen a négyzetszámokat adja, és ennek megfelelően a nyelv nem szemilineáris (és így természetesen nem környezetfüggetlen).

25. Feladat. Készítse el azt a hagyományos WK-automatát, amely a {anbncnanbnn > 1} nyelvet fogadja el (a felsőszálon).

26. Feladat. Készítse el azt a hagyományos WK-automatát, amely a nyelvet (molekulákat) fogadja el.

A példáink többségében minden lépésben maximum egy betűt olvasott mindkét fej. Mivel azonban voltak olyan átmeneteink, amikben mindkét fej olvasott és lépett, ezek az automaták nincsenek egyik általunk definiált speciális osztályban sem. Most nézzük mire képesek a speciális megszorításokkal rendelkező változatok.

6.1.1. Speciális változatok - hierarchia eredmények

Biológiai megfontolások alapján motivált a minden állapot végállapot változat, ekkor, ha a fejek fel tudják dolgozni az inputot, megtörténik az elfogadás. Ugyancsak biológiailag motivált az egy állapottal rendelkező modell, hiszen a legegyszerűbb enzimeket könnyebben tudjuk úgy elképzelni, hogy nincs „állapotuk". Amennyiben nem egy, hanem két különböző enzimként képzeljük a molekula két szálát olvasó fejeket, egyértelmű, hogy értelmet nyer az egyszerre csak egy fej mozgását megengedő modell is. Végül, mivel az enzimek lokálisan dolgoznak, nem életszerű, hogy bármilyen hosszú (pl. több százezer betűnyi) lánc olvasása egy lépésben megtörténjen, az ennek egy betűre való korlátozásával egy ilyesmi megszorítást próbálhatunk a modellnek adni.

Jelölje N1WK, NSWK, F1WK, FSWK, NWK, FWK, 1WK, SWK és WK az N1WK, NSWK, F1WK, FSWK, NWK, FWK, 1WK, SWK, illetve a(z általános) WK-automaták által felismert nyelvek osztályát.

Kezdjük a legerősebb megszorítással rendelkező N1WK-automatákkal. Ezek egyetlen állapottal rendelkeznek (jelölje ezt q), egyszerre csak az egyik fej léphet és az is csak egy betűt olvashat egy lépésben. Ennek megfelelően az a T* nyelv fogadható, amelyre értelmezve van a átmenet minden aT-re, és a átmenet minden -ra, ahol ez egy aT komplementere. Láthatjuk, hogy ezek a nyelvek nagyon speciális reguláris nyelvek.

Tekintsük most az NSWK-automatákat. Ezekben ugyancsak függetlenül mozoghat a két fej, ennek megfelelően olyan nyelvek fogadhatóak el, amelyek molekuláit, mindkét fej végig tudja olvasni, vagyis (u1, ..., un)* ⋂ (v1, ..., vm)*, ahol u1, ... un pontosan azok a V*-beli szavak, amelyekre ha n átmenet van az első (felső) fejre értelmezve); v1, ..., vm pedig pontosan azok a szavak, amik komplementerét a második (alsó) fej tudja egy-egy lépésben olvasni, vagyis ha m átmenet van az alsó fejre értelmezve). Ezek ugyancsak eléggé speciális reguláris nyelvek (két speciális alakú reguláris kifejezés által leírt nyelv metszeteként állnak elő). Ilyen nyelvre példa a (aa)* nyelv. Viszont ez a nyelv nem N1WK nyelv, vagyis N1WK-automata nem tudja elfogadni.

Ezek alapján tehát:

1. Következmény.

N1WKNSWKREG

Tekintsük most az NWK-automatákat. Kezdjük egy példával:

20.Példa. Legyen ahol δ a következőképpen definiált:

Ekkor tekintsük csak az M által elfogadott alakú molekulákat. Világos, hogy ezek feldolgozása csak az első átmenettel kezdődhet. Az első átmenet n-szeri (n ∈ ℕ) alkalmazásával eljutunk oda, hogy a felsőszálon már b következik. Ekkor a harmadik átmenet n-szeri alkalmazásának kell következnie, hogy az alsó szálon is eljussunk az első -ig. Ezek után a negyedik átmenet alkalmazásával fejezhető be ezen speciális alakú molekulák feldolgozása. Így viszont a negyedik átmenetet is n-szer kellett alkalmazni, hogy a két fej azonos pozícióba kerüljön, tehát az ilyen alakú elfogadott molekulák az nyelvet alkotják. Viszont így L(M) ⋂ {a*b*} = L', ami nem reguláris. Mivel a reguláris nyelvek zártak a metszetképzésre (és {a*b*} reguláris), ez csak úgy lehetséges, ha L(M) nem reguláris.

Másrészt viszont a reguláris ab* nyelv nem NWK nyelv. Ez könnyen belátható, ha figyelembe vesszük, hogy minden NWK nyelv zárt a Kleene plusz műveletre, hiszen az automatának nincs memóriája, hogy észrevegye már befejezte-e a feldogozást, vagy még el sem kezdte.

Nézzük most az F1WK-automatákat.

6. Tétel. Minden reguláris nyelv F1WK nyelv, van nem reguláris F1WK nyelv is.

Bizonyítás: Először is bizonyítsuk be, hogy mindegyik reguláris nyelv elfogadtatható F1WK-automatával. Legyen adott egy reguláris nyelv az azt elfogadó véges automatával: (Q, T, q0, δ, F). Ekkor definiáljuk a következő F1WK-automatát: ahol qfQ új állapot és δ' a következőképpen definiált:

  • legyen minden qQ \ F, aT párra.

  • legyen minden qF és aT esetén, továbbá

  • legyen minden aT esetén;

  • nincs más átmenet értelmezve.

Ekkor az első és második típusú átmenetekkel, nem használva a qf állapotot, éppen az eredeti véges automatát szimulálhatjuk a felső szálon tekintett inputon, amennyiben a szó végén elfogadó állapotba kerülhetett az eredeti automata, és csak ekkor kerülhet a megadott WK-automata qf állapotba a felső szál végén. Ekkor viszont az alsó szál is elolvasható, de a felső szál olvasásával már nincs értelmezett átmenet. Mindkét szál csak akkor olvasható el, ha éppen a felső szál utolsó betűjének olvasásakor kerülünk qf állapotba.

Ezek alapján világos, hogy az elfogadott nyelv éppen az eredeti reguláris nyelv (az esetleges üres szó kivételével, amit, ahogy előre rögzítettük nem tartunk molekulának). A megadott automata pedig a tulajdonságait tekintve F1WK-automata. Ahhoz, hogy belássuk, hogy a REGF1WK tartalmazási reláció valódi, szükség van egy olyan példanyelvre, ami F1WK-automatával elfogadtatható, de nem reguláris.

6.6. ábra - A jelölt másolat nyelvet elfogadó F1WK-automata.

A jelölt másolat nyelvet elfogadó F1WK-automata.

A 6.6. ábrán mutatott F1WK-automata a {wcww∈{a,b}*} nyelvet fogadja el, ami nem reguláris, (sőt nem is környezetfüggetlen). Az automata működése pedig a 16. Példán bemutatott automatáéhoz nagyon hasonló.

QED.

Vannak olyan „megszorítások" is, amik az elfogadott nyelveket tekintve nem jelentenek megszorítást:

7. Tétel. A következő nyelvcsaládok egybeesnek: 1WK = SWK = WK.

Bizonyítás: Az alapötlet az, hogy az eredeti WK-automata lépéseit szétbonthatjuk új állapotok bevezetése közben olyan lépésekre, amikre már ezek a megszorítások is teljesülnek. A teljesen formális bizonyítás helyett, annak főbb lépésit írjuk csak le. Legyen M az eredeti WK-automata, ekkor megmutatjuk, hogyan lehet egy vele ekvivalens M' SWK, illetve egy ezekkel ekvivalens M" 1WK-automatát előállítani. Ehhez először az eredeti WK-automata lépéseit szétbontjuk olyan lépésekre, amikben csak az egyik fej lép:

Minden olyan lépést, amiben mindkét fej lép egy új állapot segítségével két lépésre bonthatunk, amelyek egyikében az első, a másikban pedig a második fej lép. Formálisan:

Az M minden átmenete helyett, ahol u ≠ λ, v ≠ λ, legyen az M' átmenete, ahol p' egy újonnan bevezetett állapot, amely pontosan ebben a két állapotátmenetben szerepel az M' automatában.

Továbbá, minden olyan lépést, amikor egy fej egy betűnél hosszabb sztringet olvas egy lépésben, új állapotok bevonásával szétbonthatunk olyan lépések sorozatára, amelyekben pontosan egy betűt olvas az adott fej. Formálisan, pl. a felsőszál esetén ez a következőképpen néz ki:

Ha az M' automatában valamely u = a1 ... an (n > 1) szóra, akkor az M" automatában legyenek definiálva a alkalmasan választott p1, ..., pn-1 új állapotokra, amelyek mindegyike az M"-ben pontosan abban a két átmenetben szerepel, amit itt megadtunk (az egyikben az ∈ jel előtt, a másikban a δ" átmenetfüggvény első paramétereként).

Az ilyen lépések segítségével mindig elérhetjük, hogy minden átmenetben max. egy betűt olvasson az automata miközben az elfogadott nyelv megegyezik az eredetivel. Kimaradt még az az eset, ha volt olyan átmenet definiálva, amiben nem történt olvasás egyik szálon sem. Az ilyen esetekben (hasonlóan ahhoz, ahogy az üresszavas lépéseket a hagyományos véges automatáknál távolítjuk el) az adott átmenetet együtt kell kezelni a következő olyan átmenettel, amiben már történik betűolvasás (akár több egymást követő üresszót olvasó átmenet után), és egyből abba az állapotba kell történnie az átmenetnek, amibe a betű elolvasása után jutna.

QED.

Továbbá az FSWK-automaták is el tudják fogadni az összes WK nyelvet:

8. Tétel. A következő nyelvcsaládok egybeesnek: FSWK = FWK = WK .

Bizonyítás: A teljes formális bizonyítás (megtalálható pl. [Kuske, Weigel], ahol eredetileg megjelent) helyett, annak ötletét mutatjuk be. Induljunk ki egy tetszőleges WK-automatából, és megmutatjuk, hogy van vele ekvivalens FSWK-automata. Mivel minden állapot végállapot, azokat a molekulákat, miknek mindkét szálát végig tudjuk olvasni, elfogadja az automata. Készítsük el azokat az átmeneteket, amikkel az eredeti automata elfogadja az egy, illetve két bázispárból álló molekulákat. Azokra az állapotokra, amelyekkel így történik elfogadás nincs értelmezett átmenet. Tehát ezeknek a rövid molekuláknak az elolvasása két lépésben történik, és amennyiben az input hosszabb (csak így kezdődött), a feldolgozás akkor sem folytatható ebben az irányban (másik nemdeterminisztikus futást kell használni az esetleges elfogadásra). Ezután csak az ezeknél hosszabb molekulákra koncentrálunk. Láthattuk, hogy az eredetivel ekvivalens (ugyanazt a nyelvet elfogadó) SWK-automatát egyszerűen készíthetünk, sőt 1WK-automatát is. Az alapötlet itt is hasonló: az, hogy a molekula olvasása során először a felső fejjel egyet lépünk. Ezután viszont a feldolgozás során csak olyan átmeneteink lesznek, amik egy adott fejet két betű olvasásával mozgatnak előre. (Ez megoldható új állapotok felvételével úgy, hogy az összes kétbetűs szóra megnézzük, hogy az eredetivel ekvivalens 1WK automatának milyen lehetőségei lennének arra, hogy egymás után az adott betűket olvassa az adott szálon. Például egy q-a állapot jelentheti azt, hogy az előző 1WK-automata egy q állapotához képest a felső szálon már egy a-val többet olvastunk, mint az eredeti automatában, hiszen pl. az eredeti b helyett, amivel ott a q állapotba kerültünk, itt egy ba-t olvastunk el... Ez azt jelenti, hogy az ilyen állapotban a felső szálon csak a betű olvasható, a felső fejjel csak ilyen átmenet lehetséges. A konstrukció elég technikai, de az ötlet elegáns és megoldható.) Következésképpen véletlenül sem alakulhat úgy, hogy a két fej ugyanarra a pozícióra kerül, ami az input végén lesz érdekes. Tehát kell még olyan átmenet ami megengedi, hogy az egyik fej csak egyet lépjen, és esetlegesen ezzel fejezze be az automata az input feldolgozását, azokból az állapotokból, tehát amikbe így juthat el az automata nincs értelmezett átmenet. Ezek alapján viszont csak azok és pontosan azok a molekulák lesznek elfogadva, amiknél megengedjük, hogy a két fej ugyanabba a pozícióba kerülhessen, ezt pedig csak akkor engedjük, amikor az eredeti WK-automata (vagy az azzal ekvivalens 1WK) végállapotba kerülne ugyanebben a pozícióban. Az új automatában tehát minden állapot végállapot, az elfogadásról ott döntünk, hogy megengedjük mindkét fejnek hogy a szó végére érjen egyszerre, és minden lépésben csak egy fej lép. Tehát bármelyik WK nyelvhez tudunk készíteni FSWK-automatát.

Mivel minden WK nyelvről beláttuk, hogy egyben FSWK nyelv is, az FWK nyelvosztálynak is meg kell egyeznie ezekkel.

QED.

Mivel egy WK-automata esetén az adott input szó elfogadásához nem használunk fel az adott szónál nagyobb tárterületet (vagyis lineárisan korlátozott Turing-géppel megvalósítható az elfogadás), minden WK nyelv környezetfüggő. Emellett az is igaz, hogy ha a V ábécé egyelemű) és ekkor természetesen az egyetlen betű saját maga komplementere, akkor csak reguláris nyelvek elfogadására képesek a WK-automaták. Eszerint viszont nem minden környezetfüggő nyelv WK nyelv.

A WK-automaták által elfogadott nyelvek hierarchiáját a 6.7. ábrán látható Hasse-diagram mutatja be. Minden WK-automatával elfogadtatható nyelv környezetfüggő (lineáris tárhelyen megoldható a feladat).

6.7. ábra - Watson-Crick véges automata nyelvosztályok hierarchiája (a nyíl a tartalmazó osztály felé mutat).

Watson-Crick véges automata nyelvosztályok hierarchiája (a nyíl a tartalmazó osztály felé mutat).

A hierarchiában egyetlen eddig nem megoldott fontos kérdés van, vajon az F1WK nyelvek családja valódi részhalmaza-e az FSWK = WK családnak. Az F1WK-automaták esetén nem működik az a páros-páratlan pozícionálós trükk, amit az FSWK-automatáknál használtunk, viszont olyan WK nyelvről sincs (egyelőre) tudomásunk, amely bizonyosan nem fogadható el F1WK-automatával. Az ábrán a kék nyíl jelzi ezt a tartalmazási relációt, amiről nem tudjuk tehát, hogy valódi tartalmazást jelent-e. Másrészt, tudjuk, hogy a REG és az NWK nyelvcsaládok halmazelméleti tartalmazást tekintve nem összemérhetőek, így van olyan F1WK nyelv is, ami nem NWK nyelv. Viszont, hogy van-e olyan NWK nyelv, ami nem F1WK nyelv, ez ugyancsak egy nyitott kérdés. (Tehát lehet, hogy az NWK-tól az F1WK-ba vezet nyíl, és nem a WK-val jelzett osztályba.) Persze, ha az első problémával kapcsolatosan valaki bizonyítaná, hogy F1WK = WK, akkor azzal automatikusan a második kérdés is megválaszolódna.

8. Definíció Determinisztikusnak nevezünk egy WK-automatát, ha minden (elvileg) lehetséges konfigurációban maximum egy átmenet van engedélyezve.

Ezek alapján azt mondhatjuk, hogy a 16-18. Példák mindegyikében determinisztikus WK-automatával fogadtuk el az adott nem környezetfüggetlen nyelvet. Az eredeti nemdeterminisztikus változat tehát a determinisztikus változatnál általánosabb fogalom, minden determinisztikus WK-automata egyben (nemdeterminisztikus) WK-automata is. Ezzel ellentétben igaz a következő:

9. Tétel. A determinisztikus WK-automaták által elfogadott nyelvek osztálya kisebb, mint a nemdeterminisztikus társaikkal elfogadott nyelvek osztálya.

Bizonyítás: Elég egy példát adnunk olyan nyelvre, amelyet nemdeterminisztikus WK-automata elfogad, de nincs olyan determinisztikus WK-automata, ami elfogadná. Vegyük, pl. két már vizsgát nyelv unióját: legyen . Ekkor, belátható, hogy az első tagba eső szavak esetén egy determinisztikus automatának úgy kell működnie, hogy miközben az egyik fej a középső (-ból álló) részt olvassa, a másik fejnek olvasnia kell az első (-ból álló) részt (egy adott véges automata nem tud bármilyen nagy számot eltárolni az állapotaival); viszont a második tagba eső molekulák esetén egy determinisztikus automatával az egyik fejjel csak akkor szabad az első részt (az -ból álló blokkot) elolvasni, amikor a másik fejjel már a harmadik (-ből álló) blokkot olvassa. Emiatt a megadott L nyelv, bár nemdeterminisztikusan nem túl bonyolultan elfogadtatható WK-automatával, nincs olyan determinisztikus WK-automata, ami elfogadná.

QED.

27. Feladat. Adjuk meg a bizonyításban használt L nyelvet elfogadó nemdeterminisztikus WK-automatát.

Adjunk meg FSWK-automatát, ami ugyanezt a nyelvet fogadja el.

Például az N1WK, vagy az NSWK-automaták esetén nincs is értelme determinisztikus változatról beszélni, ugyanis a kezdő- és egyetlen állapotban determinisztikus esetben csak az egyik fej tud olvasni, a másik, mivel több állapot nincs, nem mozdulhat el, ennek megfelelően nincs olyan molekula, amit mindkét fej végig tudna olvasni egy determinisztikus NSWK-automata esetén, tehát csak az üres nyelv lehet az elfogadott...

A fejezet zárásaként egy az RE nyelvosztály WK-automatákkal való jellemzését mutatjuk meg:

10. Tétel. Minden egyes rekurzívan felsorolható nyelv megadható egy FSWK/FWK/SWK/1WK/WK nyelv kódjaként.

Bizonyítás: Az 5. Tételből tudjuk, hogy minden egyes L SRSL(k) nyelvhez van olyan FWK-automata, amely ugyanazt a nyelvet fogadja el. Mivel az FWK osztály ekvivalens az FSWK, az SWK, az 1WK és a WK-automaták osztályával, ezen típusok mindegyikére is teljesül az előbbi állítás. A 3. Tétel értelmében viszont ezek a nyelvek alkalmasak az RE nyelvosztály reprezentálására a jelen tétel állításában szereplő módon.

QED.

A következő fejezetben a WK-automatáknak egy másik típusát tárgyaljuk, ahol az átmenetfüggvényt, illetve ennek következtében a szavak elfogadását is máshogy interpretáljuk.