Egy ,,kicserélési lemma'' környezet-független nyelvekre

Pontos bibliográfiai adatok:
William Ogden, Rockford J. Ross, and Karl Winklmann. An ``interchange lemma'' for context-free languages. SIAM Journal on Computing, 14(2):410-415, May 1985.

Rövid cím: Kicserélési lemma.

A cikk egy új szükséges feltételt ad környezet-független nyelvekre, majd példát is ad az alkalmazására: a lemma segítségével belátja, hogy nem környezet-független egy olyan nyelvről, amely sokáig ellenállt minden hasonló bizonyítási kísérletnek.

Tétel. Legyen L egy T abc-jű környezet-független nyelv. Ekkor létezik olyan c > 0 konstans, hogy minden n ł 2 egészre, minden Q Í L ÇTⁿ halmazra és minden olyan m egészre, melyre n ł m ł 2 létezik k ł |Q|/(cn²) egész és z₁,Ľ, z_k Î Q szavak a következő tulajdonságokkal:

1. z_i = w_ix_iy_i, i = 1,Ľ, k,
2. |w₁| = |w₂| = Ľ = |w_k|,
3. |y₁| = |y₂| = Ľ = |y_k|,
4. m ł |x₁| = |x₂| = Ľ = |x_k| > m/2, és
5. w_ix_jy_i Î L minden i,j Î {1,2,Ľ, k} esetén.

A bizonyítás Chomsky normálformában levő nyelvtanokhoz tartozó levezetési fák levelei számlálásának segítségével történik.

A cikk az alkalmazásra is példát ad: megmutatja, hogy a ,,dadogó'' szavak (azaz az xyyz alakú szavak, ahol y nem üres) nyelve hárombetűs abc felett nem környezet-független.

Szavak kombinatorikus tulajdonságai és a Chomsky osztályok kapcsolata

Pontos bibliográfiai adatok:
Dömösi Pál et al. Some combinatorial properties of words, and the Chomsky hierarchy. In Proc. Internat. Conf. ``Words, Languages and Combinatorics, II'', Kyoto, Japan; eds.: M. Ito and H. Jürgensen, pages 105-123. Singapore: World Scientific, 1992.

Rövid cím: Kombinatorikus tulajdonságok.

Jelöljük Q-val a primitív szavak nyelvét, azaz azokat a szavakat, amelyek nem állnak elő más szó hatványaként. (Formálisan Q = T⁺\{w^m | w Î T^*, m ł 2}, ahol T egy legalább kétbetűs abc.) Sokat kutatott téma, hogy vajon Q környezet-független-e, a sejtés az, hogy nem. Jelen cikk nem dönti el a kérdést, de belátja, hogy Q teljesít három olyan feltételt, az Ogden, az erős Bader-Moura és a Sokolowsky feltételt, amelyet minden környezet-független nyelv teljesít. A cikk egy negyedik feltételt is vizsgál, ami szükséges feltétele minden környezet-független nyelvnek, a Parikh szemilinearitást. Megmutatja, hogy QÇ(a^*b)ⁿ (ahol n ł 1 egész) Parikh szemilineáris, tehát ez a támadási kísérlet is kudarcot vall. A dolgozat utolsó része általánosan vizsgál bizonyos nyelvi tulajdonságokat, különös tekintettel azok eldönthetőségére és elhelyezkedésükre a Kleene féle aritmetikai hierarchiában.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a Ogden feltételt, ha létezik olyan n ł 2 egész, melyre z Î L esetén, ha legalább n+1 pozíciót z-ben kitüntetettnek tekintünk, akkor z felbontható z = uvwxy alakban, ahol teljesülnek a következők:

1. vagy u, v és w, vagy w, x és y mindegyike tartalmaz kitüntetett pozíciót,
2. vwx legfeljebb n kitüntetett pozíciót tartalmaz,
3. minden m ł 0 számra uv^mwx^my Î L.

Tétel. Minden környezet-független nyelv teljesíti az Ogden feltételt.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a Sokolowsky feltételt, ha minden Y Í T^*, |Y| ł 2, és minden u₁, u₂, u₃ Î T^* esetén, ha {u₁xu₂xu₃ | x Î Y⁺} Í L, akkor létezik olyan x˘,x˘˘ Î Y⁺, x˘ ą x˘˘, melyre u₁x˘u₂x˘˘u₃ Î L.

Tétel. Minden környezet-független nyelv teljesíti a Sokolowsky feltételt.

