6.2. 5'→3' WK-automaták

Ebben a szakaszban olyan speciális Watson-Crick automatákat vizsgálunk, amelyeknél a két olvasó fej egymással szemben halad az input két végéről indulva. Ez a rész teljes egészében a szerző a témával kapcsolatos munkáin alapul.

6.2.1. Biológiai motiváció

A DNS felépítése olyan, hogy a két szál biokémiailag egymással szemben áll. Az egyik szál 5' végéhez a másik szál 3' vége tapad és fordítva. Ennek megfelelően, ha úgy képzeljük el, hogy a két szálon egy-egy enzim csúszik végig a DNS szekvenciasorrendjét olvasva, akkor azok a korábban ismertetett verzióval ellentétben biokémiailag azonos irányban mozognak, ami fizikai, matematikai vagy számítási szempontból éppen ellenkező irányt jelent. Tehát az 5'→3' WK-automatákban az olvasófejek a molekula két végéről, az adott fej által olvasott szál 5' végéről indulnak, és egymással szemben haladnak. Ez viszont arra is lehetőséget ad, hogy a futás véget érjen a két fej találkozásakor, hiszen ekkorra a teljes input feldolgozása megtörtént, az inputmolekula minden egyes bázispárjának egyik tagját elolvasta az automata. Vizsgáljuk meg tehát ezt a modellt.

6.2.2. Formális leírás

A definíció az előző fejezetben tárgyalt hagyományos WK-automatákétól az állapotátmenet-függvény értelmezésében, illetve a konfigurációkban tér el. Ahhoz viszont, hogy a két fej által olvasható sztringek ne 'fedhessenek át', vagyis a két fej mindig csak olyan betűket olvasson, aminek a másik szálon levő párja még ebben a lépésben sem kerül olvasásra a másik fej által, bevezetésre kerül egy technikai paraméter, ami a feldolgozás során a két fej távolságát jelzi.

9. Definíció. Egy M = (V, ρ, Q, q0, F, δ) rendezett hatost (érzékeny) 5'→3' WK-automatának nevezzük, aminek V, ρ, Q, q0 és F elemei ugyanazok, mint a hagyományos WK-automatának. A δ alakja pedig: , és értéke csak véges sok esetben különbözik az üres halmaztól. Az összes értelmezett átmenetre vegyük azu∣+∣vértéket, ahol a felső fej az u, az alsó fej a v-t olvassa az átmenet során. Ezenu∣+∣vértékek maximumát jelöljük r-rel és az automata sugarának hívjuk, ez a maximális érték, amivel az automata fejei közeledhetnek egymáshoz egy átmenet során. Legyen R = {0,1, ..., r, + ∞} az érzékenységi paraméterek lehetséges halmaza, és ez legyen úgy beállítva minden átmenetre, hogyu∣+∣v∣ ≤ r'. A konfigurációk rendezett párok, ahol u, vV* és v az u komplementere, a még feldolgozandó input és a qQ az aktuális állapot. A kezdeti konfiguráció: ahol w az inputszó, a feldolgozandó input molekulának a felső szálon megjelenő része. A konfigurációk az állapotátmenet-függvénynek megfelelően változhatnak az automata számítási lépései alapján: ahol ub, u, ujV*, vb, v, vjV* pedig ezek komplementerei, r'R pedig az érzékenységi paraméter, továbbá, ha ub u uj∣ > r, akkor r' = ∞, egyébként pedig r' = ∣ ubuuj ∣. A szokásos módon akkor mondjuk, hogy M elfogad egy w input szót, ha valamely pF állapotra. Az automata által elfogadott szavak halmaza jelenti az automata által elfogadott L(M) nyelvet.

Azt mondjuk, hogy az M WK-automata determinisztikus, ha minden lehetséges konfigurációja esetén legfeljebb egy közvetlenül elérhető konfiguráció létezik.

Ezekben az automatákban csak olyan átmeneteket engedünk meg, amikben a fejek nem mehetnek túl egymáson, ezt hivatott az érzékenységi érték szabályozni: ha a fejek közel vannak egymáshoz (már látják egymást, hiszen akár egy lépésben képesek lennének befejezni a számítást), akkor, csak akkor engedélyezett egy átmenet, ha a távolságuk éppen megfelelő ehhez. Ennek megfelelően, a konfigurációkban csak a „még hátra levő, még feldolgozandó inputot" kell tárolnunk, aminek hossza, ha nem haladja meg az r-et, korlátozza, megszabja a lehetséges átmeneteket.

Mint láthatjuk az 5'→3' WK-automata egy futása során az inputmolekula egy betűpárját legfeljebb egy fej olvassa (a pár másik tagját, komplementerét pedig ekkor a másik fej már nem fogja olvasni), így az input feldolgozása tekinthető párhuzamosnak. Mivel ezek az automaták az input molekula minden egyes betűjére annak (maximum) csak a, vagy részét olvassák, ebben az alfejezeteben csak olyan ρ relációkat tekintünk, amely egy-egyértékű (bijekció).

A következő példa az 5'→3' WK-automata egy tipikus működését írja le.

21. Példa (tükörszavak nyelve). Legyen , ahol

A fel nem sorolt esetekben nincs definiált átmenet (üres halmaz a lehetséges állapotok halmaza). Látható, hogy az érzékenységi paraméter értéke az automata esetén az R = {0,1,2,+∞ } halmazba eshet. Ekkor M az input feldolgozásakor, egyszerre olvashatja az input egy betűjét az első fejjel, amíg ennek a komplenterét a második fejjel, miközben marad a q állapotában (ha a fejek távolsága nem volt kisebb, mint 2). Ily módon minden páros hosszúságú olyan szót el tud fogadni, aminek a második fele megegyezik az első felének visszafele fordítottjával. Amennyiben az input páratlan hosszúságú, az utolsó (középső) betű olvasásával az automata p állapotba mehet át, de ez az átmenet csak az érzékenységi paraméter 1 értéke esetén, használható, vagyis, amikor a fejek távolsága pontosan 1.

A 22. példában bemutatott automata determinisztikusan fogadja el a tükörszavak nyelvét.

Itt jegyezzük meg, hogy a Watson-Crick komplementaritás miatt a DNS molekulák között a palindrom tulajdonságot sokszor úgy szokás értelmezni, hogy az 5'→3' irányban olvasva mindkét láncon ugyanaz van (palindrom-molekula). Könnyen belátható, hogy ebben az esetben, ha nincs olyan betű, ami saját magával (is) komplementer relációban áll, akkor csak páros hosszúságú palindromok létezhetnek. Ezek a molekulák az előző példabeli automata kis módosítással kapott változatával fogadtathatók el.

28. Feladat. Adjon meg olyan állapotnélküli automatát, amely a palindrom-molekulákat fogadja el.