Környezet-független nyelvekre adott kicserélési és pumpáló lemmák

Pontos bibliográfiai adatok:
R. Boonyavatana and G. Slutzki. The interchange or pump (DI)lemmas for context-free languages. Theoretical Computer Science, 56(3):321-338, March 1988.

Rövid cím: Feltételek összehasonlítása.

A cikk összehasonlítja a kicserélési lemmát különböző pumpáló lemmákkal: a Bar-Hillel félével, Ogdenével, ennek általánosított változatával, a fentiek lineáris változatával, valamint a Sokolowsky féle feltételekkel. Ezen felül definiál egy kicserélési feltételt lineáris környezet-független nyelvekre, és összehasonlítja a többi feltétellel. Az eredmények megmutatják, hogy a kicserélési feltételek nem összehasonlíthatóak a pumpáló feltételekkel és a kiterjesztett Sokolowsky feltétellel, de határozottan erősebbek a Sokolowsky feltételnél.

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a lineáris kicserélési feltételt, ha létezik olyan c > 0 konstans, hogy minden n ł m ł 2 egészekre, és minden Q Í L ÇTⁿ halmazra létezik R Í Q a következő tulajdonságokkal:

1. |R| ł |Q|/(cn), és
2. valamilyen i ł 0 számra {xwy | $u,v,z Î T^* : |x| = |u| = i, |w| = |z| = m, xzy,uwv Î R} Í LÇTⁿ.

Definíció. Azt mondjuk, hogy egy R Í T^*×T^* reláció nem korlátos, ha minden m számra léteznek olyan x,y Î T^* szavak, melyre |x|,|y| ł m, és R(x,y) fennáll.

Definíció. x,y Î T^* esetén x < y azt jelenti, hogy x-et úgy kaphatjuk y-ból, hogy néhány betűjét kitöröljük. Ha a törölt szimbólumok y utolsó (első) m szimbóluma közül kerülnek ki, azt így jelöljük: x < ^my (x  ^m < y). Szavak párjaira definiáljuk a következő relációt:

(x˘,y˘) < m (x,y) Ű (x˘ < xŮy˘ = y) Ú(x˘ = xŮy˘ < y) Ú(x˘ < m x Ůy˘ m < y).

Definíció. Azt mondjuk, hogy egy L Í T^* nyelv teljesíti a kiterjesztett Sokolowsky feltételt, ha minden u₁,u₂,u₃ Î T^* szóra és minden R Í T^*×T^* nem korlátos relációra, ha {u₁xu₂yu₃ | R(x,y)} Í L, akkor létezik olyan m egész, hogy minden x,y Î T^* esetén

|x|,|y| > m Ů R(x,y)\implies$x˘,y˘: (x˘,y˘) < m (x,y) Ů u1x˘u2y˘u3 Î L.

A rekurzívan felsorolható nyelvek jellemzése beszúró-törlő rendszerek segítségével

Pontos bibliográfiai adatok:
Lila Kari, Gheorghe Paun, Gabriel Thierrin, and Sheng Yu. At the crossroads of dna computing and formal languages: Characterizing recursively enumerable languages using insertion-deletion systems. In Proceedings of the 3rd DIMACS Workshop on DNA Based Computers, held at the University of Pennsylvania, June 23 - 25, 1997, pages 318-333, June 1997.

Rövid cím: Beszúró-törlő rendszerek.

A formális nyelvek elméletében a leggyakoribb generáló mechanizmus az újraírás. A természetes nyelvek vizsgálata során merült fel a gondolat, hogy az újraírás mellett, vagy helyett szövegrészek beszúrásával, vagy törlésével képezzünk új szövegeket. E módszerek a molekuláris számítások szempontjából is rendkívül fontosak, mert különböző enzimek segítségével DNS, illetve RNS molekulákon megvalósíthatóak bizonyos (a környezettől is függő) beszúrások és törlések. A cikk a beszúró-törlő rendszerek több alosztályáról belátja, hogy az általuk generált nyelv megegyezik a rekurzívan felsorolható nyelvekkel.

Definíció. Beszúró-törlő rendszeren a következő konstrukciót értjük:

g = (V,T,A,I,D),

ahol V egy abc, T Í V, A Í V^*, I,D Í V^*×V^*×V^* véges halmazok.

T a rendszerünk terminális abc-je, A az axiómák, I a beszúró, D a törlő szabályok halmaza. (u,z,v) Î I azt jelenti, hogy ha egy szóban előfordul az uv részszó, akkor u és v közé beszúrhatjuk a z szót. (u,z,v) Î D azt jelenti, hogy ha egy szóban előfordul az uzv részszó, akkor u és v közül kitörölhetjük a z szót.

x,y Î V^* esetén xŢy pontosan akkor áll fenn, ha a következők egyike teljesül:

• x = x₁uvx₂, y = x₁uzvx₂, x₁, x₂ Î V^* és (u,z,v) Î I
• x = x₁uzvx₂, y = x₁uvx₂, x₁, x₂ Î V^* és (u,z,v) Î D

Jelölje Ţ^* a Ţ reláció reflexív, tranzitív lezártját. A g által generált nyelv:

L(g) = {w Î T* | xŢ* w, x Î A}.

Nyelvek generálása kétfajta zárójelpár segítségével

Pontos bibliográfiai adatok:
Viliam Geffert. How to generate languages using only two pairs of parentheses. EIK: Journal of Information Processing and Cybernetics EIK (formerly Elektronische Informationsverarbeitung und Kybernetik), 27, 1991.

Rövid cím: Geffert normálforma.

A szerző két jól használható normálformát ad a 0. típusú nyelvtanokra.

Tétel. Minden G nulladik típusú nyelvtanhoz megadható egy vele ekvivalens G˘ nyelvtan, melynek idő- és térbonyolultsága aszimptotikusan egyenlő a G nyelvtanéval, mindössze 5 nemterminális szimbólumot használ (ezek: S˘,(,),[,]), szabályai kettő kivételével környezet-függetlenek. (A két kivétel: ()®e, és []®e.)

Tétel. Minden G nulladik típusú nyelvtanhoz megadható egy vele ekvivalens G˘ nyelvtan, melynek idő- és térbonyolultsága aszimptotikusan egyenlő a G nyelvtanéval, mindössze 5 nemterminális szimbólumot használ (ezek: S˘,X,A,B,C), szabályai egy kivételével környezet-függetlenek. (A kivétel: ABC®e.)

Fair párosító rendszerek

Pontos bibliográfiai adatok:
H. J. Hoogeboom and N. van Vugt. Fair Sticker Languages. Technical Report, L.I.A.C.S., University of Leiden, NL, Number 00-01, 2000.

Rövid cím: Fair párosító rendszerek.

1994-ben nagy vihart kavart Leonard M. Adleman cikke, amiben leírta egy kísérletét, melyben a molekuláris biológia eszközeivel megoldotta a Hamilton-útkeresés feladatának egy példáját. Az érdeklődést fokozta, hogy a köztudomásúan NP-teljes problémát sikerült polinomiális idő alatt megoldani. Módszerének formális modelljét Lila Kari, Gheorghe Paun, Grzegorz Rozenberg, Arto Salomaa és Sheng Yu adta meg 1996-ban, párosító rendszerek (matching systems, vagy sticker systems) néven. Jelen cikk ezen modellek egy speciális esetével, az ún. fair számítási módú párosító rendszerekkel foglalkozik. Megoldja azt a múlt évig megoldatlan problémát, hogy az ilyen rendszerek által generált nyelvek mindig környezet-függetlenek-e. Sőt: bebizonyítja, hogy az így generált nyelvek kódolásainak osztálya pontosan megegyezik az ún. vak egy-számlálójú gépek által elfogadott nyelvosztállyal.

Definíció. Párosító rendszeren a következő ötöst értjük:

g = (V,r,Du,Dl,A),

ahol V egy véges, nem üres abc, r Í V ×V egy szimmetrikus reláció V felett, D_u,D_l Í V⁺ felső és alsó nyúlványok véges halmaza, végül A Í V^*×V^* az axiómák véges halmaza.

Az általános és a fair számítási módú rendszerek által generált nyelvek:

L() ={x V^*  y V^* : (x,y) , x=x_0x', y=y_0y',
    (x_0,y_0) A, x' D_u^*, y' D_l^*},
L_f() ={x V^*  y V^*,n 0 : (x,y) , x=x_0x', y=y_0y',
    (x_0,y_0) A, x' D_u^n, y' D_l^n}.

Definíció. Vak egy-számlálójú gép alatt a következő ötöst értjük:
B = (Q,S,d,q_in,F), ahol Q az állapotok véges halmaza, S az input abc, q_in Î Q a kezdőállapot, F Í Q a végállapotok halmaza, és d Í Q×S×{-1,0,1}×Q az utasítások véges halmaza.