A következő példa mutatja, hogy a nemdeterminisztikus futások hogyan használhatók ki, egyben megmutatva, hogy a nemdeterminisztikus változat elfogadóereje nagyobb, mint a determinisztikus változaté.

22. Példa (a jelölt másolat nyelv komplementere). A célunk olyan automata készítése, amely a {wcww ∈ {a,b}*} nyelv komplementerét fogadja el (az ábécé felett) a felső szálon. Készítsük el azt a nemdeterminisztikus 5'→3' WK-automatát, melynek működése a következő nemdeterminisztikus futásokat engedi meg. Legyen az automatának olyan futása, hogy fogadjon el minden olyan molekulát, amelyben a felső szálon van {a,b,c}-beli és -beli betű is. Továbbá, legyen az automatának olyan futása, amivel elfogad minden olyan inputot, amiben a c-k száma nem 1 a felső szálon. (Ehhez elég végigolvasni az inputot a felső szálon, és állapotot váltani, ha egy c-t olvastunk, majd megint ha újabbat. Ilyen futással elfogadtatható minden olyan szó, amiben nincs c, vagy egynél több van.) Legyen olyan futás, ami elfogadja az összes olyan alakú molekulát, amelyre, az u és a v hossza különböző. (Ez megtehető úgy, hogy a két fej egyszerre olvas egy-egy betűt, így közeledve egymás felé, ha nem egyszerre érnek a betűkhöz, akkor el kell elfogadni az inputot.) Ekkor már csak az olyan alakú, de nem megfelelő szavakat kell elfogadni, amik a felső szálon ugyan ucv (u,v ∈ {a,b}*) alakúak és az u és a v hossza megegyezik. Az ilyen szavak közül csak az eleme a nyelvünknek, amiben van olyan betű amiben az u és a v eltér, vagyis a felső szálon a szó xeycx'e'y' alakba írható, ahol az x és az x' hossza egyenlő, valamint az y és az y' hossza megegyezik, továbbá e ≠ e', e, e' ∈ {a,b}. Ekkor legyen az automata elfogadó futása a következő: Az első fej olvassa el az x szórészt, majd az automata az állapotával jegyezze meg az itt olvasott e ∈ {a,b} betűt. Ezután a két fej egyszerre betűnként lépve olvassa el az y-t, illetve az y' szórész komplementerét (ezek hossza megegyezik, tehát egyszerre fogja a két fej ezeknek az olvasását befejezni). Ekkor az első fej a c betűt fogja olvasni, a második fej pedig az e' komplementerét. Ennek megfelelően az automata ellenőrizni tudja, hogy a megjegyzett e és a most olvasottnak megfelelő e' érték különbözik-e. Ha különböznek, akkor a második fej elolvassa az x' rész komplementerét is, a fejek találkoznak és az automata végállapotba kerül, elfogad. Ellenkező esetben ez egy nem elfogadó futás.

6.2.3. 5'→3' WK-automata nyelvosztályok

Ahhoz, hogy további eredményeket mutassunk be az 5'→3' WK-automatákkal kapcsolatban néhány a formális nyelvekben ismert fogalmat ismétlünk át röviden (részletesebb leírásért ajánljuk pl. a [Dömösi et al.] tankönyvet).

Legyen G = (N, T, S, H) egy generatív nyelvtan (23. Definíció). Emlékeztetőül: A G nyelvtan lineáris, ha minden levezetési (helyettesítési) szabálya olyan, hogy a baloldalon pontosan egy nemterminális szimbólum áll, és semmi más, a jobboldalon pedig maximum egy nemterminális és akárhány terminális (bármilyen sorrendben): Au vagy AuBv; ahol A,BN és u,vT*.

Lássuk, akkor most az általános, korlátozás nélküli 5'→3' WK-automata számítási erejét [Nagy 2008] alapján.

11.Tétel. Az érzékeny 5'→3' WK-automaták által elfogadott nyelvek 5'-3'WK halmaza megegyezik a Chomsky-féle lineáris nyelvek LIN halmazával.

Bizonyítás: Az egyszerűség kedvéért a bizonyításban a Watson-Crick komplementaritási relációként az identikus relációt tekintjük (más egy-egyértékű relációk esetén is hasonlóképpen megy a bizonyítás menete).

A tétel bizonyítása konstruktív, először az első irányt tekintjük: legyen adva egy G = (N, T, S, H) lineáris nyelvtan, az egyszerűség kedvéért normálformában. Ekkor megkonstruáljuk azt az M 5'→3' WK-automatát, amely a G által generált nyelvet fogadja el. Mivel G normálformájú, minden levezetési szabálya maximum egy terminálist tartalmaz, ennek megfelelően olyan érzékeny 5'→3' WK-automatát adunk meg, amelyre R = {0,1,+∞}.

Legyen M = (T, id, N ∪ {qf}, S, {qf}, δ) ahol qfN, δ pedig a következőképpen van definiálva a H szabályhalmaz alapján:

  • ha BaAbH, ahol A,BN, a, bT ∪ {λ} (és a normálforma feltétel miatt ekkor minden ilyen szabályra ∣ab∣ ≤ 1),

  • ha BaAbH, ahol A,BN, a, bT ∪ {λ},

  • ha BAH, ahol A,BN és a=b=λ,

  • ha AaH, ahol AN, aT,

  • ha A → λ ∈ H, ahol AN.

Könnyen belátható lépésenkénti indukcióval, hogy a nyelvtan minden egyes termináló levezetésének pontosan egy elfogadó út fog megfelelni az automatában, és más elfogadó út nem lesz.