A vak egy-számlálójú gép működése hasonló a véges, nem determinisztikus automatáéhoz, csak még tartalmaz egy számlálót is. A számláló kezdetben nulla, az egyes állapot-átmenetek módosíthatják az értékét legfeljebb eggyel, és akkor fogad el a gép egy szót, ha végigolvasása után végállapotba jut, és a számláló értéke is nulla. Működése közben gépünk semmilyen módon nem függ a számláló értékétől, így azt sem tudja ellenőrizni, hogy az érték éppen nulla-e.

Betűnkénti keverés

Pontos bibliográfiai adatok:
B. Bérard. Literal shuffle. Theoretical Computer Science, 51(3), pp. 281-299, 1987.

Rövid cím: Betűnkénti keverés.

Két szó keverését a legkönnyebben a következőképp képzelhetjük el: az abc betűi kártyalapok. Az abc feletti szavak lapsorozatok. Két szó keverése úgy áll elő, hogy a lapsorozatokat (lazán a kézben tartva) egymásba csúsztatjuk. Így az egyes szavak betűi nem keverednek össze, de a két szó betűi igen. A betűnkénti keverés annyival kötöttebb, hogy a két lapsorozat ,,közös részén'' a lapoknak szigorúan felváltva kell érkezniük a két pakliból. Így keverni már csak egy ügyes kártyás tud. A keverés és a betűnkénti keverés műveletét kézenfekvő általánosítani nyelvekre is.

A keverés művelete jól használható bizonyos párhuzamos feldolgozási, illetve többpontú kommunikációs problémák modellezésében. A betűnkénti keverés ezen modellek szinkronizált változatát adja.

Ez a cikk pótolja azt a hiányosságot, hogy bár a keverés műveletét többen alaposan tanulmányozták, a betűnkénti keverést eddig nem. Közli a betűnkénti keverés pontos definícióját, alaptulajdonságait. Foglalkozik a Chomsky nyelvosztályoknak a betűnkénti keverés műveletére való zártságának kérdésével. Vizsgálja továbbá a betűnkénti keverés műveletével kapott nyelvek bizonyos tulajdonságait.

Definíció. A keverés (shuffle) műveleten a következőt értjük: x,y Î X^* esetén x  \sqcup^ y = {x₁ y₁ Ľx_n y_n | n ł 1, x = x₁Ľx_n, y = y₁Ľy_n, x_i, y_i Î X^* (1 Ł i Ł n)}.

Tétel. A keverés művelet kommutatív, asszociatív. Az L₀, L₁, L₃ nyelvosztályok zártak a keverés műveletére nézve.

Képnyelvek tulajdonságainak eldönthetetlenségéről

Pontos bibliográfiai adatok:
D. Robilliard et D. Simplot. Undecidability of existential properties in picture languages. Theoretical Computer Science, 233, 2 (1999), 51-74.

Rövid cím: Képnyelvek.

A cikk három módszert is leír, hogy hogy jelenthetnek meghatározott abc feletti szavak síkbeli képeket. Ilyen módon szavak nyelvéből képnyelveket kapunk. A dolgozat bevezeti a képek bizonyos geometriai tulajdonságait, és vizsgálja, hogy mikor eldönthető reguláris nyelvekről, hogy tartalmaznak-e olyan képrészletet, aminek meghatározott tulajdonsága van. Az eredmény a legtöbb esetben negatív: eldönthetetlen problémák sorát kapjuk ilyen módon.

Absztrakt nyelvosztályok

Rövid cím: AFL-elmélet.

A formális nyelvek elméletében gyakori feladat bizonyos konkrét nyelvosztályok jellemzése különböző szempontokból. Megfigyelhetjük, hogy amikor bizonyítjuk, hogy egy adott nyelvosztály teljesít valamilyen adott tulajdonságot, általában a nyelvosztálynak csak néhány alaptulajdonságát használjuk ki. Ez vezet ahhoz a gondolathoz, hogy ne konkrét nyelvosztályokat vizsgáljunk, hanem nyelvosztályok olyan gyűjteményét, melyben minden egyes elem teljesít bizonyos alaptulajdonságokat.

Definíció. Egy nyelvosztály AFL, ha tartalmaz legalább egy nem-üres nyelvet, és zárt a következő műveletekre nézve: unió, e-mentes lezárás, e-mentes homomorfizmus, inverz homomorfizmus, reguláris nyelvvel való metszet.

Valamennyi Chomsky-osztály AFL. Ezek után, ami tételeket ki tudunk mondani egy AFL-re, az automatikusan igaz lesz az összes Chomsky osztályra, így meg tudjuk spórolni a bizonyítások ismétlését.

A könyvrészlet definiálja az AFL fogalmát, bemutatja néhány tulajdonságát. Definiál további nyelvosztály-gyűjteményeket, és azok tulajdonságait is vizsgálja.

Logikai formulákkal definiálható naylevek

Rövid cím: Logikai formulák.

A formális nyelvek elméletében nyelvek definiálására a leggyakoribb eszközök vagy generálják, vagy elfogadják az adott nyelvet. A könyvrészlet egy ezektől különböző módszert mutat be: nyelvek definiálását logikai formulák segítségével. Ezek a formulák sokszor nagyon kényelmesen használhatóak, mivel a nyelvek intuitív definícióját formális leírássá fordítják. Gyakran könnyen és természetesen alkalmazhatóak adott nyelvekből újak definiálására is.

A szerző pontosan definiálja, hogy milyen típusú logikai formulákat használ nyelvek definiálására, és belátja, hogy az íly módon definiálható nyelvek osztálya megegyezik L₀-al.

Lindenmayer rendszerek

Rövid cím: Lindenmayer rendszerek.

A Lindenmayer rendszerek a nyelvtanokban megszokott újraíráson alapulnak, mégis három jelentős eltérést mutatnak a nyelvtanokhoz képest. Nincsenek benne külön terminális és nyelvtani jelek, így valamennyi levezetett mondatforma generált szó is egyben. Az ebből adódó hatóerő-csökkenést némiképp ellensúlyozza, hogy nem a mondatforma egy jelét írjuk egy lépésben át, hanem egyszerre, szimultán valamennyi jelét, illetve, hogy nem kezdő jelünk (axiómánk), hanem kezdő szavunk adott. Első hallásra talán meglepő, hogy bizonyos algák növekedését olyan pontosan le lehet írni L-rendszerek segítségével, hogy az elmélet a kidolgozását is némiképp az algáknak köszönheti.

A szerző definiálja az L-rendszerek néhány fajtáját, majd példát ad rájuk. Megvizsgálja a rendszerek néhány tulajdonságát, pl. zártsági tételeket bizonyít, összehasonlítja az így definiálható nyelvosztályokat a Chomsky osztályokkal, majd ejt néhány szót az L-rendszerek ún. növekedési függvényeinek érdekességeiről.

Az eldönthetőség és az el nem dönthetőség határmezsgyéjén I.

Rövid cím: Eldönthetőség I..

A tanulmány pontosan definálja az eldönthetőség és az el nem dönthetőség fogalmát, majd áttekintést ad a lehető legélesebb határokról, ami az eldőnthető problémák és a hozzájuk tartozó eldönthetetlen problémák között fekszenek. A diszkrét számítások széles köréből veszi a problémákat, az érintett modellek: diofantoszi egyenletek, a szóprobléma, Post-féle rendszerek, molekuláris számítások, regiszter-gépek, neurális hálózatok, sejtautomaták, síklefedések, síkbeli Turing-gépek. Ezek után rátér a klasszikus Turing gépek elemzésére, és egy példával fejezi be a problémák bemutatását: az ún. 3x + 1 problémát elemzi.

Az első (I.) részhez az első két fejezet: a bevezetés és a klasszikus Turing gépen kívüli modellek tartoznak.

Az eldönthetőség és az el nem dönthetőség határmezsgyéjén II.

Rövid cím: Eldönthetőség II..

A tanulmány pontosan definálja az eldönthetőség és az el nem dönthetőség fogalmát, majd áttekintést ad a lehető legélesebb határokról, ami az eldőnthető problémák és a hozzájuk tartozó eldönthetetlen problémák között fekszenek. A diszkrét számítások széles köréből veszi a problémákat, az érintett modellek: diofantoszi egyenletek, a szóprobléma, Post-féle rendszerek, molekuláris számítások, regiszter-gépek, neurális hálózatok, sejtautomaták, síklefedések, síkbeli Turing-gépek. Ezek után rátér a klasszikus Turing gépek elemzésére, és egy példával fejezi be a problémák bemutatását: az ún. 3x + 1 problémát elemzi.

A második részhez a 3, 4, 5 fejezetek tartoznak: a klasszikus Turing gépek elemzése, a 3 x + 1 probléma és a befejezés.

Kooperáló nyelvtan-rendszerek I.