A másik irány bizonyításához legyen M = (T, id, Q, q0, F, δ) adott valamilyen R = {0, ..., r, +∞} érzékenységi paraméterekkel, amihez megkonstruáljuk azt a G nyelvtant, ami az automata által elfogadott nyelvet fogja generálni. Az általánosság csorbítása nélkül feltehetjük, hogy Q × R és T halmazok diszjunktak (ha ez nem teljesül, a Q halmaz elemeinek átnevezésével ez elérhető). Ekkor legyen G = (Q × R ∪ {S}, T, S, H), ahol S ∉ (Q × R) ∪ T, és a nyelvtan szabályait a következőképpen definiáljuk:

  • S → (q0, r') minden r'R esetén,

  • legyen (q, +∞) → u (q',r') vH minden {r'r' ∈ ℕ, r' > r - ∣u∣ -∣v∣} ∪ {+∞} értékre, ha , (q, q'Q, u, vT*),

  • legyen (q, r") → u (q', r') vH, ahol r" < +∞ és r' = r" - ∣u∣ - ∣v∣, ha , (q, q'Q, u, vT*), továbbá r" ≥ ∣u∣ + ∣ v ∣,

  • legyen (q, ∣u∣+∣v∣) → uvH, ha

Könnyen ellenőrizhető, hogy pontosan az elfogadó futásokhoz lehet termináló levezetéseket találni a megkonstruált nyelvtanban, így a tételt mindkét irányban bebizonyítottuk.

QED.

29.Feladat. Adjon meg ekvivalens 5'→3' WK-automatát a G = ({S, A, B, C}, {a,b}, S, H) nyelvtanhoz, ahol H = {SaA, SBb, AaA, ACa, BBb, B → λ, CbA, CaB}.

30. Feladat. Adjon meg ekvivalens lineáris nyelvtant az M = ({a, b, c}, id, {q0, q1, q2, q3, q4}, q0, {q3, q4}, δ) 5' → 3' WK-automatához, ahol az átmenetfüggvény a következőképpen definiált:

Ezeknek a kétfejű automatáknak nemcsak az a jelentősége, hogy az inputot akár kétszer gyorsabban dolgozza fel (a két fej miatt), mint a hagyományos véges automata, de egy bővebb nyelvosztály elfogadására képesek, hiszen nemcsak a reguláris, hanem a lineáris nyelvek elfogadására képesek, amiben megtalálható pl. a palindrómák nyelve.

A következő eredmény arról szól, hogy az 5'→3' WK-automaták determinisztikus változata nem olyan kifejezőerejű, mint a nemdeterminisztikus változat.

12. Tétel. A determinisztikus 5'→3' WK-automatákkal elfogadott nyelvek det5'-3'WK osztálya valódi része a lineáris nyelvek LIN osztályának.

Bizonyítás: A tartalmazás nyilvánvaló, így csak a valódiságát kell bizonyítani. A bizonyítás, aminek alapgondolatát közöljük, egy példa segítségével megy: tekintsük az

L = {anbann ∈ ℕ} ∪ {anca2nn ∈ ℕ}

lineáris nyelvet a felső szálon. Egy input esetén amelyre n kellően nagy, kezdetben nincs esély annak eldöntésére, hogy az adott inputmolekula vajon az első vagy a második a nyelvet definiáló molekulahalmazba esik. Márpedig e nélkül determinisztikus 5'→3' WK-automatával nincs esély annak elfogadására, hiszen az állapotok által csak véges méretű memóriája van az automatának... Így belátható, hogy L nem det5'-3'WK nyelv.

QED.

A det5'-3'WK nyelvosztályt 2detLIN osztályként fogjuk hivatkozni, utalva arra, hogy ez az eredeti automaták által elfogadott LIN nyelvosztálynak az a része, amit ezen két olvasó fejjel rendelkező automaták determinisztikus változatai fogadnak el.

Ahogy a hagyományos, úgy az 5'→3' Watson-Crick-automatáknál is szokás a különböző korlátozásokkal rendelkező változatokat is vizsgálni. Most ezt fogjuk tenni mi is.

Ennek megfelelően jelöljük az (érzékeny) 5 → 3' WK, SWK, 1WK, FWK, NWK, FSWK, F1WK, NSWK és N1WK automaták által elfogadott nyelvosztályokat, rendre 5'-3'WK, 5'-3'SWK, 5'-3'1WK, 5'-3'FWK, 5'-3'NWK, 5'-3'FSWK, 5'-3'F1WK, 5'-3'NSWK és 5'-3'N1WK jelekkel. Ha determinisztikus automatákat tekintünk, akkor a det előszót tesszük az adott nyelvosztály neve elé, jelölésben, pl. det5'-3'F1WK.

Először lássuk, mely megszorítások az automatára magára nem jelentenek megszorítást az elfogadott nyelvosztályra.

Az 5' → 3' WK-automatákkal elfogadott nyelvek osztályai közül az alábbiak egybeesnek:

5'-3'WK = 5'-3'SWK = 5'-3'1WK = 5'-3'FWK = 5'-3' FSWK = 5'-3' F1WK,

és így megegyeznek a Chomsky-féle LIN nyelvosztállyal.

Bizonyítás: Haladjunk sorban:

Kiindulva egy tetszőleges 5'→3' WK-automatából, új állapototok bevezetésével elérhetjük, hogy minden lépésben csak az egyik fej léphessen (hasonlóan a hagyományos WK-automatáknál mutatott módon), így egy az eredetivel ekvivalens 5'→3' SWK-automata állítható elő.

Továbbá, egy 5'→3' SWK-automatából kiindulva annak átmenetei helyett olyan átmenetek láncait vezethetjük be, megfelelő új állapotok bevonásával, amelyekben minden fej minden lépésben maximum egy betűt olvashat. Azok az átmenetek pedig, amikben nem történik olvasás a szokásos módon (ahogy pl. a véges automatáknál) kiküszöbölhetőek. Ez alapján (a hagyományos WK-automatáknál is mutatott módon) elérhető, egy az eredetivel ekvivalens 5'→3' 1WK-automata.

Tekintsünk most egy 5'→3' 1WK-automatát. Figyeljük meg, hogy bármely molekula elfogadásakor az utolsó átmenetben a fejek közelségét már érzi az automata, az érzékenységi paraméter értéke nem +∞. Tekintsük azokat az átmeneteket, amikkel befejeződhet az input feldolgozása, vagyis ezesetben valamelyik fej elolvassa az utolsó betűt. Minden ilyenben 1 az érzékenységi paraméter értéke 5'→3' 1WK-automaták esetén. Ekkor megtehetjük, hogy töröljük (nem engedjük meg) azokat az átmeneteket, amelyek 1 érzékenységi paraméter mellett nem elfogadó állapotba vezetnek. Ennek köszönhetően az így módosított automatákkal csak akkor lehet egy molekulát végig olvasni, ha azt el kell fogadnia az automatának. Így, ha ezekben minden állapotot végállapotnak tekintünk, akkor sem változik meg az elfogadott nyelv. Tehát az első három ekvivalenciát beláttuk (a fordított irány minden esetben triviális).

Ráadásul az utóbb megkonstruált automata, ami az előző konstrukciókon végig haladva bármely (rögzített) WK-automatával ekvivalensen megkonstruálható, nem csak FWK, de 1WK is, tehát F1WK és emiatt FSWK is egyben.

Ezzel a bizonyítást befejeztük.

QED.

Tehát az automaták előbb említett bizonyos csoportjai képesek a teljes LIN osztály elfogadására.

Lássuk a többi 5'→3' WK nyelvcsaládra vonatkozó hierarchia eredményeket. Tekintsünk most olyan automatákat, amik elfogadó ereje is korlátozott.

Az NSWK és N1WK közti különbség, hogy, míg az előző több betűs sztringek olvasására is képes egy-egy átmenet során, a második csak betűk olvasására képes.

Belátható, hogy egy NSWK-automata által elfogadott sztring nyelv az

(u1 + u2 + ... + un)*(w1 + ... + wk)(v1 + ... + vm)*

alakba írható, ahol u1, ..., un az első fej által egy átmenetben olvasható sztringek (+∞ érzékenységi paraméter mellett), v1, ..., vm pedig az alsó szálon (+∞ paraméter mellett) olvasható sztringek komplenterei, valamint w1, ..., wk az érzékenységi paraméter nem +∞ értékei esetén, a fejek (közeli) találkozásakor általuk olvasható véges sok lehetőség alapján adható meg.

2. Következmény. Az 5'→3' NSWK által elfogadott nyelvek speciális reguláris nyelvek, vagyis 5'-3' NSWK ⊊ REG .

2. Lemma. Az 5'→3' N1WK-automatákkal elfogadott nyelvek osztálya valódi része az 5'→3' NSWK-automatákkal elfogadott nyelvek osztályának:

5'-3' N1WK ⊊ 5'-3' NSWK.

Bizonyítás: A tartalmazás a két osztály definíciójából következik. A valódi tartalmazás belátásához pedig tekintsük az

nyelvet. Mivel egy N1WK-automata csak betűnként tud olvasni, könnyen belátható, hogy nem lehet képes L elfogadására.

QED.

3. Lemma. Az 5'→3' NSWK-automatákkal elfogadott nyelvek osztálya valódi része a az 5'→3' NWK-automatákkal elfogadott nyelvek osztályának:

5'-3' NSWK ⊊ 5'-3' NWK.

Bizonyítás: A tartalmazás a definíció alapján triviális.

A valódi tartalmazáshoz: pl. a palindrom-molekulák nyelve, amely 28. feladatban szerepelt 5'-3' NWK nyelv. Viszont, mivel ez nem reguláris nyelv, nem lehet 5'-3' NSWK nyelv.

QED.

4. Lemma. Az 5'→3' NWK-automatákkal elfogadott nyelvek osztálya valódi része a LIN nyelvosztálynak:

5'-3' NWKLIN.

Bizonyítás: Mivel a tartalmazás az előző eredmények és a definíciók alapján nyilvánvaló, elegendő egy olyan lineáris nyelvet megadnunk, amely nem 5'-3' NWK nyelv. Ehhez tekintsük az

reguláris nyelvet. Belátható, hogy ez a nyelv nem fogadtatható el 5'→3' NWK-automatával.

QED.

Az előbbi bizonyítások azt is mutatják, hogy 5'-3' NWKREG és REG ⊄ 5'-3' NWK, tehát e két osztály a halmazelméleti tartalmazási relációt tekintve nem összemérhető.

Az 5'→3' WK-automatákkal elfogadott nyelvek hierarchiája megtekinthető a 6.8. ábrán Hasse-diagram formájában.

A továbbiakban tekintsük a determinisztikus (érzékeny) 5'→3' WK-automatákat.

6.2.4. 2detLIN nyelvek

Az alfejezetet néhány további formális definícióval kezdjük.

10. Definíció. Egy G = (N, T, S, H) lineáris nyelvtant k-arányú lineáris nyelvtannak hívunk (ahol k ∈ ℚ, k ≥ 0), ha minden egyes AuBv alakú (A, BN, u, vT*) szabályára teljesül, hogy

A k-arányú lineáris nyelvek osztályába, amit k-LIN jelöl, pontosan azon L nyelvek tartoznak, amelyekhez van olyan k-arányú lineáris nyelvtan, ami L-t generálja (valamely k értékre).

Akkor mondjuk, hogy egy nyelvtan fix-arányú lineáris, ha k-arányú lineáris valamely k ∈ ℚ értékre. A fix-arányú lineáris nyelvek a fix-arányú lineáris nyelvtanokkal generálhatóak, ezt a nyelvosztályt fixLIN jelöli.

Speciálisan a k = 1 esetben a páros lineáris elnevezés is használt, mind a nyelvtanra, mind a generált nyelvekre.

A fix-arányú lineáris nyelvek halmaza tehát tartalmazza a k-arányú nyelveket minden nemnegatív k racionális számra.

Figyeljük meg, hogy, speciálisan, a k = 0 esetben a definíció éppen a reguláris nyelvtanokat, illetve ennek megfelelően a reguláris nyelveket adja vissza.

Köztudott, hogy a palindrómák (tükörszavak) nyelve páros lineáris.

Emlékeztetőül, az alfejezet címében is szereplő osztály, 2detLIN = det5'-3'WK a determinisztikus (érzékeny) 5'→3' WK-automaták által elfogadott nyelvek osztálya. Most lássuk e nyelvosztály viszonyát az imént definiált speciális lineáris nyelvekhez viszonyítva.

14. Tétel.Minden fix-arányú lineáris L nyelvhez van olyan determinisztikus 5'→3' WK-automata, ami elfogadja L-et, vagyis

fixLIN ⊆ 2detLIN.

Bizonyítás: A bizonyítás konstruktív. Legyen adott egy G = (N, T, S, H) k-arányú lineáris nyelvtan, valamilyen adott értékre. Ekkor az általánosság csorbítása nélkül feltehetjük, hogy G-ben:

  • minden AuH szabályra, ahol uT*, teljesül, hogy ∣u∣ ≤ n + m;

  • minden AuBvH szabályra, ahol A, BN, u, vT*, teljesül, hogy ∣u∣ = m, ∣v∣ = n.

(Ha nem így lenne, akkor új nemterminálisok bevezetésével a nyelvtan az eredetivel ekvivalens ilyen alakúra hozható).

Legyen (úgy, hogy teljesüljön, minden aT-re), és legyen Legyen qfN. Ekkor definiáljuk az M = (V, ρ, N ∪ {qf}, S, {qf}, δ) automatát az R = {0,1..., m + n,+ ∞} érzékenységi paraméterekkel a következő átmenetfüggvénnyel:

  • minden AuH szabályra, legyen

  • minden AuBvH szabályra, legyen

    • ahol v' a v komplementer sztringje; és

    • legyen

Ekkor könnyen belátható, hogy M éppen a G által generált nyelvet fogadja el a felsőszálon.

Most megmutatjuk, hogy van olyan M' automata, ami ekvivalens M-mel és determinisztikus. Az M' automatában a megtett lépések száma egyértelműen meghatározza a fejek helyét, amíg azok távolsága le nem csökken az érzékenységi távolságra. Eközben a folyamat közben minden lépés után a lehetséges állapotok egy részhalmaza lehet az, amiben az automata megtalálható lehet. Mivel az állapothalmaz véges, a lehetséges részhalmazok száma is véges. A folyamat ugyanúgy szimulálható véges 5'→3' WK-automatával, mint ahogy a hagyományos nemdeterminisztikus véges automaták is szimulálhatóak determinisztikus véges automatákkal. Amikor a távolság a fejek közt az érzékenységi távolság alá csökken (vagyis ≤ m + n) már csak véges sok lehetőség van, amit ugyancsak képes egy determinisztikus automata ellenőrizni.

Ezek alapján készíthető minden fixLIN nyelvhez azt elfogadó determinisztikus 5'→3' WK-automata.

QED.

Tekintsük most a következő feladatokat.

31. Feladat. Tekintsük a G = ({S, A, B}, {a,b}, S, H) -arányú lineáris nyelvtant, amiben H = {SaaSaaa, SbbAaaa, Aaaaa, AbbBbbb, Bbab}.

Készítse el azt a determinisztikus 5'→3' WK-automatát, amely a G által generált nyelvet fogadja el.

32. Feladat. Tekintsük a G = ({S, A, B}, {a,b,c}, S, H) nyelvtant, ahol H = {SaaAb, AaaAb, A → λ, SbBaaa, BbBaaa, Bb, Bbb}.

Konstruálja meg azt a determinisztikus 5'→3' WK-automatát, amely a G által generált nyelvet fogadja el.

Figyeljük meg, hogy az utóbbi feladatban szereplő nyelv nem fixLIN nyelv, nincs olyan k, amire generálható lenne k-arányú lineáris nyelvtannal. Az előző tételben szereplő tartalmazás valódi:

3. Követelmény. Van olyan 2detLIN nyelv, amely nem fixLIN nyelv, tehát

fixLIN ⊊ 2detLIN.

A 2detLIN nyelvosztály néhány érdekes tulajdonságával folytatjuk:

15. Tétel. A halmazelméleti tartalmazási relációt tekintve a 2detLIN nyelvosztály nem összemérhető a determinisztikus egyfordulós veremautomaták által elfogadott detLIN nyelvosztállyal.

Bizonyítás: A tétel bizonyítása két példával történik. A 2detLIN osztályba tartozó tükörszavak nyelve köztudottan nem detLIN nyelv, a veremautomata csak nemdeterminisztikusan tudja megtalálni a szó közepét, ahol „fordulnia" kell. Ezzel szemben a {anban} ∪ {anca2n} nyelvnél a veremautomata tudja mikor kell fordulnia, sőt azt is, hogy a két halmaz közül melyikben való ellenőrzést kell folytatnia, ezzel szemben 5'→3' WK-automatával determinisztikusan nem lehet ezt a nyelvet elfogadni.

QED.

Szemben a k-arányú lineáris nyelvek halmazaival, a 2detLIN osztály nem zárt az unió műveletre (elég az előző bizonyításban használt {anban} ∪ {anca2n} nyelvre gondolni, melynek mindkét tagja külön-külön 2detLIN nyelv.

A lineáris nyelvek halmaza, a fixLIN és a 2detLIN nyelvekkel egyetemben, nem zárt a konkatenáció és a Kleene-iteráció műveletekre sem.

33. Feladat. Adjon meg olyan L 2detLIN nyelvet, amelyre sem L2, sem L* nem lineáris.

Most tekintsük a determinisztikus 5'→3' WK-automaták speciális változatait. Itt is vannak olyan megszorítások, amelyek az elfogadott nyelveket tekintve nem jelentenek változást az eredeti 2detLIN osztályhoz képest.

16. Tétel. A determinisztikus 5'→3' FWK, SWK, 1WK, FSWK és F1WK-automatákkal elfogadott nyelvek osztálya megegyezik a 2detLIN osztállyal:

det5'-3'FWK = det5'-3'SWK = det5'-3'1WK = det5'-3'FSWK = det5'-3'F1WK = 2detLIN.

Bizonyítás: A bizonyítás pontosan ugyanúgy megy, mint a 13. tétel bizonyításában, figyelembe véve, hogy ha az eredeti automata determinisztikus, akkor a megkonstruált automata is lehet determinisztikus.

QED.

Nézzük a hierarchia alján álló nyelvosztályokat.

17. Tétel. A determinisztikus 5'→3' NSWK (illetve N1WK) automaták által elfogadott nyelvosztályok valódi részhalmazai a (nemdeterminisztikus) 5'→3' NSWK (illetve N1WK) automaták által elfogadott nyelvek osztályainak:

det5'-3'NSWK ⊊ 5'-3'NSWK det5'-3'N1WK ⊊ 5'-3'N1WK.

Továbbá, a determinisztikus 5'→3' N1WK automaták által elfogadott nyelvosztály valódi részhalmaza a determinisztikus 5'→3' NSWK automaták által elfogadott nyelvosztálynak:

det5'-3'N1WKdet5'-3'NSWK.

Bizonyítás: Vegyük észre, hogy a determinisztikus 5'→3' NSWK (és így az N1WK) automatákban, azokban az átmenetekben, amikben a fejek távol vannak egymástól (+∞ paraméterrel), mindig csak az egyik fej léphet, a másik nem mozdulhat, amíg elég közel nem ér a két fej egymáshoz, ennek megfelelően az elfogadott nyelvek osztálya még speciálisabb reguláris nyelveket tartalmaz, mint a nemdeterminisztikus esetben. Ezekkel a determinisztikus automatákkal éppen az (x1 + x2 + ... + xi)*(z1 + ... + zj), illetve az (z1 + ... + zj)(x1 + x2 + ... + xi)* alakú reguláris nyelvek fogadtathatók el, ahol x1, x2, ..., xi, z1, ..., zjV+ az NSWK esetben és x1, x2, ..., xi, z1, ..., zjV az N1WK esetben.

Ezzel a tétel mindhárom állítását beláttuk.

QED.

18. Tétel. A determinisztikus 5'→3' WK-automatákkal elfogadott nyelvosztályok között fennállnak a következő relációk:

1.

det5'-3'NWK ⊊ 2detLIN

2.

det5'-3'NSWKdet5'-3'NWK

Bizonyítás: A tartalmazás a definíciók alapján nyilvánvaló. A tartalmazási relációk valódiságának belátásához példát adunk olyan nyelvekre, amelyek az egyik, a jobboldali osztályba beletartoznak, de a másikba, a baloldali osztályba nem.

Az első állításhoz használjuk a G = ({S, A, B}, {a,b,c}, S, H) nyelvtan által generált nyelvet, ahol

H = {SaAa, SbBb, AcBc, AaSb, AbSa, B → λ}. Ez nyilvánvalóan egy páros lineáris nyelv, tehát 2detLIN nyelv, viszont megmutatható, hogy állapotnélküli determinisztikus 5'→3' WK-automatával nem lehet elfogadtatni.

A második állítás belátásához: a tükörszavak nyelve, ahogy már volt róla szó, benne van det5'-3'NWK-ben, viszont nincs benne 5'-3'NSWK-ben.

QED.

5. Lemma. A determinisztikus 5'→3' NWK automaták által elfogadott nyelvek osztálya valódi részhalmazai a (nemdeterminisztikus) 5'→3' NWK automaták által elfogadott nyelvek osztályainak:

det5'-3'NWK ⊊ 5'-3'NWK.

Bizonyítás: Tekintsük az L = {anbm ∣ 0 ≤ n, 2nm ≤ 3n}, amit a G = ({S}, {a,b}, S, H) nyelvtannal generálhatunk, ahol

H = {SaSbb, SaSbbb, S →λ}.

A G alapján könnyen megkonstruálható az a nemdeterminisztikus állapotnélküli automata, ami L-et elfogadja. Viszont belátható, hogy nincs olyan determinisztikus állapotnélküli automata amely L-et el tudná fogadni.

QED.

6.8. ábra - Érzékeny 5'→3' Watson-Crick véges automata nyelvosztályok hierarchiája és viszonyuk a Chomsky-féle nyelvosztályokhoz.

Érzékeny 5'→3' Watson-Crick véges automata nyelvosztályok hierarchiája és viszonyuk a Chomsky-féle nyelvosztályokhoz.

A 6.8. ábrán szereplő Hasse-diagram tartalmazza mind a nemdeterminisztikus, mind a determinisztikus (érzékeny) 5'→3' WK-automaták által elfogadott nyelvosztályokat. Az ábrán kék színnel jelöltük a Chomsky hierarchia osztályait, pirossal a determinisztikus automatákkal elfogadtatható osztályokat (ideértve pl. a detCF, a determinisztikus végállapottal elfogadó veremautomaták által elfogadott nyelvosztályt is), zöld szín pedig jelzi a különböző 5'→3' WK-automaták által elfogadott nyelvosztályokat. Ha két halmaz között nem vezet irányított út, akkor azok halmazelméleti tartalmazási szempontból nem összemérhetőek, vagyis mindkettő tartalmaz a másikban nem szereplő nyelvet.

Látható, hogy a szerző által definiált 2detLIN nyelvosztály szépen illeszkedik a klasszikus Chomsky-féle nyelvosztályok hierarchiájába.

Az eddig ebben a fejezetben vizsgált automaták befejezik az inputmolekula feldolgozását, amikor a két olvasófej találkozik. Ezzel az „érzékeny" modellel ellentétben most azt a modellt tekintjük vizsgálatunk tárgyának, amely nem érzékeny, a fejek találkozását nem érzi, tehát mindkét fejnek végig kell olvasnia az input molekula megfelelő láncát az 5' végétől a 3' végéig.

6.2.5. Végigolvasó és többször végigolvasó (nem érzékeny) 5'→3' WK-automaták

Ebben az alfejezetben olyan 5'→3' WK-automatákat nézünk meg röviden, amelyek nem érzik ha a fejek találkoznak, vagy áthaladnak egymás felett. Ennek megfelelően csak akkor tudnak dönteni egy input elfogadásáról, ha mindkét fejjel végigolvasták azt.

Végigolvasó 5'→3' WK-automaták

Nézzük tehát azt a modellt, amely szerint mindkét fejnek végig kell olvasnia az input molekula megfelelő láncát az 5' végétől a 3' végéig. Nézzük először is az állapotátmenet-függvény interpretációját és az elfogadott nyelv definícióját erre az esetre:

11. Definíció. A (nem érzékeny) végigolvasó 5'→3' WK-automata egy konfigurációján egy 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ó ahol w az input szó a felső szálon (kezdetben még a teljes molekula feldolgozandó). Akkor mondjuk, hogy egy konfigurációból közvetlenül elérhető egy konfiguráció (jelekkel: ha Az automata elfogad egy molekulát, vagyis egy w szót, ha valamely pF állapotra. Az elfogadott szavak halmaza adja az automata által elfogadott (vagy felismert) molekulahalmazt (nyelvet).

Az ilyen nem érzékeny 5'→3' WK-automatákat szokás fordított (reverse) WK-automatáknak (RWK-automata) is hívni. Ennek megfelelően az általuk elfogadott nyelvosztályok nevében a WK tag helyett RWK-t írunk (az 5'-3' előtagot pedig elhagyjuk), így is megkülönböztetve őket a korábbi automata változatok által definiált nyelvcsaládoktól.

Ugyancsak szokás a determinisztikus változatot, a korábbiakhoz hasonló értelemben definiálni.

A végigolvasó 5'→3' WK-automatákkal olyan nyelveket is el tudunk fogadni, amelyeket az érzékeny, és a fejek találkozásánál a feldolgozást abbahagyó változatokkal nem. Tekintsünk néhány érdekes példát.

23. Példa (a többszörös megfelelés nyelve). A 6.9. ábrán látható determinisztikus RWK-automata az {anbncnn > 0} nyelvet fogadja el. Az automata működése nagyon hasonlít a 17. Példában mutatott hagyományos WK-automata működéséhez, az ellenőrzés itt is blokkok hosszának összehasonlításával (egyszerre olvasásával) megy, és egy blokkot kétszer is olvas az automata.

6.9. ábra - Végigolvasó 5'→3' Watson-Crick véges automata amely a többszörös megfelelés nyelvét fogadja el.

Végigolvasó 5'→3' Watson-Crick véges automata amely a többszörös megfelelés nyelvét fogadja el.

Nagyon hasonló módon működik a következő példa is.

24. példa. A 6.10. ábrán látható determinisztikus RWK-automata az {anbmcndmn, m > 0} nyelvet fogadja el. Az ellenőrzés itt is blokkok hosszának összehasonlításával (egyszerre olvasásával) megy.

6.10. ábra - Végigolvasó 5'→3' Watson-Crick véges automata amely a keresztfüggőségek nyelvét fogadja el.

Végigolvasó 5'→3' Watson-Crick véges automata amely a keresztfüggőségek nyelvét fogadja el.

25. Példa. Legyen M = ({a,b,c}, id, {q}, q, {q}, δ) egy állapotnélküli RWK-automata, ahol

(Nincs más definiált átmenet.)

Ha csak azok az elfogadott szavak érdekelnek minket, amik a felső láncon a+b+c+ alakúak, akkor minden ilyen elfogadott molekula alakú. Ekkor a molekula feldolgozása a következőképpen megy:

⊢* ha kn; vagy

⊢* ha nk.

Ha k ≠ n, akkor marad a a felsőszálon, vagy c az alsószálon, amit az M nem tud feldolgozni. Tehát a molekula feldolgozása csak akkor folytatható, ha n=k. Ekkor viszont:

⊢* ⊢*

Ekkor, ⊢* ha km; vagy

⊢* ha mk.

A számítás csak akkor folytatható, ha k = m, vagyis

⊢* ⊢*

Ez viszont azt jelenti, hogy az ilyen inputot pontosan akkor fogadja el az M automata, ha n = m = k, vagyis anbncn alakú, valamely n ≤ 1 értékre.

Ez a nyelv viszont egy nem környezetfüggetlen nyelv. Ezt úgy kaptuk, hogy az M automata által elfogadott L nyelvnek vettük a metszetét a reguláris a+b+c+ nyelvvel. Mivel a környezetfüggetlen nyelvek zártak a reguláris nyelvekkel való metszetképzésre, az eredeti L nyelv sem lehet környezetfüggetlen.

A következő példa elve is hasonló.

26. Példa. Legyen M = ({a,b,c}, id, {q0,p,r,q}, q0, {q0,p,r,q}, δ) egy F1RWK-automata, ahol

Tekintsük azokat az elfogadott szavakat, amik a felső láncon a+b+c+ alakúak, akkor minden ilyen elfogadott molekula alakú.

Az előző feladatban mutatott érveléshez hasonló módon itt is belátható, hogy csak anbncn alakú ilyen szavakat fogad el M, aminek következtében ez az automata is egy nem környezetfüggetlen nyelvet fogad el.

Amint láthatjuk a végigolvasás segítségével nem lineáris, sőt nem környezetfüggetlen nyelveket is viszonylag könnyen fogadhatunk el ezekkel a véges automatákkal. Az elfogadási erejük kulcsa abban rejlik, a hagyományos WK-automatákhoz hasonlóan, hogy a két fej összehangoltan mozoghat, és az input egyes részeit mindkét fej olvassa, ezzel lehetővé téve/megkönnyítve/meggyorsítva az input egyes részeinek összehasonlítását.

34. Feladat. Adjon meg olyan RWK-automatát, amely az {anbmcnbmann, m > 0} nyelvet fogadja el.

Tekintsük a különböző korlátozásokkal rendelkező RWK-automaták által elfogadott nyelvosztályokat.

Egyrészt a legegyszerűbb típusoknál mindegy milyen irányban haladnak a fejek, ha nem hangolhatjuk össze a mozgásukat sem állapotok, sem egyszerre lépés segítségével.

6. Lemma. A legegyszerűbb végigolvasó automaták csak speciális reguláris nyelvek elfogadására képesek:

N1WK = N1RWKNSWK =NSRWKREG.

Bizonyítás: Az N1RWK-automatákban, ugyanúgy, mint az N1WK-automatákban, egyszerre csak az egyik fej léphet és az is csak egy betűt olvashat egy lépésben, így az a T* nyelv fogadható el, amelynek minden betűjére értelmezve van átmenet a felső, és annak komplementerére az alsó fej által.

Tekintsük most az NSRWK-automatákat. Ezekben ugyancsak függetlenül mozoghat a két fej, ennek megfelelően pont azok a nyelvek fogadhatóak el, amelyek molekuláit, mindkét fej végig tudja olvasni: ezek pedig (u1, ..., un)* ⋂ (v1, ..., vm)* alakba írhatóak valamely {u1, ... un, v1, ... vn} véges szóhalmazzal, ugyanúgy, mint az NSWK-automaták esetén.

QED.

7. Lemma. Az állapotnélküli RWK-automaták nagyobb osztály elfogadására képesek, mint az állapotnélküli egyszerű RWK-automaták, vagyis az

NSRWKNRWK tartalmazás valódi.

Bizonyítás: A tartalmazás a definíció miatt nyilvánvaló. Azt kell csak megmutatnunk, hogy bővebb a második osztály. Láttuk a 6. Lemmában, hogy NSRWKREG, viszont a 25. Példában mutattunk olyan NRWK-automatát, amely nem reguláris nyelvet fogad el.

QED.

8. Lemma. Az RWK-automaták az NRWK nyelvek osztályánál nagyobb osztály elfogadására képesek:

NRWKRWK.

Bizonyítás: A tartalmazás nyilvánvaló. Mivel az állapotnélküli automaták nem tudják megkülönböztetni a kezdőállapotukat a végállapotuktól, minden elfogadott w szóra w+ is elfogadásra kerül. Az egy szóból álló reguláris nyelv {aaab} nem bír ezzel a tulajdonsággal, így nem tudja állapotnélküli NRWK-automata elfogadni.

QED.

Egyrészt a 25. Példában megmutattuk, hogy az NRWK-automaták képesek nagyon összetett nyelvek elfogadására, másrészt az előző bizonyításból kiderült, hogy nagyon egyszerű nyelveket viszont nem tudnak elfogadni. Ennek oka, hogy a két fej összehangolt mozgásával egyrészt bonyolult dolgok ellenőrzésére is képesek, viszont állapotok nélkül, nem tudnak emlékezni még egyszerű dolgokra sem (pl. hogy már elkezdték a munkát)...

9. Lemma. Az F1RWK-automaták a reguláris nyelvek osztályánál nagyobb osztály elfogadására képesek:

REGF1RWK.

Bizonyítás: Először lássuk be, hogy F1RWK-automatákkal minden reguláris nyelv elfogadtatható: használjuk ehhez a felső fejet, mint az eredeti reguláris nyelvet elfogadó hagyományos automata olvasófejének szimulációját. Ha az eredeti automata végállapotban van, akkor megengedjük, hogy a szimuláló F1RWK-automata átmenjen egy olyan állapotba, amiben a felső fej már nem olvashat, az alsó fej viszont egyszerűen végig lépkedhet az alsó láncon (természetesen 5'→3' irányban). Ennek megfelelően pontosan azok a szavak lesznek elfogadva, amiket az eredeti véges automata is elfogad.

A 26. Példában láttuk, hogy F1RWK-automatával nem reguláris nyelv is elfogadható, így ez a tartalmazás valódi.

QED.

A hierarchia másik végén olyan RWK-automaták vannak, melyeknél a korlátozás nem jár az elfogadott nyelvosztály szűkülésével az RWK osztályhoz képest.

10. Lemma. A végigolvasó 5'→3' WK-automatákkal elfogadott nyelvek osztálya megegyezik a végigolvasó 5'→3' 1WK-automatákkal elfogadott nyelvek osztályával, illetve a végigolvasó 5'→3' FSWK-automatákkal elfogadott nyelvek osztályával (illetve a köztük levő nyelvosztályokkal), vagyis

RWK = SRWK = 1RWK = FRWK = FSRWK.

Bizonyítás: Ezen típusú WK-automaták esetén a megfelelő állítások bizonyítása analóg módon megy a hagyományos automatákra tett ugyanilyen jellegű állítások bizonyításával, amiket korábban bemutattunk.

QED.

Az 6.11. ábra mutatja az RWK nyelvosztályok hierarchiáját, láthatjuk, hogy az egymáshoz képesti viszonyuk megegyezik a hagyományos WK-automaták nyelvosztályainak hierarchiájával.

6.11. ábra - Végigolvasó 5'→3' Watson-Crick véges automata nyelvosztályok hierarchiája és viszonyuk a Chomsky-féle nyelvosztályokhoz.

Végigolvasó 5'→3' Watson-Crick véges automata nyelvosztályok hierarchiája és viszonyuk a Chomsky-féle nyelvosztályokhoz.

19. Tétel. Minden RE nyelv felírható egy RWK nyelv homomorf képeként.

Bizonyítás: A bizonyításnak csak a vázát írjuk le. Legyen adott az L rekurzívan felsorolható nyelv, ekkor van olyan determinisztikus TM Turing-gép, amely L-et fogadja el. Ekkor minden wL szóra a TM elfogadja w-t, a számítás véges sok lépésben véget ér. A számítás minden lépése után a TM konfigurációja, vagyis a szalagtartalom, TM állapota, illetve a fej helye könnyen leírható véges szavakkal (pl. beszúrva a TM állapotát jelző szimbólumot az aktuális szalagpozíció elé). Tudjuk, hogy TM két egymást követő konfigurációja csak minimális eltérést mutathat egymástól, amit a véges RWK-automatánk is ellenőrizni tud. Legyen ♯ speciális szimbólum, amit elválasztásra használunk. Minden wL szóra gyártsunk le azt a molekulát, amelynek felső szálán a TM egymás utáni konfigurációi vannak kódolva, egymástól ♯ jelekkel elválasztva, majd az elfogadó konfigurációt követően két ♯ jel után a szalag eddigi tartalmának fordítottja jön (visszafele írva a kód, és az eredeti jelek helyett azok komplementer jeleit használva). Az így készített molekula palindrom-molekula.

Vegyük a következő elven működő RWK-automatát. Először a második fej előremegy az első ♯ jelhez. Ezután a két fej együttesen olvassa a molekula megfelelő részén levő kódokat. Az automata ellenőrzi, hogy a második fej által olvasott konfiguráció valóban az első fej által olvasott konfiguráció rákövetkezője-e. Ha ez így van, akkor mindkét fej a ♯ jel elolvasása után, átlép a molekulában tárolt következő konfigurációkra, és azokra végzi az ellenőrzést.

Amikor az alsó fej, a kettős ♯ jelhez ér, ott megvárja a másik fejet. Eközben a felső fej az utolsó molekulában tárolt konfigurációt olvassa, és ellenőrzi, hogy valóban elfogadó konfiguráció-e.

Amennyiben az eddigi ellenőrzés sikeres volt (és csak akkor) folytatódik a munka, a két fej egyszerre indul középről, és ellenőrzik, hogy a molekula valóban palindrom-e, vagyis tényleg ugyanazok a konfigurációk vannak mindkét oldalon a megfelelő sorrendben tárolva a molekulában. Ha ez is egyezik, és csak ekkor az RWK-automata elfogadja az input molekulát, illetve annak felső szálán levő kódot.

Ha a felső szálon a kiinduló konfigurációban szereplő w input szót speciális megjelölt ábécével írjuk (persze ezt az ellenőrzéskor is figyelembe véve), akkor egy olyan homomorfizmussal, ami a jelöletlen betűkhöz a λ üresszót, a jelölt betűkhöz pedig ezek jelöletlen megfelelőit rendeli, éppen a w szót kapjuk. Ennek megfelelően éppen az L rekurzívan felsorolható nyelv áll elő az RWK-automatánk által elfogadott nyelvre a megadott morfizmust alkalmazva.

QED.

Az előző tétel következménye, hogy nagyon komplex nyelvek elfogadására képesek a végigolvasó 5'→3' WK-automaták, ennek megfelelően pl. annak eldöntése, hogy egy ilyen automata által elfogadott nyelv üres-e vagy véges-e, algoritmikusan nem eldönthető probléma.

Az alfejezet zárásaként, mielőtt további végigolvasó 5'→3' WK-automata modelleket tekintenénk, egy érdekes, a könyv írásakor (még) NYITOTT KÉRDÉSRE hívjuk fel a figyelmet.

Megoldandó (Kutatási) Probléma: Láthattuk, hogy vannak olyan RWK nyelvek, amelyek nem lineárisak. Mégsem ismert a LIN és RWK nyelvosztály kapcsolata. Bizonyítandó, vagy cáfolandó, hogy LINRWK.

Érzékeny végigolvasó automaták

Mielőtt továbblépünk a következő alfejezetre, itt jegyezzük meg, hogy az érzékenység és a végig olvasás kombinálható, ilyenkor az érzékenységi paraméter értéke a R = {-∞,0,1,...,r,+∞} halmazból való. Ekkor -∞ értékkel jelezhetjük, hogy az adott átmenet akkor van engedélyezve, ha a fejek már túljutottak egymáson.

Ezek az érzékeny és mégis végigolvasó automaták minden lineáris, illetve 2detLIN nyelvet el tudnak fogadni (attól függően, hogy a nemdeterminisztikus vagy a determinisztikus modellt tekintjük). Illetve képesek az 23-26. Példákban leírt nem környezetfüggetlen nyelvek elfogadására is.

m-szer végigolvasó 5'→3' WK-automaták

Most röviden nézzük a modell egy lehetséges további kiterjesztését, amiben a fejek m-szer (m ≥ 1) összehangoltan mennek végig a molekulán, mielőtt az automata az elfogadásról döntene [Leupold, Nagy].

A determinisztikus/nemdeterminisztikus SWK és 1WK-automaták ezesetben is ugyanazt a nyelvosztályt tudják elfogadni, mint az általános determinisztikus/nemdeterminisztikus WK társaik, ha ugyanannyi futást engedünk meg.

Megmutatható, hogy pl. állapotnélküli esetben az újabb olvasások semmi pluszt nem jelentenek, az automata nem tud emlékezni korábbi futások által már ellenőrzött tulajdonságokra.

Ezzel szemben mind a nemdeterminisztikus, mind a determinisztikus 5'→3' F1WK, FSWK, FWK és WK-automatákra teljesül az, hogy az általuk elfogadott nyelvosztályok végtelen valódi hierarchiát alkotnak a környezetfüggő CS nyelvosztályon belül a megengedett futások száma alapján.

Ha m + 1 futást engedünk meg, akkor nemdeterminisztikus/determinisztikus 5'→3' F1WK-automatával szimulálható az m futást megengedő nemdeterminisztikus/determinisztikus 5'→3' WK-automata.

Az is igaz, hogy bármely n > m > 0 esetén a determinisztikus n futást megengedő 5'→3' WK-automaták által elfogadott nyelvek osztálya és a nemdeterminisztikus m futást megengedő 5'→3' WK-automaták által elfogadott nyelvek osztályai halmazelméleti szempontból nem összemérhetőek a tartalmazási relációt tekintve.

Vagyis már a csak egy futást megengedő (vagyis az előzetesen tárgyalt „végigolvasó") nemdeterminisztikus 5'→3' WK-automaták is el tudnak fogadni olyan nyelvet minden m ∈ ℕ értékre, amire determinisztikusan az m futás sem elegendő.

Másrészt viszont van olyan nyelv bármely m ∈ ℕ-re, amire determinisztikusan elég az m futás, de nemdeterminisztikusan sem lehet kevesebbel megoldani.

Csak röviden jegyezzük meg, hogy van a WK-automatáknak nem véges verziója is, ahol veremmel, vagy számlálókkal kiegészítve működik az automata az input DNS molekulák feldolgozásán.