Rövid cím: Nyelvtan-rendszerek I.

A klasszikus formális nyelvi elméletek olyan eszközökkel (pl. automata, nyelvtan) dolgoznak, melyek elfogadnak, vagy generálnak egy-egy nyelvet. Ez a megközelítés a hagyományos olyan területeken, mint pl. természetes nyelvek elemzése, programozási nyelvek fordítása. Az utóbbi időkben viszont egyre elterjedtebbek azok a megközelítési módok, amikben nem egy eszköz old meg egy feladatot, hanem több, viszonylag egyszerűbb eszköz együttműködve dolgozik a probléma megoldásán. A könyvrészlet a nyelvtanok fogalmát terjeszti ki ebben az értelemben: definálja a kooperáló nyelvtan-rendszerek fogalmát és megvizsgálja azok tulajdonságait.

Az első (I.) részhez a 3.1 és a 3.2 fejezetek tartoznak.

Definíció. CD grammatika rendszer alatt a következő n+2-est értjük:

G = (T,G1,...,Gn,S), ahol

• G_i = (N_i,T_i,P_i) (1 Ł i Ł n) szokásos, axióma nélüli környezet-független grammatikák, N_i a nemterminálisok halmaza, T_i a terminálisoké, P_i a szabályhalmaz,
• T Í Č_{i = 1}ⁿ T_i ,
• S Î Č_{i = 1}ⁿ N_i = N .

Kooperáló nyelvtan-rendszerek II.

Rövid cím: Nyelvtan-rendszerek II.

A klasszikus formális nyelvi elméletek olyan eszközökkel (pl. automata, nyelvtan) dolgoznak, melyek elfogadnak, vagy generálnak egy-egy nyelvet. Ez a megközelítés a hagyományos olyan területeken, mint pl. természetes nyelvek elemzése, programozási nyelvek fordítása. Az utóbbi időkben viszont egyre elterjedtebbek azok a megközelítési módok, amikben nem egy eszköz old meg egy feladatot, hanem több, viszonylag egyszerűbb eszköz együttműködve dolgozik a probléma megoldásán. A könyvrészlet a nyelvtanok fogalmát terjeszti ki ebben az értelemben: definálja a kooperáló nyelvtan-rendszerek fogalmát és megvizsgálja azok tulajdonságait.

A második (II.) részhez a 3.3, 3.4 fejezetek, valamint a befejezés tartozik.

Definíció. CD grammatika rendszer alatt a következő n+2-est értjük:

G = (T,G1,...,Gn,S), ahol

• G_i = (N_i,T_i,P_i) (1 Ł i Ł n) szokásos, axióma nélüli környezet-független grammatikák, N_i a nemterminálisok halmaza, T_i a terminálisoké, P_i a szabályhalmaz,
• T Í Č_{i = 1}ⁿ T_i ,
• S Î Č_{i = 1}ⁿ N_i = N .

Sejtautomaták

Rövid cím: Sejtautomaták.

Az ötvenes években a kutatókat foglalkoztató egyik legizgalmasabb kérdés az volt, hogy képesek-e gépek önmaguk reprodukálására. Egyfajta választ erre a kérdésre Neumann János adott, aki megalkotta 1953-ban a sejtautomatákat, biológiai motivációk alapján. Ezzel megmutatta, hogy léteznek ön-reprodukáló gépek. A sejtautomaták később a párhuzamos számítógépek egy modelljének matematikai alapját is képezték.

A sejtautomaták olyan véges állapotú automatáknak valamilyen d-dimenziós elrendezésű, minden irányban végtelen hálózata, melyben minden automata azonos működésű, és az állapot-átmenetek csak az adott automata ,,szomszédjainak'' állapotától függenek. A hálózat párhuzamosan működik, szinkronizáltan és diszkrét lépésekben.

A könyvrészlet pontosan definiálja a sejtautomaták fogalmát, példákat ad rá. Részletesebben foglalkozik két speciális esettel: a sokak által ismert életjátékkal és a lövész-osztagok szinkronizációs problémájával. Végül megmutatja azt a rendkívül fontos elméleleti tételt, hogy a sejtautomaták és a Turing-gépek képesek egymás hatékony szimulációjára, illetve bevezeti a reverzibilis sejtautomaták fogalmát. A fejezetet feladatok zárják, néhány érdekesebb feladat megoldásának ismertetése hozzátartozik a dolgozat bemutatásához.

Vissza a Formális nyelvek és automaták szeminárium lapjára.