Bibliográfia

[Bur70] A.W. Burks. Introduction. In Essays on Cellular Automata. University of Illinois Press, 1970.

[CCV97a] Judit Csima and Erzsébet Csuhaj-Varjú. Hybrid eco-grammar systems. Kézirat, kidolgozás alatt, 1997.

[CCV97b] Judit Csima and Erzsébet Csuhaj-Varjú. Teams in nonstandard eco-grammar systems. Kézirat, kidolgozás alatt, 1997.

[Csi] Judit Csima. On extended eco-grammar systems. Kézirat, kidolgozás alatt.

[CV95] Erzsébet Csuhaj-Varjú. Eco-grammar systems: recent results and perspectives. In Pǎun [Pǎu95], pages 79–103.

[CVK] Erzsébet Csuhaj-Varjú and Alica Kelemenová. Team behaviour in eco-grammar systems. Theoretical Computer Science, közlésre elfogadva.

[CVKKP93] Erzsébet Csuhaj-Varjú, Alica Kelemenová, Jozef Kelemen, and Gheorghe Pǎun. Eco(grammar) systems: a language theoretic model for AL. Manuscript, 1993.

[CVKKP94a] Erzsébet Csuhaj-Varjú, Alica Kelemenová, Jozef Kelemen, and Gheorghe Pǎun. Eco-grammar systems: a generative framework for AL. Submitted, 1994.

[CVKKP94b] Erzsébet Csuhaj-Varjú, Alica Kelemenová, Jozef Kelemen, and Gheorghe Pǎun. Eco-grammar systems, A preview. In R. Trappl, editor, Proceedings 12th European Meeting on Cybernetics and System Research, pages 941–948. World Sci. Publ., 1994.

[CVKKP97] Erzsébet Csuhaj-Varjú, Alica Kelemenová, Jozef Kelemen, and Gheorghe Pǎun. Eco-grammar sysyems: A grammatical approach to likelife interactions. Artificial Life, 3(3):1–28, 1997.

[CVPS95] Erzsébet Csuhaj-Varjú, Gheorghe Pǎun, and Arto Salomaa. Conditional tabled eco-grammar systems. In Pǎun [Pǎu95], pages 227–239.

[DM95] Jürgen Dassow and Valeria Mihalache. Eco-grammar Systems, Matrix Grammars and E0L systems. In Pǎun [Pǎu95], pages 210–226.

[FdB91] J.Doyne Farmer and Aletta d’A. Belin. Artificial Life: the coming evolution. In Ch.G. Langton et al., editors, Artificial Life II., pages 815–840. Addison-Wesley, 1991.

[HR75] Gabor T. Herman and Grzegorz Rozenberg. Developmental systems and Languages. North Holland/American Elsevier, 1975.

[KK94] Alica Kelemenová and Jozef Kelemen. From colonies to eco(grammar) systems, an overview. In J. Karhumäki, H.A. Maurer, and G. Rozenberg, editors, Proceedings Important Results and Trends in Theoretical Computer Science. Springer-Verlag, 1994.

[Pǎu95] Gheorghe Pǎun, editor. Artificial Life: Grammatical Models. Black Sea University Press, 1995.

[RS80] Grzegorz Rozenberg and Arto Salomaa. The Mathematical Theory of L-systems. Academic Press, 1980.

[Sal73] Arto Salomaa. Formal languages. Academic Press, 1973.

[tB96] Maurice ter Beek. Teams in Grammar systems. Master’s thesis, Leiden University, 1996.

Ökoszisztémák formális nyelvi modelljei

Készítette: Csima Judit Témavezető: Csuhaj Varjú Erzsébet

Budapest, 1997. április 26

Tartalom

1 Bevezetés 4 1.1 A mesterséges élet elmélet . . . . . . . . . . . . . . . . . . . . 4 1.2 Lindenmayer rendszerek . . . . . . . . . . . . . . . . . . . . . 5 1.3 Eco-grammatika rendszerek . . . . . . . . . . . . . . . . . . . 6

1.3.1 Az EG rendszerek informális definíciója . . . . . . . . . 7 1.3.2 A dolgozat felépítése . . . . . . . . . . . . . . . . . . . 9

2 Alapvető tudnivalók a formális nyelvek elméletéből 10 2.1 Nyelvek és műveletek . . . . . . . . . . . . . . . . . . . . . . . 10 2.2 Nyelvtanok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.3 Lindenmayer rendszerek . . . . . . . . . . . . . . . . . . . . . 12

3 Az eco-grammatika rendszer definíciója, példák 15

3.1 ELP ( 0L, CF ) rendszerek és nyelvek . . . . . . . . . . . . . . 15 3.1.1 Az általános definíció . . . . . . . . . . . . . . . . . . . 15 3.1.2 Az egyszerű EG rendszer definíciója, példák . . . . . . 21 3.1.3 Az ELP (0L, CF) osztályok definíciója, példák . . . . . 23

3.2 ELP ( 0L, INS ) és ELP ( 0L, REP ) rendszerek és nyelvek . . 28

3.2.1 Az ELP ( 0L, INS ) rendszerek definíója

Példák ELP ( 0L, INS ) nyelvekre . . . . . . . . . . . . 28 3.2.2 A ELP ( 0L, REP ) rendszerek definíciója

Példák ELP ( 0L, REP ) nyelvekre . . . . . . . . . . . 32

4 Hierarchia a CF, INS és REP nyelvosztályok körében 37 4.1 Az LELP ( 0L, CF ) nyelvek hierarchiája . . . . . . . . . . . . 37 4.2 Az LELP ( 0L, INS ) nyelvek hierarchiája . . . . . . . . . . . 47 4.3 Az LELP ( 0L, REP ) nyelvek hierarchiája . . . . . . . . . . . 54

5 A CF, INS és REP nyelvosztályok kapcsolata 59 6 Nyitott kérdések és további variánsok 75

6.1 Nyitott kérdések . . . . . . . . . . . . . . . . . . . . . . . . . 75 6.2 Az EG rendszerek további variánsai . . . . . . . . . . . . . . . 76

6.2.1 Kiterjesztett EG rendszerek . . . . . . . . . . . . . . . 76 6.2.2 Előre megadott team-ekkel dolgozó

EG rendszerek . . . . . . . . . . . . . . . . . . . . . . 77 6.2.3 További lehetőségek még... . . . . . . . . . . . . . . . . 78

Köszönetnyilvánítás

Köszönöm témavezetőmnek, Csuhaj Varjú Erzsébetnek, hogy megismertetett az eco-grammatika rendszerekkel és köszönöm a dolgozat elkészítéséhez nyújtott segítségét, szakmai és technikai tanácsait és figyelmes lektorálását.

1. fejezet

Bevezetés

1.1 A mesterséges élet elmélet

A mesterséges élet elmélet (Artificial Life, AL) az életet, mint rendszert vizsgálja. Létező biológiai jelenségek közös vonásait ragadja meg és olyan mesterséges modelleket hoz létre, melyek tükrözik ezeket a vonásokat. Ezeket a modelleket vizsgálva próbál új információkat nyerni a modellált jelenségről, az életről. A.W.Burks [Bur70] Neumann nyomán úgy foglalta össze az elmélet lényegét, hogy az nem más, mint egy adott folyamat logikai összefüggéseinek megismerése. Nem csak a létező életet, hanem a lehetséges életet akarjuk megismerni, azt, hogy milyenek lehetnek illetve lehetnének azok a rendszerek, melyek egyik vagy másik életszerű jelenséget mutatják. Tehát a mesterséges élet elmélet nem az élet konkrét megnyilvánulási formái iránt érdeklődik, hanem az iránt, hogy mi a közös az életjelenségeket mutató akár mesterséges, akár természetes rendszerek felépítésében. Az elmélet lényegét az [FdB91]-ben megfogalmazott elv fejezi ki leginkább: Az élet sokkal inkább folyamat, minta térben és időben, mint magában álló fizikai-kémiai jelenség. Ezt a feltevést elfogadva (legalábbis munkahipotézisnek, mely, mint látni fogjuk, igen hasznos lesz), azt is el kell fogadnunk, hogy az élet, illetve az életszerű jelenségek vizsgálatára a matematika, ezen belül is a formális nyelvek elmélete igen alkalmas. Ezt bizonyítja az a számos matematikai konstrukció is, a sejtautomaták, a Lindenmayer rendszerek különféle változatai, az eco-grammatika rendszerek, melyek mind adekvát, mind releváns leírását adják ezen jelenségeknek. Hangsúlyozni szeretnénk az adekvátság (a modell jól tükrözi a modellált jelenség főbb tulajdonságait) és a relevancia (a modell vizsgálatából új információ nyerhető a modellált rendszerről) közötti különbséget. Az adekvátságot a jó definíció biztosítja, a relevancia viszont csak az eredményekből adódhat. A dolgozatban egy matematikai modellt fogunk vizsgálni, az eco-grammatika rendszert( röviden EG rendszer). Mielőtt azonban rátérnénk erre, ismerkedjünk meg az előzményekkel.

1.2 Lindenmayer rendszerek

A sejtautomaták után a Lindenmayer rendszerek voltak az első olyan konstrukciók, melyek életszerű jelenségeket modelleztek. Az ötlet a biológiából származik, Aristid Lindenmayer nevéhez fűződik. A modellezni kívánt jelenség a sejtek fejlődése és szerveződése. Ha minden sejt állapotát egy-egy karakterrel irjuk le és 1-dimenziós rendszereket tekintünk, akkor a rendszer állapotát egy szóval jellemezhetjük. Az állapotváltozás (a sejtek szaporodása, átalakulása, elpusztulása) a szó megváltozásában jelentkezik. Az egyes sejtek változásai újraíró szabályokkal adhatók meg (például a → λ jelöli azt, hogy az a állapotú sejt elpusztul, a → aa jelöli azt, ha megduplázza önmagát). Az állapotváltozás úgy történik, hogy a szóban minden betűn egy ilyen típusú szabályt hajtunk végre, párhuzamosan. Tehát egy rendszert azáltal adunk meg, hogy mik ezek a lehetséges újraíró szabályok. Azt a technikai megkötést tesszük még, hogy minden előforduló karakter esetén lennie kell olyan szabálynak, melynek bal oldalán ez a betű áll. Ez a kikötés biztosítja, hogy a fejlődés soha se blokkolódjon. Egy ilyen rendszer nyelvet generál, azon szavak halmazát, melyek a kiindulási szóból párhuzamos újraírással, véges sok lépésben elérhetők. A fenti rendszerek az 0L rendszerek. További változatok nyerhetők, ha feltesszük, hogy minden karakter csak egy szabály baloldalán szerepelhet (ezek a determinisztikus, vagy D0L rendszerek), illetve, ha azt tesszük fel, hogy betűt nem lehet törölni (ezek a növekvő, vagy P 0L rendszerek). A lényeg azonban az, hogy egy adott szóból kiindulva, adott szabályhalmaz elemeit párhuzamosan használva szósorozatokat kapunk, melyek a rendszer időbeli viselkedését írják le, illetve nyelvet generálunk, ami –reményeink szerint– a rendszer egészéről szolgáltat információt. A Lindenmayer rendszerek valós biológiai alkalmazására sok szép példa található [HR75]-ban.

1.3 Eco-grammatika rendszerek

A Lindenmayer-rendszerek egy továbbfejlesztett változatát fogjuk vizsgálni. A modell először [CVKKP93]-ban és [KK94]-ben jelent meg, részletes tárgyalás található [CVKKP94a]-ben, [CVKKP97]-ben és [Pǎu95]-ben. A modellezni kívánt jelenség röviden a következő: ágenseknek nevezett élőlények élnek egy közös környezetben. Példaként gondolhatunk az ökoszisztémákra, ahol több állat (több állatfaj ) él egy közös térségben, de hasonló struktúrát találunk más területeken is, gazdasági, nyelvészeti, AI-beli környezetben. Alaphipotézisként feltesszük, hogy mind a környezet, mind az ágensek változnak, fejlődnek az időben. A környezet az ágensektől függetlenül fejlődik, az ágensek fejlődése viszont függ a környezet aktuális állapotától. A következőkben pontosabban megfogalmazzuk, mi is a modell, melyet eco-grammatika rendszernek, röviden EG rendszernek nevezünk. Egy eco-grammatika rendszer környezetet és néhány ágenst foglal magában. Mind az ágenseket, mind a környezetet szavak segítségével írjuk le. Az ágensek 0L szabályok párhuzamos alkalmazásával fejlődnek, a környezeten pedig újraíró szabályok szekvenciális alkalmazásával hatnak. A környezet szintén 0L szabályok párhuzamos alkalmazásával fejlődik. Az, hogy az ágensek egy adott lépésben milyen fejlődési (0L) szabályt használnak, a környezet állapotától, vagyis a környezetet leíró szótól függ. Az pedig, hogy milyen újraíró, azaz akciószabályt használnak a környezeten, a saját állapotuktól függ. Lehetséges további életjelenségek vizsgálata is az EG rendszerek keretein belül ( halál, születés, szimbiózis, stb.), ekkor az alapdefiníció módosul. Ezekben az esetekben ágens másik ágensen is végrehajthat szabályokat, az alapdefiníció azonban – amihez a dolgozatban végig ragaszkodunk – csak a környezeten való akciót engedi meg. A fent említett változatokért lásd a 6. fejezetet. Ha adott egy rendszer, azaz adottak az ágensek és a környezet, szabályaikkal együtt és adott a rendszer kezdőállapota ( a rendszert leíró szavak ), akkor nézhetjük az EG rendszer időbeli fejlődését. A rendszer dinamikájáról a lehetséges állapotsorozatok halamaza ad információt. Az EG rendszert nyelvgenerátornak is tekinthetjük, ha a fejlődés során előforduló állapotokat összegyűjtjük egy halmazba. A dolgozatban, később részletezendő okok miatt a környezet által generált nyelvet fogjuk vizsgálni (azaz a környezetet leíró szavak halmazát).

1.3.1 Az EG rendszerek informális definíciója

Ahogy már mondtuk, az EG rendszerek a multi-ágens rendszereket kívánják modellezni, ahol a környezet és az ágensek kölcsönösen hatnak egymásra; egy természetes példa az ökoszisztéma. A modell felépítésénél az alábbi hat posztulátumhoz igazodunk:

1. Egy ökoszisztéma a környezetből és néhány ágensből áll. Mind a környezetet, mind az ágenseket adott ábécék feletti szavakkal írjuk le.

2. Az ökoszisztémákban egy univerzális óra működik, amely az időt egységekre osztja. Ez az univerzális óra vezérli az ökoszisztéma tagjait, a környezetet és az ágenseket.

3. Mind a környezet, mind az ágensek fejlődési szabályokkal rendelkeznek, ezek 0L szabályok, párhuzamosan alkalmazódnak, úgy, hogy az adott szó minden betűjét egyidejűleg átírják; egy ilyen lépés (ami alatt a környezet és az ágensek fejlődnek) egy időegység alatt zajlik le.

4. A környezet fejlődési szabályai függetlenek mind a saját, mind az ágensek aktuális állapotától. Az ágensek fejlődési szabályai viszont függenek a környezet aktuális állapotától (egy adott lépésben az ágens fejlődési szabályainak csak egy részhalmaza alkalmazható).

5. Az ágensek hatnak (akciót hajtanak végre) a környezeten az akciószabályok segítségével. Ezek újraíró CF szabályok. Minden időegységben minden ágens egy akciószabályt alkalmaz, melyet az összes akciószabály egy (az ágens állapotától függő) részhalmazából választ.

6. Az ágensek akcióinak elsőbbsége van a környezet fejlődésével szemben, azaz egy időegységen belül először az ágensek végrehajtják az akciójukat a fenti módon, majd az általuk nem érintett betűkön alkalmazza a környezet a fejlődési szabályait.

Ezen hat posztulátumot elfogadva az 1. ábrán látható modellt kapjuk. Az ábrán megkülönböztetjük a környezetet és az ágenseket. A környezetet a V_{E} ábécé feletti w_{E} szó írja le, 0L szabályainak halmazát P_{E} jelöli. Minden A_{i} ágenst a V_{i} ábécé feletti w_{i} szó ír le (1 ≤ i ≤ n), az i-edik ágens fejlődési szabályainak halmaza P_{i}. Minden lépésben P_{i}-nek csak egy φ_{i}(w_{E}) részhalmaza aktív (a szaggatott vonal jelzi a w_{E}-től való függést). Ezen kívül minden ágenshez tartozik egy-egy R_{i} halmaz, ez tartalmazza az A_{i} ágens akciószabályait, melyekkel a környezeten hat. Ezeket a szabályokat szekvenciálisan használja az ágens (x → y azt jelenti, hogy x egy előfordulását y-nal helyettesíti). Minden lépésben R_{i}-nek csak egy részhalmaza aktív.

A rendszer életét az univerzális óra szabályozza, azáltal, hogy az időt egységekre osztja. Egy időegység alatt először az ágensek hatnak a környezeten az akciószabályokkal (minden ágens pontosan egy szabályt használ), majd a környezet fejlődik az ágensek által nem érintett betűkön, illetve az ágensek fejlődnek φ_{i} szerint, (ez utóbbi a környezet fejlődésével párhuzamosan zajlik). Ezt jelenti az, hogy az akciószabályoknak elsőbbségük van a fejlődési szabályokkal szemben.

[figure: P_{1}; P_{2}; …; P_{n}; fejlődési; szabályok; párhuzamos; újraírás; w_{1}; w_{2}; …; w_{n}; állapotleírás; R_{1}; R_{2}; …; R_{n}; akció-; szabályok; szekvenciális; újraírás; w_{E}; állapotleírás; P_{E}; fejlődési; szabályok; párhuzamos; újraírás; φ_{1}; φ_{2}; φ_{n}; ψ_{1}; ψ_{2}; ψ_{n}; Á; G; E; N; S; E; K; K; Ö; R; N; Y; E; Z; E; T; 1.Ábra]

A rendszer állapotát a (w_{E}, w_{1}, …, w_{n}) (n + 1)-es írja le. A (2)-(5) posztulátumok definiálják, hogyan megy át egyik állapotból a másikba a rendszer. A fejlődést az ezen (n + 1)-esekből alkotott sorozatok írják le. A rendszer által generált nyelv a környezetet leíró szavak halmaza.

Sokféle kérdés vetődik fel az EG rendszerekkel kapcsolatban:

• Véges vagy végtelen-e egy adott rendszer élete?

• Eldönthető-e ez algoritmikusan?

• Van-e végtelen nem-ciklikus fejlődés?

• Milyen hatással van az ágensek számának változtatása a rendszer működésére, illetve a generált nyelvre?

Az EG rendszer általános esetben igen bonyolult lehet, ezért a dolgozatban az EG rendszerek egy egyszerűsített változatával fogunk foglalkozni, az egyszerű EG rendszerrel. Ebben φ_{i}(w_{E}) = P_{i} és ψ_{i}(w_{i}) = R_{i} áll fenn mindig (vagyis az ágensek nem alkalmazkodnak a környezethez, és minden lépésben minden szabály alkalmazható, akár akciószabályról, akár fejlődési szabályról van szó). Az egyszerű EG rendszer két további variánsával is foglalkozni fogunk. (Ezekről részletesebb eredmények találhatók [CCV97a]-ben és [CCV97b]-ben.) Ezen rendszerek abban különböznek csak az eddig látottaktól, hogy az ágensek nem CF alakú szabályokkal hatnak a környezeten, hanem beszúró, vagy betűt betűre helyettesítő szabályok segítségével. Egy (x, y, z) alakú beszúrószabály azt jelenti, hogy az ágens az x szó után, de a z szó elé bárhová beszúrhatja az y szót. Az (a, b, c) → (a, d, c) betűt betűre helyettesítő szabály azt jelenti, hogy az abc betűhármast adc betűhármasra lehet cserélni. A pontos definíciót lásd a 3. fejezet 2. pontjában. Ezekben az esetekben is egyszerű rendszereket vizsgálunk, azaz olyan rendszereket, ahol φ_{i} és ψ_{i} nem játszanak semmi szerepet.

1.3.2 A dolgozat felépítése

A 2. fejezetben a továbbiak megértéséhez szükséges formális nyelvi definíciókat és alapvető eredményeket tárgyaljuk. A 3. fejezet tartalmazza az EG rendszer eredeti definícióját, illetve az egyszerű EG rendszer definícióját mind az eredeti (CF szabályokat használó) esetben, mind inzertáló, illetve betűt betűre helyettesítő szabályokkal dolgozó ágensek esetén. A 4. és 5. fejezet adja a dolgozat érdemi részét. A 4. fejezetben azt mutatjuk meg, hogy a különböző fajta (CF, INS illetve REP szabályokat használó ágenseket tartalmazó) EG rendszerek által generált nyelvek struktúrája nagyon hasonló a három esetben. Az 5. fejezet eredményei viszont azt mutatják, hogy a három hierarchia mégis annyira különböző, hogy bármely párt vesszük is a CF, INS, REP hármasból, lesznek olyan nyelvek, melyeket csak az egyik fajta EG rendszerrel lehet előállítani, a másikkal nem. A fejezetek végén álló tételek foglalják össze a kapott eredményeket. A 6. fejezetben további variációkat mutatunk EG rendszerekre és nyitott problémákra hívjuk fel a figyelmet.

Alapvető tudnivalók a formális nyelvek elméletéből

Ezen fejezet célja az, hogy a dolgozat megértéséhez szükséges definíciókat, klasszikus formális nyelvi tételeket megismertesse az olvasóval. Bővebb ismeretekért lásd még: [Sal73]-t, illetve a fejezetben szereplő további hivatkozásokat.

2.1 Nyelvek és műveletek

Legyen V = {a_{1}, …, a_{n}} egy véges ábécé. A V elemeit betűknek hívjuk. Egy, az ezen betűkből (esetleg nulla darabból) előálló betűsorozatot V feletti szónak nevezünk. Az üres szó (azaz, azon betűsor, amely egyetlen betűt sem tartalmaz) jele λ. A V feletti összes szó halmaza: V^{∗}; V^{+} jelöli az összes nem üres V feletti szót, azaz V^{∗} = V^{+} \ {λ}. Egy X szó hossza (jelölése |x|) a benne levő betűk száma. Az a betű előfordulásának számát x-ben |x|_{a} jelöli. alph(w) jelöli azon szimbólumok halmazát, melyek előfordulnak w ∈ V^{∗}-ban. alph(L)= ⋃_{w∈L}{alph(w)}. Ha W ⊆ V és x ∈ V^{∗}, akkor |x|_{W} = ∑_{a∈W} |x|_{a}. Egy V ábécé feletti L nyelv alatt a V^{∗} egy részhalmazát értjük. Egy L ⊆ V^{∗} nyelvet λ-mentesnek mondunk, ha λ ∉ L. Az x_{1} szó részszava x_{2}-nek (jelölése x_{1} ⪯ x_{2}), ha x_{2} = αx_{1}β alakú, ahol α, β ∈ V^{∗}. Két tetszőleges szó, w_{1} és w_{2} konkatenációja alatt w_{1}w_{2}-t értjük (a két szó egymás után írása). Két nyelv konkatenációjának az

L_{1}L_{2} = {w_{1}w_{2}|w_{1} ∈ L_{1}, w_{2} ∈ L_{2}}

nyelvet nevezzük. L_{1}, L_{2} ⊆ V^{∗} esetén a ∪, ∩ és a komplementum műveletek megegyeznek a szokásos halmazműveletekkel.

2.2 Nyelvtanok

A Chomsky-féle nyelvtan egy G = (N, T, P, S) négyes, ahol

• N és T a nemterminális, ill. terminális szimbólumok véges halmazai; N ∩ T = ∅

• S ∈ N a kezdőszimbólum

• P a helyettesítési szabályok véges halmaza, azaz P olyan (α, β) rendezett párokból áll, ahol α, β ∈ (N ∪ T)^{∗} és |α|_{N} ≥ 1

Szokás a P elemeit α → β-val jelölni, ahol α-t a szabály baloldalának, β-t pedig a szabály jobboldalának nevezzük.

A Chomsky nyelvtanokat a szabályok alakja szerint osztályozzuk. A fenti definíció a 0-típusú Chomsky féle nyelvtan definíciója. Az i-típusú (i = 1, 2, 3) nyelvtanokat úgy kapjuk, hogy P szabályaira további megkötéseket teszünk:

• i = 1, azaz a környezetfüggő nyelvtan esetén a szabályok w_{1}Aw_{2} → w_{1}xw_{2} alakúak, ahol w_{1}, w_{2} ∈ (N ∪ T)^{∗}, A ∈ N, x ∈ (N ∪ T)^{+} és S → λ csak akkor eleme P -nek, ha S nem szerepel valamely szabály baloldalán

• i = 2, azaz a környezetfüggetlen nyelvtan esetén az alábbi megszorítást tesszük: a szabályok A → x alakúak, ahol A ∈ N, x ∈ (N ∪ T)^{∗} (ezen szabályokat környezetfüggetlen vagy CF szabályoknak nevezzük)

• i = 3, azaz a reguláris nyelvtanok esetén pedig A → xB, illetve A → x alakúak a szabályok, ahol A, B ∈ N, x ∈ T^{∗}

Egy Chomsky-féle G nyelvtanban az y szó közvetlenül levezethető az x szóból (jelölése x⇒_{G}y), ha x = w_{1}αw_{2}, y = w_{1}βw_{2} és (α, β) ∈ P, w_{1}, w_{2} ∈ (N ∪ T)^{∗}.

Ha egyértelmű, hogy melyik nyelvtanban tekintjük a levezetést, akkor egyszerűen ⇒-t írunk ⇒_{G} helyett. A közvetlen levezetés tranzitív (és reflexív) lezártját ⇒^{+} (⇒^{∗}) jelöli.

A G által generált nyelvnek az

L(G) = {w ∈ T^{∗}|S⇒^{∗}w}

nyelvet nevezzük. Azaz L(G) azon terminális szavak halmaza, melyek véges sok lépésben levezethetők S-ből. A G nyelvtan által generált nyelvet i-típusúnak nevezzük, ha G i-típusú nyelvtan. A 0-típusú nyelveket rekurzívan felsorolható nyelveknek is nevezzük, a nyelvosztályt RE-vel jelöljük. Az 1-típusú nyelvek a környezetfüggő nyelvek, a nyelvosztály jele CS. A 2-típusú nyelvek a környezetfüggetlen nyelvek, nyelvosztályuk jelölése:CF. Végül, a 3-típusú nyelvek a reguláris nyelvek, melyek nyelvosztályát REG-gel jelöljük. A reguláris nyelvek osztálya megegyezik a véges automatával felismerhető nyelvek osztályával. A Chomsky-féle hierarchia alapján a fenti nyelvosztályokra a következő tartalmazási relációk állnak fenn:

REG ⊂ CF ⊂ CS ⊂ RE.

Itt és a továbbiakban is, ⊂ mindig szigorú tartalmazást jelöl. (Ezen állítások bizonyítását lásd: [Sal73]) A következőkben egy példát mutatunk egy környezetfüggő nyelvtanra és az általa generált nyelvre.

Példa 2.1

Legyen G = (N, T, P, S), ahol

• N = {S, A, B, C}

• T = {a, b, c}

• P = {S → aSAC, S → abC, CA → BA, BA → BC, BC → AC, bA → bb, C → c}.

Ez a G nyelvtan környezetfüggő és L(G) = {a^{n}b^{n}c^{n}|n ≥ 1}. Ez a példa azért érdekes, mert bár az L(G) nyelv nem környezetfüggetlen, de eco-grammatikával egyszerűen generálható (lásd 3.3 példa).

2.3 Lindenmayer rendszerek

Egy 0L rendszer (vagy 0-típusú Lindenmayer rendszer) egy Σ = (V, w, P) hármas, ahol

• V véges ábécé

• w a kezdőszó, w ∈ V^{+} • P környezetfüggetlen szabályok halmaza, és P teljes, azaz bármely

a ∈ V esetén létezik a → x ∈ P szabály, x ∈ V^{∗}.

Azt mondjuk, hogy y ∈ V^{∗} közvetlenül levezethető x ∈ V^{∗}-ból Σ-ban (jelölése: x⇒_{Σ}y), ha x = a_{1} … a_{n}, y = α_{1}, …, α_{n} és a_{1} → α_{i} ∈ P minden 1 ≤ i ≤ n esetén. Azaz, ellentétben a Chomsky-féle nyelvtanokkal, ahol a levezetés szekvenciálisan történt, a L-rendszerekben párhuzamosan folyik, egyszerre helyettesítjük az összes betűt az újraírandó szóban. A ⇒_{Σ} tranzitív (és reflexív) lezártját ⇒^{+} (ill. ⇒^{∗}) jelöli. A Σ által generált nyelv:

L(Σ) = { v ∈ V^{∗} | w⇒^{∗}v }

A továbbiakban az 0L rendszerek által generált nyelvek osztályát is 0L jelöli. Egy Lindenmayer rendszer

• determinisztikus, ha bármely a ∈ V -re pontosan egy a → α ∈ P szabály van. Az ilyen rendszerek a D0L rendszerek (ill. az általuk generált nyelvek a D0L nyelvek),

• λ-mentes, vagy P OL rendszer, ha nincsen a → λ szabály P -ben,

• kiterjesztett, vagy EOL rendszer, ha megkülönböztetünk egy terminális ábécét, Δ-t, melyre Δ ⊆ V. Ekkor Σ = (V, w, P, Δ) és

L(Σ) = { v ∈ Δ^{∗} | w⇒_{Σ}v }.

• táblás, vagy T OL rendszer, ha Σ = (V, w, P), ahol P = {P_{1}, …, P_{n}}, és Σ_{i} = (V, w, P_{i}) 0L rendszer minden i, 1 ≤ i ≤ n esetén. Egy táblás L-rendszerben y közvetlenül levezethető x- ből (x, y ∈ V^{∗}), ha x = a_{1}a_{2} … a_{n}, y = α_{1}, …, α_{m} és létezik i ∈ {1, 2, …, m} úgy, hogy a_{j} → α_{j} ∈ P_{i} minden 1 ≤ j ≤ m esetén. A Σ T OL rendszer által generált nyelv:

L(Σ) = { v ∈ V^{∗} | w⇒_{Σ_{i_{1}}}v_{1}⇒_{Σ_{i_{2}}} … ⇒_{Σ_{i_{k}}} v }

Ezen nyelvosztályokra (illetve a tulajdonságok kombinálásával kapottakra) fennáll a következő összefüggés:

0L ⊂ T 0L ⊂ ET 0L.

A Chomsky-féle nyelvosztályok és a Lindenmayer rendszerek által generált nyelvosztályokra az alábbi hierarchia teljesül:

• CF ⊂ E0L ⊂ ET 0L ⊂ CS

• CF összehasonlíthatatlan mind 0L-lel, mind T 0L-lel, (azaz, CF \(T)0L

és (T)0L \ CF sem üres). A fentiek bizonyításáért, illetve további információkért lásd még: [RS80]-t. A következőkben egy példát mutatunk 0L rendszerre. Példa 2.2 Legyen Σ = (V, w, P), ahol

• V = {a}

• w = a

• P = { a → a^{2} } Ekkor L(Σ) = { a^{2^{i}} | i ≤ 0 }

Az eco-grammatika rendszer definíciója, példák

Ebben a fejezetben megismerkedünk az eco-grammatika rendszer formális definíciójával és a definíció azon speciális eseteivel, amelyeket a dolgozatban vizsgálni fogunk.

3.1 ELP ( 0L, CF ) rendszerek és nyelvek

3.1.1 Az általános definíció

Definíció 1 Egy eco-grammatika rendszer n ágenssel egy olyan

Σ = (E, A_{1}, A_{2}, …, A_{n}, σ_{0})

(n + 1)-es, melyre teljesülnek a következők’:

• E = (V_{E}, P_{E}), ahol

–V_{E} véges, nem üres ábécé, –P_{E} 0L szabályok véges halmaza V_{E} felett (azaz P_{E} CF alakú szabályokat tartalmaz és teljes),

• A_{i} = (V_{i}, P_{i}, R_{i}, φ_{i}, ψ_{i}), 1 ≤ i ≤ n, ahol

–V_{i} véges, nem üres ábécé, –P_{i} CF szabályok teljes halmaza V_{i} felett, –R_{i} újraíró szabályok véges halmaza, mely szabályok x → y x ∈ V_{E}^{∗}, y ∈ V_{E}^{∗} alakúak, –φ_{i} : V_{E}^{∗} → 2^{P_{i}}, –ψ_{i} : V_{i}^{+} → 2^{R_{i}}, (φ_{i}, ψ_{i} kiszámítható leképezések),

• σ_{0} = (w_{E}^{0}, w_{1}^{0}, …, w_{n}^{0}), a kezdőállapot.

A fenti definíció értelmezése a következő:

• E jelenti a környezetet, V_{E} a környezet ábécéje, P_{E} pedig a környezet újraíró (fejlődési) szabályainak a halmaza,

• A_{i} az i-edik ágenst képviseli (1 ≤ i ≤ n), V_{i} az i-edik ágens ábécéje, P_{i} az ágens fejlődési szabályainak a halmaza, R_{i} az i-edik ágens által a környezeten végrehajtható akciók (újraírások) halmaza. Az A_{i} ágensnek így kétféle szabálya van, a P_{i}-beliek segítségével ő maga fejlődik, az R_{i}-beliekkel a környezeten hat (újraír betűket). A φ_{i} függvény – a környezet állapotától függően – kijelöli P_{i} egy részhalmazát: az adott lépésben aktív fejlődési szabályokat. A ψ_{i} függvény– az ágens állapotától függően – kijelöli R_{i} egy részhalmazát, az adott pillanatban aktív akciószabályokat.

• σ_{0} írja le a rendszer állapotát a kezdőpillanatban.

Hasonlóan a L-rendszerekhez, egy eco-grammatika rendszer (a továbbiakban EG rendszer)

• λ-mentes, ha sem P_{E}, sem P_{i}, sem R_{i} nem tartalmaz a → λ alakú szabályt.

• determinisztikus, ha P_{E} is, P_{i} is, és R_{i} is determinisztikus szabályhalmazok.

Egy EG rendszer állapota egy (n + 1)-es:

σ = (w_{E}, w_{1}, …, w_{n})

ahol w_{E} ∈ V_{E}^{∗}, w_{i} ∈ V_{i}^{∗} 1 ≤ i ≤ n esetén. Azaz, a környezetet és az ágenseket minden pillanatban egy-egy szóval írjuk le:

• w_{E} a környezet állapota,

• w_{i} az i-edik ágens állapota, 1 ≤ i ≤ n.

Az EG rendszer működése során állapotát változtatja. A továbbiakban több lépésben definiáljuk az állapotváltozás dinamikáját.

• Egy A_{i} ágens aktív egy adott (w_{E}, w_{1}, …, w_{n}) állapotban, ha ψ_{i}(w_{i}) ≠ ∅, azaz, ha van végrehajtható akciószabálya.

• Egy aktív ágens akciója a (w_{E}, w_{1}, …, w_{n}) állapotban azt jelenti, hogy A_{i} alkalmazza valamely r ∈ ψ_{i}(w_{i}) akciószabályát a környezetre, azaz a környezetet leíró w_{E} szóban újraír egy betűt r szerint.

• Az A_{i_{1}}, …, A_{i_{s}} ( {i_{1}, …, i_{s}} ⊆ {1, …, n}, i_{k} ≠ i_{l} ) (aktív) ágensek együttes akciója a (w_{E}, w_{1}, …, w_{n}) állapotban a környezetet leíró w_{E} szó részleges, párhuzamos újraírását jelenti. Azaz, w_{E}⇒w_{E}′ ahol:

w_{E} = x_{1}u_{1}x_{2}u_{2} … u_{s}x_{s+1} w_{E}′ = x_{1}v_{1}x_{2}v_{2} … v_{s}x_{s+1}.

ha u_{j} → v_{j} ∈ ψ_{i_{j}}(w_{i_{j}}), 1 ≤ j ≤ s és x_{i} ∈ V_{E}^{∗}, 1 ≤ i ≤ s + 1 esetén.

• Azt mondjuk, hogy w_{i}⇒w_{i}′ az A_{i} ágens fejlődése a (w_{E}, w_{1}, …, w_{n}) állapotban, ha w_{i}′ a w_{i}-ből φ_{i}(w_{E})-beli szabályok párhuzamos alkalmazásával közvetlenül levezethető.

• Azt mondjuk, hogy w_{E}′⇒w_{E}′′ a környezet fejlődése , ha w_{E}′′ a w_{E}′-ből P_{E}-beli szabályok párhuzamos alkalmazásával közvetlenül levezethető.

Megjegyzés 1

Jegyezzük meg, hogy a φ és ψ leképezések között van egy lényeges különbség: φ minden w ∈ V_{E}^{∗}-ra értelmezett, azaz az ágens a környezet bármely állapotához alkalmazkodni tud (az üreshez is), de ψ csak a w ∈ V_{i}^{∗} \ λ-ra van értelmezve, azaz λ állapotú ágens soha nem lehet aktív. Ezek után az állapotváltozás pontos definíciója:

Definíció 2 Legyen σ = ( w_{E}, w_{1}, …, w_{n} ) és σ′ = ( w_{E}′, w_{1}′, …, w_{n}′ ) a Σ = (E, A_{1}, A_{2}, …, A_{n}, σ_{0}) EG rendszer két állapota. Azt mondjuk, hogy σ′ közvetlenül levezethető σ-ból, ha teljesülnek a következők:

• w_{E} = z_{1}x_{1}z_{2}x_{2} … z_{m}x_{m}z_{m+1} és w_{E}′ = z_{1}′y_{1}z_{2}′y_{2} … z_{m}′y_{m}z_{m+1}′ ahol

–z_{1}x_{1}z_{2}x_{2} … z_{m}x_{m}z_{m+1}⇒z_{1}y_{1}z_{2}y_{2} … z_{m}y_{m}z_{m+1} az A_{i_{1}}, A_{i_{2}}, …, A_{i_{m}} ( {i_{1}, i_{2}, …, i_{m}} ⊆ {1, 2, …, m}, i_{k} ≠ i_{l} ) ágensek együttes akciója következtében, ahol A_{i_{1}}, A_{i_{2}}, …, A_{i_{m}} éppen a σ-ban aktív ágensek. –z_{1}z_{2} … z_{m+1}⇒z_{1}′z_{2}′ … z_{m+1}′ pedig a környezet fejlődése.

• w_{j}⇒w_{j}′ az A_{i_{j}} ágens fejlődése

A ⇒ tranzitív (és reflexív) lezártját most is ⇒_{+} (ill. ⇒_{∗}) jelöli.

Megjegyzés 2

A σ állapotból semmi se vezethető le, ha nem tud minden aktív ágens dolgozni, például, ha w_{E} hossza rövidebb, mint ahány aktív ágens van.

A fenti definíció értelmezése: a σ = (w_{E}, w_{1}, …, w_{n}) állapotban

• először az aktív ágensek, azaz, amelyekre φ_{i}(w_{i}) ≠ ∅ teljesül, végrehajtják együttesen az akciójukat (φ_{i}(w_{i}) szerint), majd azokon a betűkön, melyeket az ágensek nem érintettek, a környezet újraírja önmagát (P_{E} szerint, párhuzamosan). (Úgy is mondhatjuk, hogy az akciószabályoknak elsőbbségük van a környezet fejlődési szabályaival szemben.)

• ezután minden ágens fejlődik φ_{i}(w_{E}) szerint.

Tehát a környezet és az ágensek kölcsönösen hatnak egymásra az akciószabályok, illetve a φ_{i} leképezések segítségével. Mivel a környezetet és az ágenseket is szavak írják le, az EG rendszereket nyelvgeneráló rendszereknek is tekinthetjük az alábbi módon.

Definíció 3 Legyen Σ = (E, A_{1}, A_{2}, …, A_{n}, σ_{0}) EG rendszer. Ekkor

• Σ állapotsorozatainak nevezzük az alábbi halmaz elemeit:

Seq(Σ, σ_{0}) = { {σ_{i}}_{i=0}^{∞} | σ_{0}⇒_{Σ}σ_{1}⇒_{Σ} … }

• a környezet állapotsorozatainak nevezzük az alábbi halmaz elemeit: Seq_{E}(Σ, σ_{0}) = {{w_{E}_{i}}_{i=0}^{∞} |{σ_{i}}_{i=0}^{∞} ∈ Seq(Σ, σ_{0}), σ_{i} = (w_{E}, w_{1}, …, w_{n})}

• a környezet által generált nyelvnek a következő nyelvet tekintjük: L_{E}(Σ, σ_{0}) = { w_{e} ∈ V_{E}^{∗} | ∃{σ_{i}}_{i=0}^{∞} ∈ Seq(Σ, σ_{0}) : σ_{i} = (w_{E}, w_{1}, …, w_{n}) }

Seq(Σ, σ_{0}) írja le a rendszer viselkedését, Seq_{E}(Σ, σ_{0}) pedig a környezet időbeli változását. A fenti definícióhoz hasonlóan értelmezhetnénk az ágensek állapotsorozatait és az ágensek által generált nyelveket is, de a továbbiakban az általános definíció egy olyan egyszerűsített változatát fogjuk vizsgálni, melyben L_{E}(Σ, σ_{0}) írja le a rendszer viselkedét. Mielőtt azonban rátérnénk ezen változat tárgyalására, tekintsünk egy példát EG rendszerre, illetve az általa generált nyelvre:

Példa 3.1

Legyen Σ = ( E, A_{1}, A_{2}, σ_{0} ) az az ELP ( 0L, CF ) rendszer, melyre

• E = ( V_{E}, P_{E} ), ahol V_{E} = { c_{1}, c_{2}, c_{3} }, P_{E} = { c_{1} → c_{1}, c_{2} → c_{1}c_{2}, c_{3} → c_{2}c_{2} }.

• A_{1} = { V_{1}, P_{1}, R_{1}, φ_{1}, ψ_{1} }, ahol V_{1} = { a_{1}, a_{2}, a_{3}, a_{4} }, P_{1} = { a_{1} → a_{2}, a_{2} → a_{3}, a_{3} → a_{1}, a_{4} → a_{4}, a_{1} → a_{4}, a_{2} → a_{4}, a_{3} → a_{4}, a_{4} → a_{4} }, φ_{1}(w) = { a_{1} → a_{2}, a_{2} → a_{3}, a_{3} → a_{1}, a_{4} → a_{4} }, ha w-ben több c_{1} van mint c_{2}, vagy ugyanannyi, φ_{1}(w) = { a_{1} → a_{4}, a_{2} → a_{4}, a_{3} → a_{4}, a_{4} → a_{4} }, ha w-ben kevesebb c_{1} van mint c_{2}, R_{1} = { c_{1} → λ, c_{2} → λ, c_{2} → c_{3}, c_{1} → c_{3}, c_{1} → c_{1}, c_{2} → c_{2} } ψ_{1}(w) = { c_{1} → λ, c_{2} → λ }, ha w = a_{1}, a_{2}, ψ_{1}(a_{3}) = { c_{2} → c_{3}, c_{1} → c_{3} }, ψ_{1}(a_{4}) = { c_{1} → c_{1}, c_{2} → c_{2} }. Azaz, az első ágens állapota nem változik tovább, ha a környezetet leíró szóban több c_{2} szerepel, mint ahány c_{1}; a c_{2} betűk leállítják az ágens fejlődését.

• A_{2} = { V_{2}, P_{2}, R_{2}, φ_{2}, ψ_{2} }, ahol V_{2} = { b_{1}, b_{2} }, P_{2} = { b_{1} → b_{2}, b_{2} → b_{1} }, φ_{2}(w) = P_{2}, minden w ∈ V_{E}^{∗} esetén, R_{2} = { c_{1} → λ, c_{2} → λ, c_{1} → c_{3} }, ψ_{2}(b_{1}) = { c_{1} → λ, c_{2} → λ }, ψ_{2}(b_{2}) = { c_{2} → λ, c_{1} → c_{3} },

• σ_{0} = { c_{1}c_{2}c_{1}c_{2}c_{1}c_{1}, a_{1}, b_{1} }

Figyeljük meg, hogy mind a környezet, mind az ágensek determinisztikusak, de mindkét ágens két akciószabály közül választhat minden lépésben. Nézzük meg egy lehetséges fejlődés első pár lépését! Hogy egyszerűbb legyen követni a levezetést, egyezzünk meg abban, hogy ha egy u → v szabályt több helyen is alkalmazhatnánk, akkor mindig a legbaloldalibb helyen fogjuk alkalmazni. Továbbá, ha az ágens mindkét akciószabálya alkalmazható lenne egy lépés során, akkor az elsőt fogjuk alkalmazni. (Tehát, ha például az első ágens az a_{1} vagy a_{2} állapotban van és c_{1} és c_{2} is előfordul a környezetet leíró szóban, akkor a c_{1} → λ szabályt alkalmazzuk.) Ezek után az első lépések a következők lehetnek (a szögletes zárójelben szereplő betűk az ágensek akciószabályainak eredményei, a kerek zárójelben állók a környezet fejlődési szabályaiból adódnak):

(c_{1}c_{2}c_{1}c_{2}c_{1}c_{1}; a_{1}, b_{1}) ⇒ ([λ](c_{1}c_{2})[λ](c_{1}c_{2})(c_{1})(c_{1}); a_{2}, b_{2})
⇒ ([λ][λ](c_{1})(c_{1}c_{2})(c_{1})(c_{1}); a_{3}, b_{1})

⇒ ([λ](c_{1})[c_{3}](c_{1})(c_{1}); a_{1}, b_{2})
⇒ ([λ](c_{2}c_{2})[c_{3}](c_{1}); a_{2}, b_{1})

Ekkor tartalmaz először több c_{2}-t, mint c_{1}-et a környezetet leíró szó, tehát:

⇒ ([λ](c_{1}c_{2})(c_{2}c_{2})[λ]; a_{4}, b_{2})

Az első ágens elérte a végső állapotát, már nem fejlődik tovább, és ebben az állapotban valódi változtatást már nem hajt végre a környezeten. Tehát:

⇒ ([c_{1}][λ](c_{1}c_{2})(c_{1}c_{2}); a_{4}, b_{1})
⇒ ([c_{1}][λ](c_{1}c_{2})(c_{1})(c_{1}c_{2}); a_{4}, b_{2})
⇒ ([c_{1}](c_{1})[λ](c_{1})(c_{1})(c_{1}c_{2}); a_{4}, b_{1})
⇒ ([c_{1}][λ](c_{1})(c_{1})(c_{1})(c_{1}c_{2}); a_{4}, b_{2})
⇒ ([c_{1}](c_{1})(c_{1})(c_{1})(c_{1})[λ]; a_{4}, b_{1})
⇒ ([c_{1}][λ](c_{1})(c_{1})(c_{1}); a_{4}, b_{2})
⇒ ([c_{1}][c_{3}](c_{1})(c_{1}); a_{4}, b_{1})
⇒ ([c_{1}](c_{2}c_{2})[λ](c_{1}); a_{4}, b_{2})
⇒ ([c_{1}][λ](c_{1}c_{2})(c_{1}); a_{4}, b_{1})
⇒ ([c_{1})[λ](c_{1}c_{2})(c_{1}); a_{4}, b_{2})
⇒ ([c_{1}](c_{1})[λ](c_{1}); a_{4}, b_{1})
⇒ ([c_{1}][λ](c_{1}); a_{4}, b_{2})
⇒ ([c_{1}][c_{3}]; a_{4}, b_{1})

Ekkor ez a levezetés leáll, mert a második ágens nem tud c_{3}-on akciószabályt végrehajtani. Természetesen ez csak egy lehetséges levezetés volt, a többi levezetés nem blokkolódik feltétlenül ilyen hamar. Ezzel a példával azt akartam megvilágítani, mennyire bonyolult lehet egy EG rendszer fejlődése, még egy ilyen viszonylag egyszerű, két ágenses esetben is.

3.1.2 Az egyszerű EG rendszer definíciója, példák

Annak, hogy az EG rendszerek egy igen speciális osztályával fogunk foglalkozni, több oka van:

1. Már ez a speciális osztály is elég érdekes, és generatív ereje elég nagy ahhoz, hogy külön figyelmet fordítsunk rá.

2. Az EG rendszer általános alakja túl bonyolult ahhoz, hogy a felmerülő kérdéseket általános esetben megválaszoljuk.

3. A mesterséges élet elméletének egyik fő szempontja éppen az, hogy egyszerű összetevőkből bonyolult viselkedésű rendszert hozzunk létre. Ezt a követelményt az EG rendszerek nyelvére lefordítva kapjuk, hogy “egyszerű” felépítésű rendszerrel szeretnénk bonyolult nyelvosztályokat leírni.

Definíció 4 A Σ = (E, A_{1}, A_{2}, …, A_{n}, σ_{0}) EG rendszert egyszerűnek nevezzük, ha 1 ≤ i ≤ n esetén az alábbiak teljesülnek:

• φ_{i} = P_{i} bármely w_{E} ∈ V_{E}^{∗} esetén (Az A_{i} ágens nem alkalmazkodik a környezethez),

• ψ_{i}(w_{i}) = R_{i} bármely w_{i} ∈ V_{i}^{+} esetén (Az A_{i} ágens összes akciószabálya végrehajtható minden pillanatban),

• R_{i} CF szabályokat tartalmaz (Azaz R_{i} minden szabálya x → y alakú, ahol x ∈ V_{E}, y ∈ V_{E}^{∗}),

• P_{i} nem tartalmaz λ-szabályt (Ez biztosítja, hogy az A_{i} ágens mindig aktív legyen).

Megjegyzés 3

Bármely 1 ≤ i ≤ n és bármely σ állapot esetén w_{i} ≠ λ, tehát ψ_{i}(w_{i}) = R_{i} áll fenn mindig. Így az ágensek fejlődésének semmi hatása nincs a környezet változására. Ezért:

• az ágensek leírásából csak R_{i} hordoz olyan információt, mely a környezet viselkedését befolyásolja, a többi (P_{i}, φ_{i}, ψ_{i}, w_{i}) elhagyható, ha csak a környezet viselkedését akarjuk megfigyelni,

• a rendszer változását a környezet írja le valójában (az egyszerű EG rendszer esetén), hiszen az ágensek független módon fejlődnek.

A fentiek értelmében ezentúl egy egyszerű EG rendszert nem Σ = (E, A_{1}, A_{2}, …, A_{n}, σ_{0})-lal, hanem Σ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w_{0})-lal fogunk jelölni, ahol

• V_{E} és P_{E} a környezet ábécéje, illetve szabályhalmaza (mint eddig),

• R_{i} az i-edik ágens akciószabályainak halmaza (ahogy eddig),

• w_{0} ∈ V_{E}^{∗} a környezet kezdőállapota.

Ezek után érthető, hogy L_{E}(Σ, σ_{0}) = L_{E}(Σ, w_{0})-t tekintjük az egyszerű EG rendszer által generált nyelvnek. A Σ által generált nyelv jelölése: L(Σ, w_{0}). Ismételten megjegyezzük, hogy minden ágens aktív minden pillanatban.

Példa 3.2 (amely azt mutatja, hogy az ágensek valóban befolyásolják a rendszer fejlődését)

Legyen Σ = (V_{E}, P_{E}, R_{1}, w_{0}), ahol

• V_{E} = {a}

• P_{E} = {a → a^{2}}

• R_{1} = {a → a^{3}}

• w_{0} = a.

Egy Σ-beli levezetés

a⇒_{Σ}a^{3}⇒_{Σ}a^{7}⇒_{Σ} …

alakú. Azaz L(Σ, a) = { a^{2^{i}−1} | i ≥ 1 }. Ha a környezetet önmagában, mint 0L rendszert nézzük, az ágensek hatása nélkül, akkor az így generált nyelv: L(E) = { a^{2^{i}} | i ≥ 1 }. (Ahogy már a 2.2 példában láttuk.) L(Σ, a) azonban nem 0L nyelv. (Lásd : [CVKKP97]-t.) Ez azt mutatja, hogy már egyetlen, igen egyszerű ágens is annyira megváltoztatja a 0L környezet viselkedését, hogy a Σ EG-rendszer az 0L nyelvosztályon kívüli nyelvet generál.

Megjegyzés 4 Nyilvánvaló, hogy minden 0L nyelv generálható egyszerű EG rendszerrel. (Ugyanis minden 0L rendszer tekinthető olyan EG rendszernek, amelyben nincs ágens.) Lássunk még egy példát egyszerű EG rendszerre: Példa 3.3 Legyen Σ = (V_{E}, P_{E}, R_{1}, R_{2}, R_{3}, w_{0}) egyszerű EG rendszer, ahol

• V_{E} = {a, b, c}

• P_{E} = {a → a, b → b, c → c}

• R_{1} = {a → a^{2}}

• R_{2} = {b → b^{2}}

• R_{3} = {c → c^{2}}

• w = abc. Ekkor–jól láthatóan– L(Σ, abc) = { a^{n}b^{n}c^{n} | n ≥ 1}.

3.1.3 Az ELP (0L, CF) osztályok definíciója, példák

Idáig az EG rendszer működésére azt a megszorítást tettük, hogy az összes aktív ágensnek részt kell vennie a levezetésben, különben a deriváció blokkolódik. Másik lehetőségként kapjuk a k tagú team-mel dolgozó EG rendszereket. Definíció 5 Legyen Σ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w_{0}) egy egyszerű EG rendszer, ahol u, v ∈ V_{E}^{∗}. Azt mondjuk, hogy v közvetlenül levezethető az u szóból Σ-ban, k tagú teammel, 1 ≤ k ≤ n esetén (jelölése: u ⇒_{Σ}^{=k} v), ha teljesülnek az alábbiak:

• u = x_{0}A_{1}x_{1} … x_{k−1}A_{k}x_{k} és v = y_{0}α_{1}y_{1} … y_{k−1}α_{k}y_{k}, ahol A_{i} ∈ V_{E}, x_{j}, y_{j}, α_{i} ∈ V_{E}^{∗}, bármely 1 ≤ i ≤ k és 0 ≤ j ≤ k esetén,

• x_{j}⇒_{P_{E}}y_{j} minden 0 ≤ j ≤ k esetén,

• A_{i} → α_{i} ∈ R_{l_{i}} valamely l_{i} ∈ {1, 2, …, n} esetén, l_{j} ≠ l_{m}, ha 1 ≤ j, m ≤ k és m ≠ j.

Azaz minden lépésben k darab véletlenül kiválasztott ágens dolgozik.

Definíció 6 Legyen Σ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w_{0}) egy egyszerű EG rendszer, ahol u, v ∈ V_{E}^{∗}. Azt mondjuk, hogy v közvetlenül levezethető az u szóból Σ-ban, egy legfeljebb k tagú team-mel, 1 ≤ k ≤ n esetén (jelölése: u ⇒_{Σ}^{≤k} v), ha ⇒_{Σ}^{=j} teljesül valamely 0 ≤ j ≤ k-ra.

Ebben az esetben a dolgozó ágensek számára csak felső korlát van. Az ⇒_{Σ}^{a} v tranzitív (és reflexív) lezártját ⇒^{a}_{Σ}^{+} (illetve ⇒^{a}_{Σ}^{∗}) jelöli, ha a ∈ {= 0, = 1, …, = n, ≤ 1, ≤ 2, …, ≤ n}. Az Σ által így generált nyelv definíciója:

Definíció 7 Legyen Σ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w_{0}) egy egyszerű EG rendszer, és legyen a ∈ {= 0, = 1, …, = n, ≤ 1, ≤ 2, …, ≤ n}. Ekkor a Σ által a team-mel generált nyelvnek az L(Σ, a) = {v ∈ V_{E}^{∗}| w⇒^{a}_{Σ}^{+}v} nyelvet nevezzük.

Az eddigiekben megismert EG rendszereket az alább felsorolt módon jelöljük:

• ELP_{n,=k}( 0L, CF ) jelöli az n ágenssel rendelkező, k tagú team-mel dolgozó egyszerű EG rendszerek osztályát.

• ELP_{n,≤k}( 0L, CF ) elöli az n ágenssel rendelkező, ≤ k tagú team-mel dolgozó egyszerű EG rendszerek osztályát

• ELP_{=}(0L, CF) = ⋃_{n=1}^{∞}⋃_{k=0}^{n}ELP_{n,=k}( 0L, CF )

• ELP_{≤}(0L, CF) = ⋃_{n=1}^{∞}⋃_{k=0}^{n}ELP_{n,≤k}( 0L, CF )

• ELP (0L, CF)-et írunk, ha nem érdekes, hogy milyen módban dolgozik a rendszer, sem az, hogy hány ágens van, csak az, hogy az ágensek CF alakú szabályokat használnak. Erre akkor lesz szükség, ha más (nem CF szabályokat használó) rendszerek is előfordulhatnak.

A dolgozatban az alábbi konvenciót fogjuk követni: egyszerű EG rendszer alatt mindig ELP ( 0L, CF ) rendszert értünk.

A fenti rendszerek által generált nyelvek osztályaira a következő jelöléseket vezetjük be (értelemszerűen): LELP_{n,=k}(0L, CF), LELP_{n,≤k}(0L, CF), LELP_{=}(0L, CF), LELP_{≤}(0L, CF), illetve LELP ( 0L, CF ).

Példa 3.4

Legyen Σ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w) az alábbi egyszerű EG rendszer :

• V_{E} = {a_{1}, b_{1}, a_{2}, b_{2}, c_{1}, …, c_{n}},

• P_{E} = {b_{1} → b_{2}^{2}, a_{1} → a_{2}^{2}, b_{2} → b_{1}^{2}, a_{2} → a_{1}^{2}} ⋃_{1≤j≤n}{c_{j} → a_{1}},

• R_{i} = {a_{1} → c_{1}, c_{i} → a_{1}}, 1 ≤ i ≤ n,

• w = b_{1}a_{1}^{1+k}.

Az L_{CF} (n, = k) = L(Σ, = k) illetve a L_{CF} (n, ≤ k) = L(Σ, ≤ k) generált nyelvekről a következőt állíthatjuk (bármely 0 ≤ k ≤ n esetén): Az L_{CF} (n, = k) esetében: Páros számú, (2s) lépés alatt a b_{1}a_{1}^{k+1}⇒^{2s}b_{1}^{4^{s}}a_{1}^{k+4^{s}} deriváció történik. Továbbá:

4b_{1}^{j}a_{1}^{j+k}⇒b_{2}^{2i}[\underbrace{a_{2}^{2}, …, a_{2}^{2}}_{j−darab}, c_{i_{1}}, …, c_{i_{k}}]^{P}

ahol [w_{1}, w_{2}, …, w_{n}]^{P} egy, a w_{1}, w_{2}, …, w_{n} elemek valamely permutációjának megfelelő szó. Ezért:

L_{CF} (n, = k) = { b_{1}^{4^{j}}a_{1}^{k+4^{j}} | j ≥ 0} ⋃

⋃ { b_{2}^{24^{j}}a_{2}^{2l_{1}}c_{i_{1}}a_{2}^{2l_{2}}c_{i_{2}} … a_{2}^{2l_{k}}c_{i_{k}}a_{2}^{2l_{k+1}} | j ≥ 0, 0 ≤ l_{i}, ∑_{1≤i} l_{i} = 4^{j} }

L_{CF} (n, = k) a továbbiak szempontjából lényeges tulajdonságai:

1. szavai vagy {a_{1}, b_{1}} (első ábécé) vagy {a_{2}, b_{2}, c_{1}, …, c_{n}} ( második ábécé) felettiek,

2. a második ábécé feletti szavakban pontosan k darab különböző c fordul elő, és ezek egymáshoz és a szóvégekhez képest bárhogy elhelyezkedhetnek a szókezdő b -betűsorozat után.

Az L_{CF} (n, ≤ k) esetén hasonló megállapításokat tehetünk: Ha egy 2t hosszú levezetés során a 2r-edik lépésben ( ahol 1 ≤ r ≤ t) rendre s_{1}, s_{2}, …, s_{t} darab ágens dolgozott ( s_{i} ≤ k teljesül minden 1 ≤ i ≤ t-re ), akkor b_{1}a_{1}^{k+1}⇒^{2t}b_{1}^{4^{t}}a_{1}^{f(s_{1},...,s_{t})}, ahol f(s_{1}, …, s_{t}) = 4^{t}(k + 1) − 3 ∑_{r=1}^{t} 4^{t−r}s_{r}.

A 2t + 1-edik lépés során pedig: b_{1}^{4^{t}}a_{1}^{f(s_{1},...,s_{t})}⇒b_{2}^{24^{t}}a_{2}^{2l_{1}}c_{i_{1}}a_{2}^{2l_{2}}c_{i_{2}} … a_{2}^{2l_{s}}c_{i_{s}}a_{2}^{2l_{s+1}}, ahol 0 ≤ s ≤ k, s + l_{1} + … + l_{s+1} = f(s_{1}, …, s_{t}). Azaz,

L_{CF} (n, ≤ k) = {b_{1}^{4^{t}}a_{1}^{f(s_{1},...,s_{t})} | 0 ≤ s_{i} ≤ k, t ≥ 1} ∪

∪{b_{2}^{24^{t}}a_{2}^{2l_{1}}c_{i_{1}}a_{2}^{2l_{2}}c_{i_{2}} … a_{2}^{2l_{s+1}}|0 ≤ s ≤ k, s+l_{1}+…+l_{s+1} = f(s_{1}, …, s_{t}), t ≥ 0}

ahol f(s_{1}, …, s_{t}) = 4^{t}(k + 1) − 3 ∑_{r=1}^{t} 4^{t−r}s_{r} . L_{CF} (n, ≤ k) legfontosabb tulajdonságai:

1. Mint a megelőző esetben, itt is két külön ábécé van, azaz a szavak vagy {a_{1}, b_{1}}, vagy {a_{2}, b_{2}, c_{1}, …, c_{n}} felettiek,

2. a második ábécé feletti szavakban legfeljebb k darab c betű szerepel, ezek mind különbözőek, és bárhol elhelyezkedhetnek a szókezdő b-betűsorozat után.

Példa 3.5

Az előző Σ rendszerhez nagyon hasonló Σ′ rendszert definiálunk: Σ′ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w) az alábbi egyszerű EG rendszer :

• V_{E} = {a_{1}, , a_{2}, , c_{1}, …, c_{n}}

• P_{E} = {a_{1} → a_{2}^{2}, a_{2} → a_{1}^{2}} ⋃_{1≤j≤n}{c_{j} → a_{1}}

• R_{i} = {a_{1} → c_{i}, c_{i} → a_{1}}, 1 ≤ i ≤ n esetén

• w = a_{1}^{1+k}.

A generált nyelvek , L_{n,=k} és L_{n,≤k} ( az előző példa alapján) a következők:

L_{n,=k} = {a_{1}^{k+4^{j}} | j ≥ 0} ∪

∪ {a_{2}^{2l_{1}}c_{i_{1}}a_{2}^{2l_{2}}c_{i_{2}} … a_{2}^{2l_{k}}c_{i_{k}}a_{2}^{2l_{k+1}} | j ≥ 0, l_{i} ≥ 0, ∑_{1≤i} l_{i} = 4^{j}}

illetve

L_{n,≤k} = {a_{1}^{f(s_{1},...,s_{t})} | 0 ≤ s_{i} ≤ k, t ≥ 0} ∪

∪ {a_{2}^{2l_{1}}c_{i_{1}}a_{2}^{2l_{2}}c_{i_{2}} … a_{2}^{2l_{s+1}} | 0 ≤ s ≤ k, s + ∑_{i=1}^{s+1} l_{i} = f(s_{1}, …, s_{t}), t ≥ 0 }

ahol f(s_{1}, …, s_{t}) = 4^{t}(k + 1) − 3 ∑_{r=1}^{t} 4^{t−r}s_{r}. Ezen nyelvek is rendelkeznek az L_{CF} (n, = k) és L_{CF} (n, ≤ k) nyelvek imént felsorolt lényegesnek mondott tulajdonságaival:

1. Ebben az eseteben is két külön ábécé van, azaz, a szavak vagy {a_{1}, b_{1}} vagy {a_{2}, b_{2}, c_{1}, …, c_{n}} felettiek,

2. a második ábécé feletti szavakban legfeljebb k darab c betű szerepel, ezek mind különbözőek, és bárhol elhelyezkedhetnek a szókezdő b-betűsorozat után.

3.2 ELP ( 0L, INS ) és ELP ( 0L, REP ) rendszerek és nyelvek

3.2.1 Az ELP ( 0L, INS ) rendszerek definíója Példák ELP ( 0L, INS ) nyelvekre

Az eddigiek során egy egyszerű EG rendszerben az ágensek u → v u ∈ V, v ∈ V_{E}^{∗} alakú CF szabályokat használtak akcióik végrehajtására. Az EG rendszerek egy újabb változatát kapjuk, ha R_{i}-ben másfajta szabályokat engedünk meg. Egy ilyen új művelet a beszúrás ( angolul insertion). Ezt informálisan úgy fogalmazhatjuk, hogy az ágens adott környezetben (például bármely két a betű közé , amelyek akármilyen távol lehetnek egymástól) beszúrhat egy szót. A formális definíció a következő:

Definíció 8 Beszúró rendszernek (rövidebben INS rendszernek) nevezünk egy I = (V, P, w) hármast, ahol

• V véges, nem üres ábécé

• P ⊆ { (u, z, v) | u, v, z ∈ V^{+} }, beszúró szabályok véges halmaza

• w ∈ V^{+}, kezdőszó.

Egy ilyen INS rendszerben a levezetést a következőképpen definiáljuk:

Definíció 9 Legyenek x, y ∈ V^{+} szavak. Azt mondjuk, hogy az y szó közvetlenül levezethető I-ben az x szóból (jelölése: x⇒_{I}y), ha x = x_{1}ux_{2}x_{3}vx_{4}, y = x_{1}ux_{2}zx_{3}x_{4}, ahol x_{1}, x_{2}, x_{3}, x_{4} ∈ V^{∗} és (u, z, v) ∈ P.

Azaz a rendszer az u szó után de a v szó elé bárhová beillesztheti a z szót . Ezek után a beszúró EG rendszer definíciója:

Definíció 10 A Σ = ( V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w ) rendszert n ágenssel rendelkező egyszerű beszúró EG rendszernek vagy rövidebben ELP ( 0L, INS ) rendszernek nevezzük, ha teljesülnek az alábbiak:

• V_{E} véges, nem üres ábécé,

• P_{E} 0L szabályok véges, teljes halmaza V_{E} felett,

• P_{1}, P_{2}, …, P_{n} beszúró szabályok véges halmazai ( az ágensek akciószabályai),

• w ∈ V_{E}^{+}, kezdőszó.

Tehát ezen rendszerek az ELP (0L, CF) rendszerektől csak abban különböznek, hogy az ágensek nem CF, hanem INS szabályokat használnak.

Definíció 11 Legyen Σ = ( V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w ) egy ELP ( 0L, INS ) rendszer, és legyen x, y ∈ V_{E}^{∗}. Azt mondjuk, hogy az y szó közvetlenül levezethető az x szóból k tagú team-mel Σ-ban (jelölése: x ⇒_{Σ}^{=k}), ha x = x_{1} … x_{k+1}, x_{j} ∈ V_{E}^{∗} minden j, 1 ≤ j ≤ k + 1 esetén, y = y_{1}z_{1} … y_{k}z_{k}y_{k+1}, ahol y_{j}, z_{j} ∈ V_{E}^{∗} minden j, 1 ≤ j ≤ k + 1 esetén, és (u_{i}, z_{i}, v_{i}) ∈ P_{j_{i}} ahol j_{i} ≠ j_{s} ha i ≠ s, 1 ≤ i, s ≤ k, illetve x_{j}⇒_{P_{E}}y_{j} minden j, 1 ≤ j ≤ k + 1 esetén.

Példa 3.6

Legyen Σ = (V_{E}, P_{E}, R_{1}, R_{2}, w) olyan ELP ( 0L, INS) rendszer két ágenssel, melyre:

• V_{E} = { a, b, c, d }

• P_{E} = { a → a, b → b, c → c, d → d }

• R_{1} = { (a, c, b) }

• R_{2} = { (a, d, a) }

• w = aabb.

Ekkor w⇒x esetén x lehetséges értékei többek között: acdabb, adacbb, adabcb, adcabb. A ⇒^{=k} tranzitív (és reflexív) lezárását most is ⟹^{=k}_{Σ}^{+} (illetve ⟹^{=k}_{Σ}^{∗}) jelöli.

Definíció 12 Legyen Σ = ( V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w ) egy ELP ( 0L, INS ) rendszer. x, y ∈ V_{E}^{∗} esetén azt mondjuk, hogy az y szó közvetlenül levezethető az x szóból egy legfeljebb k tagú team-mel Σ-ban (jelölése: x ⇒_{Σ}^{≤k} y), ha x ⇒_{Σ}^{=j} y valamely j ≤ k esetén.

Definíció 13 Legyen Σ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w) egy ELP ( 0L, INS ) rendszer. Az általa a módban ( a ∈ { = 0, = 1, …, = n, ≤ 1, …, ≤ n }) generált nyelvnek az

L(Σ, a) = { v ∈ V_{E}^{∗} | w ⟹_{Σ}^{∗}^{a} v }

nyelvet nevezzük.

Az ELP ( 0L, CF ) esettel teljesen megegyező módon az alábbi jelöléseket vezetjük be:

• ELP_{n,=k}( 0L, INS ) jelöli az n ágenssel rendelkező, k tagú team-mel dolgozó INS rendszerek osztályát.

• ELP_{n,≤k}( 0L, INS )jelöli az n ágenssel rendelkező, ≤ k tagú team-mel dolgozó INS rendszerek osztályát.

• ELP_{=}( 0L, INS ) = ⋃_{n=1}^{∞}⋃_{k=0}^{n}ELP_{n,=k}( 0L, INS )

• ELP_{≤}( 0L, INS ) = ⋃_{n=1}^{∞}⋃_{k=0}^{n}ELP_{n,≤k}( 0L, INS )

• ELP ( 0L, INS)-et írunk, ha nem érdekes, hogy milyen módban dolgozik a rendszer, sem az, hogy hány ágens van, csak az, hogy az ágensek beszúró szabályokat használnak.

A rendszerekhez kapcsolódó nyelvosztályok jelölése, rendre: LELP_{n,=k}( 0L, INS ), LELP_{n,≤k}( 0L, INS ), LELP_{=}(0L, INS), LELP_{≤}( 0L, INS ), illetve LELP ( 0L, INS ). Példa 3.7 Legyen Σ = ( V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w ) olyan ELP ( 0L, INS ) rendszer, ahol:

• V_{E} = { a_{1}, b_{1}, a_{2}, b_{2}, c_{1}, c_{2}, …, c_{n} }

• P_{E} = { b_{1} → b_{2}, a_{1} → a_{2}, b_{2} → b_{1}, a_{2} → a_{1} } ∪_{1≤j≤n}{ c_{j} → a_{1} }

• R_{i} = { (b_{1}, c_{1}, a_{1}), (b_{2}, a_{1}, a_{2}) } , 1 ≤ i ≤ n esetén

• w = a_{1}^{3}b_{1}a_{1}^{k}. A generált L(Σ, = k) = L_{INS}(n, = k) illetve L(Σ, ≤ k) = L_{INS}(n, ≤ k) nyelveket vizsgáljuk. Egy általános levezetés az = k módban a következőképpen kezdődik:

a_{1}^{3}b_{1}a_{1}^{k}⇒_{Σ} a_{2}^{3}b_{2}[c_{i_{1}}, …, c_{i_{k}}, \underbrace{a_{2}, …, a_{2}}_{(k−1)−szer}]^{P} a_{2}⇒_{Σ} a_{1}^{3}b_{2}a_{1}^{3k}⇒_{Σ} …

Ez alapján jól látható, hogy:

L_{INS}(n, = k) = {a_{1}^{3}b_{1}a_{1}^{k+2ik}| i ≥ 0} ∪

∪\{ a_{2}^{3}b_{2} [c_{i_{1}}, …, c_{i_{k}}, \underbrace{a_{2}, …, a_{2}}_{(k+2ik−1)−szer}]^{P} a_{2} | i ≥ 0\}

L_{INS}(n, = k) lényeges tulajdonságai:

• Két fajta szót tartalmaz, az {a_{1}, b_{1}} felettieket, és az {a_{2}, b_{2}, c_{1}, …, c_{n}} felettieket.

• c_{i_{1}}, c_{i_{2}}, …, c_{i_{k}} a b betű után bárhol előfordulhat, kivéve a szó végén, de a b betű előtt soha.

• c_{i}-k bármilyen messze lehetnek b-től.

• Pontosan k darab különböző c szerepel az { a_{2}, b_{2}, c_{1}, …, c_{n} } feletti

szavakban. L_{INS}(n, ≤ k)-t vizsgálva hasonló eredményre jutunk, mint a CF esetben :

L_{INS}(n, ≤ k) = { a_{1}^{3}b_{1}a_{1}^{f(s_{1},...,s_{t})} | 0 ≤ s_{i} ≤ k, t ≥ 0} ∪

∪ \{a_{2}^{3}b_{2} [c_{i_{1}}, …, c_{i_{k}}, \underbrace{a_{2}, …, a_{2}}_{(f(s_{1},...,s_{t})−1)−szer}]^{P} a_{2} | s ≥ 0, 1 ≤ i_{t} ≤ n, t ≥ 0 \}

Ahol f(s_{1}, …, s_{t}) = k + ∑_{i=1}^{t} s_{i} áll a fenti definícióban. A lényeges tulajdonságok pedig ugyanazok, mint L_{INS}(n, = k) esetén, azzal a különbséggel, hogy itt legfeljebb k darab c betű szerepelhet az {a_{2}, b_{2}, c_{1}, …, c_{n}} feletti szavakban. L_{n,=k} és L_{n,≤k} mintájára módosítjuk az előző példát: Példa 3.8 Legyen Σ′ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w) olyan ELP (0L, INS) rendszer ahol:

• V_{E} = { a_{1}, a_{2}, c_{1}, c_{2}, …, c_{n} }

• P_{E} = { a_{1} → a_{2}, a_{2} → a_{1} } ∪_{1≤j≤n}{c_{j} → a_{1}}

• R_{i} = { (a_{1}, c_{i}, a_{1}), (a_{2}, a_{1}, a_{2}) } 1 ≤ i ≤ n esetén

• w = a_{1}^{k+1}.

Ekkor:

I_{n,=k} = L(Σ, = k) = { a_{1}^{1+k+2ik} | i ≥ 0} ∪

∪ \{a_{2} [c_{i_{1}}, …, c_{i_{k}}, \underbrace{a_{2}, …, a_{2}}_{(k+2ik−1)−szer}]^{P} a_{2} | i ≥ 0\}

illetve I_{n,≤k} = L(Σ, ≤ k) = { a_{1}^{t} | t ≥ k + 1, 0 ≤ s_{i} ≤ k} ∪

\{a_{2}[c_{i_{1}}, …, c_{i_{k}}, \underbrace{a_{2}, …, a_{2}}_{t−szer}]^{P} a_{2} | t ≥ k − 1, k ≥ s ≥ 0 \}

I_{n,=k} lényeges tulajdonságai :

1. két diszjunkt ábécé van, a szavak vagy {a_{1}} vagy {a_{2}, c_{1}, …, c_{n}} felettiek,

2. az {a_{2}, c_{1}, …, c_{n}} feletti szavakban a c_{i_{1}}, …, c_{i_{k}} betűk bárhol előfordulhatnak egymáshoz képest,

3. az {a_{2}, c_{1}, …, c_{n}} feletti szavakban pontosan k darab c betű szerepel.

I_{n,≤k} lényeges tulajdonságai ugyanezek, kivéve, hogy az {a_{2}, c_{1}, …, c_{n}} feletti szavakban nem pontosan k darab, hanem legfeljebb k darab c betű szerepel.

3.2.2 A ELP ( 0L, REP ) rendszerek definíciója Példák ELP ( 0L, REP ) nyelvekre

Az egyszerű EG rendszer egy másik módosítását kapjuk, ha az ágensek CF akciószabályait, betűt betűre helyettesítő szabályokra cseréljük. Azaz ekkor egy akció azt jelenti, hogy az ágens két adott betű között álló harmadik betűt más betűre kicserél. Formálisan:

Definíció 14 Az R rendszert betűt betűre helyettesítő rendszernek nevezzük, ha R = ( V, P ), ahol

• V véges, nem üres ábécé

• P ⊆ { (a, c, b) → (a, d, b) | a, b, c, d ∈ V }, betűt betűre helyettesítő szabályok halmaza.

Definíció 15 Egy R = (V, P) betűt betűre helyettesítő rendszerben azt mondjuk, hogy az y szó közvetlenül levezethető az x szóból x, y ∈ V^{∗} esetén (jelölése: x⇒_{R} y), ha teljesülnek az alábbiak:

• x = x_{1}acbx_{2}, y = x_{1}adbx_{2}, ahol x_{1}, x_{2} ∈ V^{∗}

• (a, c, b) → (a, d, b) ∈ P Definíció 16 A Σ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w) rendszert betűt betűre helyettesítő EG rendszernek, vagy rövidebben REP rendszernek nevezünk, ha az alábbiak fennálllnak:

• V_{E} véges, nem üres ábécé

• P_{E} 0L szabályok véges halmaza V_{E} felett

• R_{i} betűt betűre helyettesítő szabályok véges halmaza minden i, 1 ≤ i ≤ n esetén

• w ∈ V_{E}^{+}, kiindulási szó. Mint az előző esetben, V_{E} a környezet ábécéje, P_{E} a környezet fejlődési szabályainak halmaza, az R_{i}-k az ágensekhez tartozó helyettesítőszabályok halmazai, w pedig a környezet kezdőállapota. A REP rendszerbeli levezetés k-tagú team-mel az alábbi módon van definiálva: Definíció 17 Legyen Σ = ( V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w ) REP rendszer és legyen x, y ∈ V_{E}^{∗}. Ekkor azt mondjuk, hogy az y szó közvetlenül levezethető k tagú team-mel az x szóból Σ-ban (jelölése: x ⟹_{Σ}^{≤k} y), ha :

• x = x_{1}c_{1}x_{2}c_{2} … x_{k}c_{k}x_{k+1}, x_{i} ∈ V_{E}^{∗}

• y = y_{1}d_{1}y_{2}d_{2} … y_{k}d_{k}y_{k+1}, y_{i} ∈ V_{E}^{∗}

• x_{1}c_{1}x_{2}c_{2} … x_{l} = α_{l}a_{l}, x_{l+1}c_{l+1} … x_{k}c_{k}x_{k+1} = b_{l}β_{l}, 1 ≤ l ≤ k

• (a_{l}, c_{l}, b_{l}) → (a_{l}, d_{l}, b_{l}) ∈ R_{i_{l}} ahol i_{l} ≠ i_{s} ha l ≠ s

• továbbá x_{j}⇒_{P_{E}} y_{j} minden 1 ≤ j ≤ k + 1 esetén. Definíció 18 Legyen Σ = ( V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w) egy ELP ( 0L, REP ) rendszer . x, y ∈ V_{E}^{∗} esetén azt mondjuk, hogy az y szó közvetlenül levezethető az x szóból legfeljebb k tagú team-mel Σ-ban (jelölése: x ⟹_{Σ}^{≤k} y), ha x ⟹_{Σ}^{=j} y valamely j ≤ k esetén. A ⇒^{=k} tranzitív (és reflexív) lezárását ⟹^{=k}_{Σ}^{+} (illetve ⟹^{=k}_{Σ}^{∗}) jelöli.

Definíció 19 A Σ = (V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w) REP rendszer által a teammel ( a ∈ { = 0, = 1, …, = n, ≤ 1, …, ≤ n }) generált nyelv alatt az

L(Σ, a) = { v ∈ V_{E}^{∗} | w ⟹_{Σ}^{∗}^{a} v }

nyelvet értjük. Itt is bevezetjük az ELP ( 0L, CF ) és ELP ( 0L, INS ) esetekkel teljesen megegyező módon az alábbi jelöléseket:

• ELP_{n,=k}( 0L, REP ) jelöli az n ágenssel rendelkező, k tagú team-mel dolgozó REP rendszerek osztályát.

• ELP_{n,≤k}( 0L, REP ) jelöli az n ágenssel rendelkező, legfeljebb k tagú team-mel dolgozó REP rendszerek osztályát.

• ELP_{=}( 0L, REP ) = ⋃_{n=1}^{∞}⋃_{k=0}^{n}ELP_{n,=k}( 0L, REP )

• ELP_{≤}( 0L, REP ) = ⋃_{n=1}^{∞}⋃_{k=0}^{n}ELP_{n,≤k}( 0L, REP )

• ELP (0L, REP)-et írunk, ha nem érdekes, hogy milyen módban dolgozik a rendszer, sem az, hogy hány ágens van, csak az, hogy az ágensek betűt betűre helyettesítő szabályokat használnak.

A rendszerekhez kapcsolódó nyelvosztályok jelölése, rendre: LELP_{n,=k}( 0L, REP ), LELP_{n,≤k}( 0L, REP ), LELP_{=}(0L, REP), LELP_{≤}(0L, REP), illetve LELP ( 0L, REP ). Példa 3.9 Legyen Σ = ( V_{E}, P_{E}, R_{1}, R_{2}, …, R_{n}, w ) olyan ELP ( 0L, REP ) rendszer, ahol:

• V_{E} = { a_{1}, a_{2}, c_{1}, c_{2}, …, c_{n} }

• P_{E} = { a_{1} → a_{2}^{2}, a_{2} → a_{1}^{2} } ∪_{1≤j≤n}{ c_{j} → a_{1} }

• R_{i} = { (a_{1}, a_{1}, a_{1}) → (a_{1}, c_{i}, a_{1}) } ∪ ∪ { (e, c_{i}, f) → (e, a_{2}, f) | e, f ∈ {a_{1}}∪_{j=1,j≠i}^{n}{c_{j} } }, minden 1 ≤ i ≤ n esetén

• w = a_{1}^{2+k}.

Ekkor:

R_{n,=k} = L(Σ, = k) = { a_{1}^{k+2 4^{i}} | i ≥ 0} ∪

\{ a_{2}^{2}[c_{i_{1}}, …, c_{i_{k}}, \underbrace{a_{2}^{2}, …, a_{2}^{2}}_{(2 4^{i}−2)−szer}]^{P} a_{2}^{2} | i ≥ 0, 0 ≤ i_{s} ≤ n \}

illetve

R_{n,≤k} = L(Σ, ≤ k) = { a_{1}^{f(s_{1},...,s_{i})} | 0 ≤ s_{t} ≤ k, 1 ≤ t} ∪

⋃ \{a_{2}^{2}[c_{i_{1}}, …, c_{i_{s}}, \underbrace{a_{2}^{2}, …, a_{2}^{2}}_{(f(s_{1},...,s_{i})−2−s)−szer}]^{P} a_{2}^{2} | t ≥ 0, k ≥ s ≥ 0, 1 ≤ i_{t} ≤ n, \}

ahol f(s_{1}, …, s_{i}) = (2+k)4^{i} −3∑_{t=1}^{i}4^{(i−t)}s_{t} és s_{t} jelöli a 2t−1-edik lépésben dolgozó ágensek számát. A fenti két nyelvnek a következő lényeges tulajdonságai vannak:

1. mindkét nyelv szavai két csoportba oszthatók, az {a_{1}} felettiekre, illetve az {a_{2}, c_{1}, …, c_{n}} felettiekre,

2. az {a_{2}, c_{1}, …, c_{n}} feletti szavakban a c betűk bárhol előfordulhatnak, kivéve a szó első és utolsó betűjeként,

3. az {a_{2}, c_{1}, …, c_{n}} feletti szavakban R_{n,=k} esetén pontosan, R_{n,≤k} esetén legfeljebb k darab c betű szerepel .

Példa 3.10

Legyen Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}w) olyan ELP ( 0L, REP ) rendszer, ahol:

• V_{E} = { a_{1}, a_{2}, b_{1}, b_{2}, c_{1}, …, c_{n} }

• P_{E} = { a_{1} → a_{2}^{2}, a_{2} → a_{1}^{2}, b_{1} → b_{2}^{2}, b_{2} → b_{1}^{2} }∪_{i=1}^{n}{ c_{i} → a_{1} }

• R_{i} = { (b_{1}, a_{1}, a_{1}) → (b_{1}, c_{i}, a_{1}) } ⋃{ (b_{2}, c_{i}, a_{2}) → (b_{2}, a_{1}, a_{2}) }, ha 1 ≤ i ≤ n

• w = b_{1}a_{1}a_{1}.

= 1 módban a levezetés a következőképpen zajlik:

b_{1}a_{1}a_{1}⇒_{Σ} b_{2}^{2}c_{i}a_{2}^{2}⇒_{Σ} b_{1}^{4}a_{1}a_{1}^{4}⇒_{Σ} b_{2}^{8}c_{2}a_{2}^{8}⇒_{Σ} …

így

L_{R}(n, = 1) = L(Σ, = 1) = { b_{1}^{4^{i}}a_{1}a_{1}^{4^{i}} | i ≥ 1} ∪ {b_{2}^{2 4^{i}}c_{2}a_{2}^{2 4^{i}} | i ≥ 1 } Hasonlóan:

L_{R}(n, ≤ 1) = L(Σ, ≤ 1) = {b_{1}^{4^{i}}a_{1}^{f(s_{1},...,s_{i})}a_{1}^{4^{i}}|i ≥ 1}∪{b_{2}^{2 4^{i}}a_{2}^{f(s_{1},...,s_{i})}a_{2}^{2 4^{i}}|i ≥ 1}∪

∪ { b_{2}^{2 4^{i}}a_{2}^{f(s_{1},...,s_{i})−1}c b_{2}^{2 4^{i}} | i ≥ 1}

ahol s_{t} = 1, ha a 2t−i-edik lépésben nem dolgozott az ágens, s_{t} = 0 különben, és f(s_{1}, …, s_{i}) = ∑_{t=1}^{i} 4^{(i+1−t)}s_{t}. A két nyelv leglényesebb tulajdonságai a következők:

1. mindkét nyelv szavai két csoportba oszthatók, az {a_{1}, b_{1}} felettiekre, illetve az {a_{2}, c_{2}, b_{2}} felettiekre ,

2. c_{2} csak a b és a betűk határán fordulhat elő.

Hierarchia a CF, INS és REP nyelvosztályok körében

Ezen fejezet három nagyobb részre osztható. Az elsőben azt vizsgáljuk meg, hogyan viszonyulnak egymáshoz az LELP_{n,=k}( 0L, CF ), illetve az LELP_{n,≤k}( 0L, CF ) nyelvosztályok n és k különböző értékeire. A második részben ugyanezen kérdésekre keresünk választ az LELP (0L, INS) nyelvosztályba tartozó nyelvek esetén. Végül az LELP ( 0L, REP ) nyelvek hierarchiáját vizsgáljuk meg. Látni fogjuk, hogy a három esetben kapott eredmények igen hasonlóak lesznek.

4.1 Az LELP ( 0L, CF ) nyelvek hierarchiája

Az LELP ( 0L, CF ) nyelvek hierarchiáját először [CVK]-ben vizsgálták. Az alábbiakban az ott kapott eredményeket tárgyaljuk. Először egy lemmát fogalmazunk meg, mely igen hasznos lesz a továbbiakban.

Lemma 1 Legyen L az { L_{n,=k}, L_{n,≤k} | 1 ≤ k ≤ n } halmaz eleme és legyen L_{1} = L ∩ { a_{1} }^{∗}, illetve L_{2} = L ∩ { a_{2}, c_{1}, …, c_{n} }^{∗}. Ha L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, CF ) rendszer esetén, akkor

1. ha v ∈ L_{2}, |v| > N = l max_{1≤i≤m}max_{u→t∈R_{i}}|t|+k max_{1≤i≤n}max_{c_{i}→t∈P_{E}}|t| és w⇒_{Σ}v, akkor w ∈ L_{1},

2. ha v ∈ L_{2} és w⇒_{Σ}v, akkor w ∈ L_{1},

3. ha v ∈ L_{1} és w⇒_{Σ}v, akkor w ∈ L_{2}.

A lemma tehát azt állítja, hogy ha valamely Σ ∈ ELP ( 0L, CF ) rendszer az L nyelvet generálja, akkor az csak olyan formában lehetséges, hogy minden Σ-beli levezetésben felváltva szerepelnek alph(L_{1}) és alph(L_{2}) feletti szavak. Bizonyítás

(1) Tegyük fel, hogy létezik v ∈ L_{2}, amelyre |v| > N, w⇒_{Σ}v, de w ∈ L_{2}. Mivel |v| > N, ezért a w⇒_{Σ}v lépésben P_{E}-ből a_{2} → u, u ∈ alphL_{2}^{+} alakú szabályt is alkalmaztunk (különben |v| ≤ N állna). Így viszont P_{E} nem tartalmazhat a_{2} → u′, u′ ∈ alphL_{1}^{+} alakú szabályt, mert ekkor vegyes indexű betűket tartalmazó szavak is előfordulnának L(Σ, = l)- ben. Mivel L_{1}-ben bármilyen hosszú szavak előfordulnak, P_{E}-nek tartalmaznia kell a_{1} → u′, u′ ∈ alphL_{1}^{+} szabályt (mert a_{2} → u′, u′ ∈ alphL_{1}^{+} alakút nem tartalmazhat). Legyen w ∈ L_{j}, j = 1 vagy j = 2 esetén. Ekkor egy L_{i}-beli szó Σ-beli levezetése során (ha i ≠ j) létezik olyan w_{1}⇒_{Σ}w_{2} lépés, amikor w_{1} ∈ L_{j} és w_{2} ∈ L_{i}. Ebben a lépésben csupa (j) → (i) alakú szabályt használtunk (azaz csupa u_{1} → u_{2} szabályt, ahol u_{1} ∈ alphL_{j}^{+} és u_{2} ∈ alphL_{i}^{+}). Mivel (L_{n,=k} konstrukciója miatt) létezik w_{1}′ ∈ L_{j} szó, melyre w_{1} ⪯ w_{1}′ és |w_{1}′| > m + k, ezért vegyes indexű betűket tartalmazó szót lehetne levezetni a P_{E}-beli a_{j} → u, u ∈ alphL_{j}^{+} szabály segítségével. Ezzel ellentmondásra jutottunk az L_{n,=k} nyelv definíciójával.

(2) A fenti gondolatmenettel az is belátható, hogy minden elég hosszú L_{1}-beli v szó esetén, ha u⇒_{Σ}v teljesül, akkor u ∈ L_{1} is áll. Ha lenne u′⇒_{Σ}v′ lépés, ahol u′, v′ ∈ L_{2}, akkor mivel létezik olyan u′′ ∈ L_{2} szó, melyre u′ ⪯ u′′ és melyre |u′′| > m + k, ezért a P_{E}-beli a_{1} → u, u ∈ alphL_{2}^{+} szabály segítségével vegyes indexű szavakat lehetne levezetni Σ-ban ( létezik a fenti P_{E}-beli szabály, mert az előbb mondottak értelmében hosszú L_{2}-beli szavakat csak L_{1}- beliekből lehet levezetni).

(3) Az (1) és a (2) pont bizonyítását szóról szóra megismételve kaphatjuk a (3) pont állítását, azzzal a kivétellel, hogy N helyett N′ = l max_{1≤i≤m}max_{u→t∈R_{i}}|t| írható.

Először azt vizsgáljuk meg, hogyan viszonyulnak egymáshoz az LELP (0L, CF) nyelvosztályok, n és k különböző 1 ≤ k ≤ n értékeire.

Állítás 1

1. • 1 ≤ k ≤ n esetén, ha n ≤ m, akkor LELP_{n,=k}( 0L, CF ) ⊆ LELP_{m,=k}( 0L, CF ).

• 1 ≤ n, m esetén LELP_{n,=1}( 0L, CF ) = LELP_{m,=1}( 0L, CF ).

• Minden 2 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha m < n vagy l < k, akkor L_{n,=k} ∈ LELP_{n,=k}( 0L, CF ) \ LELP_{m,=l}( 0L, CF ). (L_{n,=k} definíciójáért lásd a 3.5 példát)

2. Minden 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha l > k, akkor létezik olyan L nyelv, melyre: L ∈ LELP_{n,=k}( 0L, CF ) \ LELP_{m,=l}( 0L, CF ).

Bizonyítás

(1) Ha L = L(Σ, = k) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP (0L, CF) rendszerrel, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) ∈ ELP ( 0L, CF ) olyan rendszer, melyre:

• V_{E}′ = V_{E} ∪ { d }, ahol d ∉ V_{E}, új betű

• P_{E}′ = P_{E} ∪ { d → d }

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ n

• R_{j}′ = { d → d }, ha n + 1 ≤ j ≤ m

• w′ = w.

Ekkor L(Σ′, = k) = L(Σ, = k) nyilvánvalóan fennáll, hiszen az R_{n+1}′, …, R_{m}′ ágensek sosem jutnak szóhoz Σ′-ban, tehát minden Σ′-beli levezetés megismételhető Σ-ban. A másik irányú tartalmazás triviális. A második pont bizonyításához azt kell még belátnunk, hogy LELP_{n,=1}( 0L, CF ) ⊆ LELP_{m,=1}( 0L, CF ), ha 1 ≤ m ≤ n. Ha L ∈ LELP_{n,=1}( 0L, CF ) tehát, ha L = L(Σ, = 1) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP ( 0L, CF ) esetén, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) olyan ELP ( 0L, CF ) rendszer, melyre:

• V_{E}′ = V_{E}

• P_{E}′ = P_{E}

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ m − 1

• R_{m}′ = R_{m} ∪ R_{m+1} ∪ … R_{n}

• w′ = w.

Jól látható, hogy L(Σ, = 1) = L(Σ′, = 1), hiszen a Σ-beli levezetéseket meg lehet valósítani Σ′-ben és viszont ( az = 1 mód miatt).

(2) Ha L_{n,=k} = L(Σ, = l) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, CF) rendszerrel, akkor az 1. lemma miatt minden v ∈ L_{2} szóra és minden w⇒_{Σ}v lépésre w ∈ L_{1} teljesül. Nézzük az ilyen lépések során felhasznált olyan szabályokat, amelyek c betűt hoznak be, azaz nézzük a

P_{C} = { a_{1} → αc_{i}β | i ∈ { 1, …, n }, α, β ∈ alphL_{2}^{∗} }

szabályhalmazt, ahol P_{C} P_{E}-beli vagy ágensszabályokat tartalmaz.

• P_{C} nem tartalmazhat P_{E}-beli szabályt, mert ekkor k-nál több c betű fordulhatna elő L(Σ, = l)-beli szavakban.

• Mivel k ≥ 2, ezért léteznek c_{1} és c_{2} különböző c betűk, és ezek bármilyen messze állhatnak egymástól. Ha l = 1 lenne, akkor mivel csak az ágensek hozhatnak be c betűket, a c_{1} és c_{2} minden együttes előfordulására külön szabály lenne szükséges, de az ágensek összesen is csak véges sok szabállyal rendelkeznek. Tehát l = 1 nem lehetséges. Ha pedig l ≥ 2, akkor minden c betűre csak egy ágens létezhet, amely azt a c betűt be tudja hozni, különben két egyforma c betűt tartalmazó szó lehetne L(Σ, = l)-beli szavakban.

• Semelyik Σ-beli ágens sem hozhat be két különféle c betűt, mert ekkor nem tudnánk biztosítani Σ-ban azt, hogy a c betűk bármilyen kombinációban előfordulhassanak.

Az eddigiekből az következik, hogy ha L_{n,=k} = L(Σ, = l), akkor m ≥ n és l ≥ k is fenn kell, hogy álljon.

(3) Az L = { a^{k}, b^{k} } nyelvre k ≥ 1 esetén teljesülnek az alábbiak:

• L = L(Σ, = k), ha Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w ) az az ELP ( 0L, CF ) rendszer, melyre

V_{E} = { a, b }

P_{E} = { a → a, b → b }

R_{i} = { a → b, b → a }, ha 1 ≤ i ≤ n w = a^{k}.

• Másrészt L semmilyen Σ′ ∈ ELP (0L, CF) rendszerrel sem generálható = l > k módban, mert k-nál több ágens nem tud egyszerre dolgozni L szavain, így a levezetések már az első lépésben blokkolódnak.

Ezzel a bizonyítást befejeztük.

A következőkben az LELP_{n,≤k}(0L, CF) nyelvosztályok hierarchiáját vizsgáljuk.

Állítás 2

1. • 1 ≤ k ≤ n esetén, ha n ≤ m, akkor LELP_{n,≤k}( 0L, CF ) ⊆ LELP_{m,≤k}( 0L, CF ).

• 1 ≤ n, m esetén LELP_{n,≤1}( 0L, CF ) = LELP_{m,≤1}( 0L, CF ).

2. Minden 2 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha m < n vagy l < k, akkor L_{n,≤k} ∈ LELP_{n,≤k}( 0L, CF ) \ LELP_{m,≤l}( 0L, CF ). (L_{n,≤k} definíciójáért lásd a 3.5 példát)

3. • Minden 1 ≤ k < n és 1 ≤ l ≤ m esetén, ha l > k, akkor L_{n,≤k} ∈ LELP_{n,≤k}( 0L, CF ) \ LELP_{m,≤l}( 0L, CF ).

• 1 ≤ n ≤ l ≤ m esetén LELP_{n,≤n}(0L, CF) ⊆ LELP_{m,≤l}(0L, CF).

Bizonyítás

(1) Ha L = L(Σ, ≤ k) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP (0L, CF) rendszerrel, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) ∈ ELP ( 0L, CF ) olyan rendszer, melyre:

• V_{E}′ = V_{E}

• P_{E}′ = P_{E}

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ n

• R_{j}′ = P_{E}, ha n + 1 ≤ j ≤ m

• w′ = w.

Ekkor L(Σ′, ≤ k) = L(Σ, ≤ k) fennáll, hiszen a Σ-beli levezetések Σ′-ben is végrehajthatók és megfordítva szintúgy. Azt kell még belátnunk, hogy LELP_{n,≤1}( 0L, CF ) ⊆ LELP_{m,≤1}( 0L, CF ), ha 1 ≤ m ≤ n. Ha L ∈ LELP_{n,≤1}( 0L, CF ) tehát, ha L = L(Σ, ≤ 1) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP ( 0L, CF ) esetén, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) olyan ELP ( 0L, CF ) rendszer, melyre:

• V_{E}′ = V_{E}

• P_{E}′ = P_{E}

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ m − 1

• R_{m}′ = R_{m} ∪ R_{m+1} ∪ … R_{n}

• w′ = w.

Jól látható, hogy L(Σ, ≤ 1) = L(Σ′, ≤ 1), hiszen a Σ-beli levezetéseket meg lehet valósítani Σ′-ben és viszont ( a ≤ 1 mód miatt).

(2) A bizonyítás szinte teljesen megegyezik az 1. állítás (2) pontjának bizonyításával: Az 1. lemma miatt, ha L_{n,≤k} = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w ) ∈ ELP ( 0L, CF ) rendszerrel, akkor minden v ∈ L_{2} szóra és minden w⇒_{Σ}v lépésre w ∈ L_{1} teljesül.

• Az ilyen lépések során felhasznált szabályok között, amelyek c betűt hoznak be, nem lehet P_{E}-beli szabály, mert ekkor k-nál több c betű fordulhatna elő L(Σ, ≤ l)-beli szavakban.

• Mivel k ≥ 2, ezért léteznek c_{1} és c_{2} különböző c betűk, és ezek bármilyen messze állhatnak egymástól. Ha l = 1 lenne, akkor mivel csak az ágensek hozhatnak be c betűket, a c_{1} és c_{2} minden együttes előfordulására külön szabály lenne szükséges, de az ágensek összesen is csak véges sok szabállyal rendelkeznek. Tehát l = 1 nem lehetséges. Ha pedig l ≥ 2, akkor minden c betűre csak egy ágens létezhet, amely azt a c betűt be tudja hozni, különben két egyforma c betűt tartalmazó szó lehetne L(Σ, ≤ l)-beli szavakban.

• Semelyik Σ-beli ágens sem hozhat be két különféle c betűt, mert ekkor nem tudnánk biztosítani Σ-ban azt, hogy a c betűk bármilyen kombinációban előfordulhassanak.

Az eddigiekből az következik, hogy ha L_{n,≤k} = L(Σ, ≤ l), akkor m ≥ n és l ≥ k is fenn kell, hogy álljon.

(3) Az előző gondolatmenetet folytatva, (mivel l > k ≥ 1, tehát l ≥ 2 teljesül) : ha L_{n,≤k} = L(Σ, ≤ l) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, CF) és l > k esetén , akkor m ≥ n és l ≥ k teljesül. Sőt, Σ-ban létezik n darab ágens, R_{1}, …, R_{n}, melyek mindegyike egy-egy c betűt tud behozni a levezetés során. Ha k < n és k < l, akkor k + 1 ≤ n és k + 1 ≤ l is fennáll. Így egy elég hosszú L_{n,≤k} ∩ { a_{1} }^{∗}-beli szón k + 1 ágenst dolgoztatva az R_{1}, …, R_{n} közül, ≤ l módban, k + 1 darab c betű szerepelne L_{n,≤k}-beli szóban. Ha pedig L = L(Σ, ≤ n) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP (0L, CF) esetén, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) az az ELP ( 0L, CF ) rendszer, melyre:

• V_{E}′ = V_{E}

• P_{E}′ = P_{E}

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ n

• R_{j}′ = P_{E}, ha n < j ≤ m

• w′ = w.

Ekkor L( Σ, ≤ n) ⊆ L( Σ′, ≤ l ), hiszen a Σ-beli levezetések Σ′-ben is megvalósíthatók lépésről lépésre. Másrészt L( Σ′, ≤ l) ⊆ L( Σ, ≤ n), mert hiába dolgozik Σ′-ben ≤ l ágens, ha az R_{1}, …, R_{n}-en felüliek csak P_{E} szabályokat használhatnak. Tehát a Σ′ levezetéseket is le lehet másolni Σ-ban.

Végül megvizsgáljuk a LELP_{n,=k}(0L, CF) és LELP_{m,≤l}(0L, CF) nyelvosztályok egymáshoz való viszonyát.

Állítás 3

1. Bármely 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén L_{n,=k} ∈ LELP_{n,=k}( 0L, CF ) \ LELP_{m,≤l}( 0L, CF ).

2. Minden 1 ≤ k ≤ n és 2 ≤ l ≤ m esetén létezik olyan L nyelv, melyre: L ∈ LELP_{n,≤k}( 0L, CF ) \ LELP_{m,=l}( 0L, CF ).

3. Ha m ≥ n ≥ 1, akkor LELP_{n,≤1}( 0L, CF ) ⊆ LELP_{m,=1}( 0L, CF ), ha pedig m < n, akkor L_{n,≤1} ∈ LELP_{n,≤1}(0L, CF)\LELP_{m,=1}(0L, CF).

4. Ha 2 ≤ k ≤ n és 1 ≤ m, akkor L_{n,≤k} ∈ LELP_{n,≤k}( 0L, CF ) \ LELP_{m,=1}( 0L, CF ).

Bizonyítás (1) Tegyük fel az ellenkezőjét, azaz, hogy L_{n,=k} = L(Σ, ≤ l) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, CF) esetén . Ha v ∈ L_{n,=k} akkor a ≤ l mód definíciója miatt minden v⇒_{P_{E}}w lépésben keletkező w szóra w ∈ L_{n,=k} is fennáll. Legyen v = a_{1}^{k+4^{j}} egy általános elem L_{1} = L_{n,=k} ∩ { a_{1} }^{∗}-ból és legyen v⇒_{P_{E}}u. Az 1. lemma miatt u ∈ L_{2} = L_{n,=k} ∩ { a_{2}, c_{1}, …, c_{n} }^{∗} áll, azaz az u szó tartalmaz c betűt. Eszerint P_{E} tartalmaz c-t behozó szabályt, ami viszont lehetetlen, mert ekkor k-nál több c betűt tartalmazó szavak is lennének L_{2}- ben. Így ellentmondásra jutottunk, azaz L_{n,=k} ∉ LELP_{m,≤l}( 0L, CF ).

(2) Legyen L az { a, b } nyelv. Ekkor L ∈ LELP_{n,≤k}( 0L, CF ) minden 1 ≤ k ≤ n esetén, mert a Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP ( 0L, CF ) rendszerre , ahol • V_{E} = { a, b, c }

• P_{E} = { a → b, b → a, c → c }

• R_{i} = { c → c }, ha 1 ≤ i ≤ n

• w = a,

teljesül, hogy L(Σ, ≤ k) = { a, b }. Másrészt, ha l ≥ 2, akkor az = l módbeli levezetés már az első lépésben megakad, mert minden L-beli szó egy betűből áll.

(3) Ha L = L(Σ, ≤ 1) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP (0L, CF) rendszer esetén, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) az az ELP ( 0L, CF ) rendszer, melyre:

• V_{E}′ = V_{E}

• P_{E}′ = P_{E}

• R_{i}′ = R_{i} ∪ P_{E}, ha 1 ≤ i ≤ n

• R_{j}′ = P_{E}, ha n < j ≤ m

• w′ = w.

Ekkor L(Σ, ≤ 1) ⊆ L(Σ′, = 1), hiszen minden Σ-beli lépést meg lehet valósítani a másik rendszerrel is ( a megfelelő ágensek kiválasztásával) . A másik irányú tartalmazás abból következik, hogy Σ′ működését = 1 módban szimulálni lehet Σ ≤ 1 módbeli működésével. Ha pedig m < n , akkor L_{n,≤1} ∈ LELP_{n,≤1}( 0L, CF ) ⊆ LELP_{m,=1}( 0L, CF ). Ezen állítás bizonyítása a következő: Ha L_{n,≤1} = L(Σ, = 1) áll valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, CF) rendszerrel, akkor az 1. lemma miatt L_{2}-beli szavakat csak L_{1}-beli szavakból lehet levezetni Σ-ban, de — az 1. állítás (2) pont bizonyításának gondolatmenetét használva — csak ágensek hozhatnak be c betűt, és egy ágens legfeljebb egy féle c_{i}-t, tehát m ≥ n szükséges.

(4) Az 1. állítás (2) pontjánál mutatott bizonyítás szóról szóra elismételhető ebben az esetben is, annyi különbséggel, hogy az 1. lemmát itt értelemszerűen az L_{n,≤k} nyelvre kell alkalmazni.

Legvégül az eddig vizsgált nyelosztályoknak az 0L nyelvosztállyal való kapcsolatát nézzük meg.

Állítás 4 1. Minden 1 ≤ l ≤ m esetén 0L ⊂ LELP_{m,≤l}( 0L, CF ).

2. Minden 1 ≤ n esetén 0L ⊂ LELP_{n,=1}( 0L, CF ).

3. Minden 2 ≤ k ≤ n esetén 0L és LELP_{n,=k}(0L, CF) összehasonlíthatatlanok.

Bizonyítás (1) Ha L = L(Σ) valamely Σ = ( V_{E}, P_{E}, w ) 0L rendszerrel, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′) az az ELP ( 0L, CF ) rendszer, melyre

• V_{E}′ = V_{E}

• P_{E}′ = P_{E}

• R_{j}′ = P_{E}, ha 1 ≤ j ≤ m

• w′ = w.

Világos, hogy L(Σ′, ≤ l) = L(Σ). A szigorú tartalmazás abból következik, hogy az L_{m,≤l} nyelvek nem 0L nyelvek. (Ezt ugyanúgy lehet belátni, ahogy megmutattuk, hogy ha L_{m,≤l} = L(Σ, = k) valami Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w ) ∈ ELP ( 0L, CF ) rendszerrel, akkor Σ-ban legalább m ágens van,és l ≥ k. Lásd a 1. állítás bizonyítását.)

(2) Ha L = L(Σ) valamely Σ = ( V_{E}, P_{E}, w ) 0L rendszerrel, akkor legyen Σ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{n}′, w′ ) az az ELP ( 0L, CF ) rendszer, melyre

• V_{E}′ = V_{E}

• P_{E}′ = P_{E}

• R_{j}′ = P_{E}, ha 1 ≤ j ≤ m

• w′ = w.

Világos, hogy L(Σ′, = 1) = L(Σ) Másrészt L_{n,=1} ∉ 0L ( lásd az 1. állítás bizonyítását ). Tehát szigorú tartalmazás áll fenn a két osztály között.

(3) Egyrészt L_{n,=k} ∉ 0L ( lásd az 1. állítás bizonyítását ), másrészt az L = { a, b } nyelvre teljesülnek az alábbiak:

• L ∈ 0L, mert a Σ = ( V_{E}, P_{E}, w) rendszerrel L = L(Σ) áll, ha

V_{E} = { a, b }

P_{E} = { a → b, b → a } w = a.

• L ∉ LELP_{n,=k}( 0L, CF ) ha k ≥ 2, mivel a levezetés már az első lépésben blokkolódik, mert csak egy ágens tud dolgozni.

Ezzel a bizonyítást befejeztük.

Foglaljuk most össze az ELP ( 0L, CF ) nyelvosztályok hierarchiájára kapott eredményeinket:

Tétel 1 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén

1. • LELP_{m,=1}( 0L, CF ) = LELP_{n,=1}( 0L, CF ) bármely n, m ≥ 1 esetén,

• LELP_{n,=k}( 0L, CF ) ⊂ LELP_{m,=k}( 0L, CF ) ha k > 1 és m > n,

• különben az LELP_{n,=k}(0L, CF) és LELP_{m,=l}(0L, CF) nyelvosztályok összehasonlíthatatlanok.

2. • LELP_{m,≤1}( 0L, CF ) = LELP_{n,≤1}( 0L, CF ) bármely n, m ≥ 1 esetén,

• LELP_{n,≤k}( 0L, CF ) ⊂ LELP_{m,≤k}( 0L, CF ) ha k > 1 és m > n,

• LELP_{n,≤n}(0L, CF) ⊂ LELP_{m,≤l}(0L, CF) ha n ≤ l ≤ m és l ≠ n vagy l ≠ m,

• különben az LELP_{n,≤k}(0L, CF) és LELP_{m,≤l}(0L, CF) nyelvosztályok összehasonlíthatatlanok.

3. • LELP_{m,≤1}(0L, CF) ⊂ LELP_{n,=1}(0L, CF) bármely n ≤ m esetén,

• különben az LELP_{n,=k}(0L, CF) és LELP_{m,≤l}(0L, CF) nyelvosztályok összehasonlíthatatlanok.

Bizonyítás Az tétel állításai a 1, 2, 3 állítások közvetlen következményei.

4.2 Az LELP ( 0L, INS ) nyelvek hierarchiája

A továbbiakban először az LELP ( 0L, INS ) rendszerek által generált nyelveket fogjuk vizsgálni. A kérdések ugyanazok lesznek, mint a CF esetben: mi az LELP_{n,=k}( 0L, INS ) és LELP_{m,≤l}( 0L, REP ) osztályok viszonya 1 ≤ k ≤ n és 1 ≤ l ≤ m különböző értékeire? A kapott eredmények nagyon hasonlóak az ELP (0L, CF) esethez, sőt maguk a bizonyítások is, ezért csak ott fogjuk részletezi az állíások bizonyításait, ahol eltérés van. Az I_{n,=k} illetve az I_{m,≤l} nyelvek definíciójáért lásd az 3.8. példát. Most is egy lemmával kezdjük a vizsgálatot:

Lemma 2 Legyen L az { I_{n,=k}, I_{n,≤k} | 1 ≤ k ≤ n } halmaz eleme és legyen L_{1} = L ∩ { a_{1} }^{∗}, illetve L_{2} = L ∩ { a_{2}, c_{1}, …, c_{n} }^{∗}. Ha L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, INS ) rendszer esetén, akkor

1. v ∈ L_{2} és w⇒_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ}v esetén w ∈ L_{2} áll.

Bizonyítás (1) Először N-nél hosszabb L_{2}-beli szavakra látjuk be az állítást, ahol N = l max_{1≤i≤m} max_{(u,t,v)∈R_{i}} |t| + k max_{1≤i≤n} max_{(c_{i}→t)∈P_{E}} |t|. Tegyük fel, hogy létezik v ∈ L_{2}, amelyre |v| > N, w⇒_{Σ}v, de w ∈ L_{2}. Ekkor a w⇒_{Σ}v lépésben P_{E}-ből a_{2} → u, u ∈ alphL_{2}^{+} alakú szabályt is alkalmaztunk (különben |v| ≤ N állna). Tehát P_{E} nem tartalmazhat a_{2} → u′, u′ ∈ alphL_{1}^{+} alakú szabályt, a vegyes indexű betűkből álló szavak tilalma miatt. Mivel L_{1}-ben bármilyen hosszú szavak előfordulnak, P_{E} tartalmaz a_{1} → u′, u′ ∈ alphL_{1}^{+} szabályt (mert a_{2} → u′, u′ ∈ alphL_{1}^{+} alakút nem tartalmazhat). Ha w ∈ L_{j}, j = 1 vagy j = 2 esetén, akkor egy L_{i}-beli szó Σ-beli levezetése során (ha i ≠ j) létezik olyan w_{1}⇒_{Σ}w_{2} lépés, amikor w_{1} ∈ L_{j} és w_{2} ∈ L_{i}. Ebben a lépésben az ágensek alphL_{j}-beli környezetbe alphL_{i}-beli szót szúrtak be, ezt a környezet a_{j} → u, u ∈ alphL_{j}^{∗} szabályával együtt alkalmazva vegyes indexű betűket tartalmazó szót tudunk levezetni, ami nem lehet. Ezzel ellentmondásra jutottunk az I_{n,=k} nyelv definíciójával. Teljesen hasonlóan az is belátható, hogy minden elég hosszú L_{1}-beli v szó esetén, ha u⇒_{Σ}v teljesül, akkor u ∈ L_{1} is áll. Ha pedig v ∈ L_{2} tetszőleges szó és w⇒_{Σ}v, de w ∈ L_{2}, akkor a P_{E}-beli a_{2} → u, u ∈ alphL_{1}^{+} szabály és a w⇒_{Σ}v során használt szabályok segítségével vegyes indexű szavakat lehetne levezetni Σ-ban ( létezik a fenti P_{E}-beli szabály, mert az előbb mondottak értelmében hosszú L_{2}-beli szavakat csak L_{1}- beliekből lehet levezetni).

(3) Az (1) bizonyítását szóról szóra megismételve kaphatjuk a (2) pont állítását, azzal a kivétellel, hogy N helyett N′ = l max_{1≤i≤m}max_{(u,t,v)∈R_{i}} |t| írható.

Az LELP ( 0L, INS ) nyelvosztályok hierarchiáját vizsgálva pontosan azt az eredményt kapjuk, mint a CF esetben:

Állítás 5

1. • 1 ≤ k ≤ n esetén, ha n ≤ m akkor

LELP_{n,=k}( 0L, INS ) ⊆ LELP_{m,=k}( 0L, INS ).

• 1 ≤ n, m esetén LELP_{n,=1}( 0L, INS ) = LELP_{m,=1}( 0L, INS ).

2. Minden 2 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha m < n vagy l < k, akkor L_{n,=k} ∈ LELP_{n,=k}( 0L, INS ) \ LELP_{m,=l}( 0L, INS ). (I_{n,=k} definíciójáért lásd a 3.8. példát)

3. Minden 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha l > k, akkor létezik olyan L nyelv, melyre: L ∈ LELP_{n,=k}( 0L, INS ) \ LELP_{m,=l}( 0L, INS ).

Bizonyítás

(1) Ha L = L(Σ, = k) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP (0L, INS) rendszerrel, akkor legyen Σ′ = (V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′) ∈ ELP (0L, INS) olyan rendszer, melyre:

• V_{E}′ = V_{E} ∪ { d } ahol d ∉ V_{E}, új betű

• P_{E}′ = P_{E} ∪ { d → d }

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ n

• R_{j}′ = { ( d, d, d) }, ha n + 1 ≤ j ≤ m

• w′ = w.

Ekkor L(Σ′, = k) = L(Σ, = k), hiszen az R_{n+1}′, …, R_{m}′ ágensek sosem vesznek részt Σ′-beli levezetésben, tehát minden Σ′-beli levezetés megismételhető Σ-ban. A másik irányú tartalmazás pedig nyilvánvaló. Azt kell még belátnunk, hogy LELP_{n,=1}(0L, INS) ⊆ LELP_{m,=1}(0L, INS), ha 1 ≤ m ≤ n. Ha L ∈ LELP_{n,=1}( 0L, INS ), tehát, ha L = L(Σ, = 1) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP ( 0L, INS ) esetén, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) olyan ELP ( 0L, INS ) rendszer, melyre:

• P_{E}′ = P_{E}

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ m − 1

• R_{m}′ = R_{m} ∪ R_{m+1} ∪ … R_{n}

• w′ = w.

Nyilvánvaló, hogy L(Σ, = 1) = L(Σ′, = 1).

(2) Ha L_{n,=k} = L(Σ, = l) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, INS) rendszerrel, akkor a 2. lemma miatt minden v ∈ L_{2} szóra és minden w⇒_{Σ}v lépésre w ∈ L_{1} teljesül. Nézzük az ilyen lépések során felhasznált olyan szabályokat, amelyek c betűt hoznak be.

• P_{C} nem tartalmazhat P_{E}-beli szabályt, mert ekkor k-nál több c betű fordulhatna elő L(Σ, = l)-beli szavakban.

• Mivel k ≥ 2, ezért léteznek c_{1} és c_{2} különböző c betűk, és ezek bármilyen messze állhatnak egymástól. Ha l = 1 lenne, akkor mivel csak az ágensek hozhatnak be c betűket, a c_{1} és c_{2} minden együttes előfordulására külön szabály lenne szükséges, de az ágensek összesen is csak véges sok szabállyal rendelkeznek. Tehát l = 1 nem lehetséges. Ha pedig l ≥ 2, akkor minden c betűre csak egy ágens létezhet, amely azt a c betűt be tudja hozni, különben két egyforma c betűt tartalmazó szó lehetne L(Σ, = l)-beli szavakban.

• Semelyik Σ-beli ágens sem hozhat be két különféle c betűt, mert ekkor nem tudnánk biztosítani Σ-ban azt, hogy a c betűk bármilyen kombinációban előfordulhassanak.

Az eddigiekből az következik, hogy ha L_{n,=k} = L(Σ, = l), akkor m ≥ n és l ≥ k is fennáll.

(3) Az I_{n,=k} nyelvben előforduló szavak hosszai rendre: 1+k, 1+2k, 1+3k, . . .. Ha indirekt feltesszük, hogy I_{n,=k} = L(Σ, = l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w ) ∈ ELP ( 0L, INS ) esetén, akkor a következőképpen jutunk ellentmondásra: Ha k ≥ 2, akkor léteznek L_{2} = I_{n,=k} ∩ { a_{2}, c_{1}, …, c_{n} }^{∗} -ben αc_{i}c_{j}β alakú szavak, ahol α, β ∈ (alphL_{2})^{∗} és i ≠ j. Mivel egy ágens se hozhat be kétféle c betűt (hiszen most l > k ≥ 2, tehát az előző pontbeli gondolatmenet most is elmondható), ezért léteznie kell (a_{1}, c_{j}γ, a_{1}) ágens szabálynak Σ-ban, valami γ ∈ (alphL_{2})^{∗} esetén, mert csak így lehet biztosítani, hogy c_{j} közvetlenül c_{i} után állhasson. Ebből viszont az is következik, hogy P_{E}-ben nem lehet a_{1} → λ szabály, mert ha lenne, akkor c_{j}-vel kezdődő szó lenne L(Σ, = l)-ben. Ha pedig nincs ilyen szabály P_{E}-ben, akkor mivel minden lépésben l > k ágens dolgozik, ezért a

v⇒_{Σ}a_{2}[ c_{i_{1}}, …, c_{i_{k}}, \underbrace{a_{2}, …, a_{2}}_{k−1}] a_{2} lépésben |v| ≤ 2k + 1 − l < k + 1-nek kellene

állnia, ami lehetetlen. Ezzel k ≥ 2 esetére beláttuk az állítást. Ha pedig k = 1, akkor az a_{2}c_{1}a_{2} szó I_{n,=k}-ban van. Továbbá az is igaz, hogy v⇒_{Σ}a_{2}c_{1}a_{2} esetén v ∈ L_{1}, tehát v = a_{1}^{s} alakú. Mivel c_{1} se szó elején, se szó végén nem fordulhat elő, ezért ha P_{E}-ben létezik a_{1} → λ szabály, akkor c_{1}-et csak (a_{1}, αa_{2}c_{1}a_{2}β, a_{1}) alakú ágensszabály hozhat be, ahol α, β ∈ (alphL_{2})^{∗}. De így a v⇒_{Σ}a_{2}c_{1}a_{2} lépés során nem tudna egynél több ágens dolgozni, ez pedig ellentmond az l > k = 1 feltételnek. Ha viszont nem létezik a_{1} → λ szabály P_{E}-ben, akkor minden lépésben legalább l > k = 1-el nő a szó hossza a levezetésben, így v⇒_{Σ}a_{2}c_{1}a_{2} esetén |v| ≤ 1-nek kellene állnia, ami nem lehetséges.

Az LELP_{n,≤k}(0L, INS) nyelvosztályokra kapott eredmények is teljesen megegyeznek a CF esettel:

Állítás 6 1 ≤ k ≤ n és 1 ≤ l ≤ m

1. • n ≤ m esetén LELP_{n,≤k}( 0L, INS ) ⊆ LELP_{m,≤k}( 0L, INS ).

• 1 ≤ n, m esetén LELP_{n,≤1}( 0L, INS ) = LELP_{m,≤1}( 0L, INS ).

2. Minden 2 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha m < n vagy l < k, akkor I_{n,≤k} ∈ LELP_{n,≤k}( 0L, INS ) \ LELP_{m,≤l}( 0L, INS ). (I_{n,≤k} definíciójáért lásd a 3.8 példát.)

3. • Minden 1 ≤ k < n és 1 ≤ l ≤ m esetén, ha l > k, akkor I_{n,≤k} ∈ LELP_{n,≤k}( 0L, INS ) \ LELP_{m,≤l}( 0L, INS ).

• 1 ≤ n ≤ l ≤ m esetén LELP_{n,≤n}(0L, INS) ⊆ LELP_{m,≤l}(0L, INS).

Bizonyítás

(1) Ha L = L(Σ, ≤ k) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP (0L, REP) rendszerrel, akkor legyen Σ′ = (V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′) ∈ ELP (0L, REP) olyan rendszer, melyre:

• V_{E}′ = V_{E} ∪ { d }, ahol d ∉ V_{E}, új betű • P_{E}′ = P_{E} ∪ { d → d }

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ n

• R_{j}′ = { ( d, d, d) }, ha n + 1 ≤ j ≤ m

• w′ = w. Ekkor L(Σ′, ≤ k) = L(Σ, ≤ k) fennáll. (Lásd az 5. állítás bizonyítását). Azt kell még belátnunk, hogy LELP_{n,≤1}(0L, INS) ⊆ LELP_{m,≤1}(0L, INS), ha 1 ≤ m ≤ n. Ez pontosan ugyanúgy történik, mint az ELP ( 0L, CF ) esetben, úgyhogy lásd a 2. állítás bizonyításának megfelelő részét.

A (2) pont és a (3) pont első állításának bizonyítása ugyanúgy történik, mint az ELP ( 0L, CF ) esetben, tehát lásd a 2. állítás bizonyítását, azzal a kivétellel, hogy a 2. lemmát kell használni az I_{n,≤k} nyelvre. A (3) pont fennmaradó részének bizonyítása a következő: Ha L = L(Σ, ≤ n) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP ( 0L, INS) esetén , akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′) az az ELP ( 0L, INS) rendszer, melyre:

• V_{E}′ = V_{E} ∪ { d } ahol d ∉ V_{E}, új betű

• P_{E}′ = P_{E} ∪ { d → d }

• R_{i}′ = R_{i}, ha 1 ≤ i ≤ n

• R_{j}′ = { ( d, d, d)}, ha n < j ≤ m

• w′ = w. Világos, hogy L(Σ, ≤ k) = L(Σ′, ≤ l), hiszen a Σ′-beli új ágensek soha nem vesznek részt a levezetésben. A következő állítás mutatja az első eltérést a CF esethez képest: Állítás 7

1. Bármely 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén I_{n,=k} ∈ LELP_{n,=k}( 0L, INS ) \ LELP_{m,≤l}( 0L, INS ).

2. Minden 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén létezik olyan L nyelv, melyre: L ∈ LELP_{m,≤l}( 0L, INS ) \ LELP_{n,=k}( 0L, INS ).

Bizonyítás

(1) Ha I_{n,=k} = L(Σ, ≤ l) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, INS) esetén , akkor a ≤ l mód definíciója miatt minden v⇒_{P_{E}}w lépésben keletkező w szóra v = a_{1}^{k+1} esetén w ∈ L_{n,=k} is fennáll. Az 1. lemma miatt w ∈ L_{2} = I_{n,=k} ∩ { a_{2}, c_{1}, …, c_{n} }^{∗} áll, azaz a w szó tartalmaz c betűt. Eszerint P_{E} tartalmaz c-t behozó szabályt, ami viszont lehetetlen, mert ekkor k-nál több c betűt tartalmazó szavak is lennének L_{2}- ben.

(2) Legyen L az { a, b } nyelv. Ekkor L ∈ LELP_{m,≤l}( 0L, INS ) minden 1 ≤ l ≤ m esetén, mert a Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, INS ) rendszerre , ahol

• V_{E} = { a, b }

• P_{E} = { a → b, b → a }

• R_{i} = { ( a, a, a) }, ha 1 ≤ i ≤ m

• w = a,

teljesül, hogy L(Σ, ≤ l) = { a, b }. Másrészt L ∉ LELP_{n,=k}( 0L, INS), ha k ≥ 1, mert az L nyelv szavaira nem lehet beszúrószabályt alkalmazni.

Az LELP ( 0L, INS) nyelvosztályok és az 0L nyelvosztály kapcsolatáról szól a következő állítás:

Állítás 8

1. Minden 1 ≤ l ≤ m esetén 0L ⊂ LELP_{m,≤l}( 0L, INS ).

2. Minden 1 ≤ k ≤ n, esetén 0L és LELP_{n,=k}( 0L, INS ) összehasonlíthatatlanok.

Bizonyítás

(1) Azt, hogy az 0L nyelveket elő lehet állítani ELP_{m,≤l}(0L, INS) rendszerrel minden 1 ≤ l ≤ m esetén, a következő konstrukció mutatja: Ha L = L(Σ) valamely Σ = ( V_{E}, P_{E}, w ) 0L rendszer esetén, akkor legyen Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) az az ELP ( 0L, INS ) rendszer, melyre:

• V_{E}′ = V_{E} ∪ { d }, ahol d ∉ V_{E}, új betű

• P_{E}′ = P_{E} ∪ { d → d }

• R_{j}′ = { ( d, d, d)}, ha 1 ≤ j ≤ m

• w′ = w.

Nyilvánvalóan fennáll, hogy L(Σ) = L( Σ′, ≤ l). A szigorú tartalmazás abból következik, hogy az I_{m,≤l} nyelvek nem 0L nyelvek. Ezt ugyanígy lehet belátni, ahogy megmutattuk, hogy ha I_{m,≤l} = L(Σ, = k) valami Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w ) ∈ ELP ( 0L, INS ) rendszerrel, akkor Σ-ban legalább m ágens van és l ≤ k. (Lásd az 5 állítás bizonyítását.)

(2) Az, hogy I_{n,=k} ∈ LELP_{n,=k}(0L, INS)\0L ugyanúgy bizonyítható, ahogy az 5. állítás (2) pontja. Az állítás második felét pedig az L = {a, b} nyelv mutatja, mert ezen nyelvre L ∈ 0L\LELP_{n,=k}(0L, INS) áll. (Lásd a 7. állítás első részénél leírtakat.)

Foglaljuk most össze az ELP (0L, INS) nyelvosztályok hierarchiájára kapott eredményeinket:

Tétel 2 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén

1. • LELP_{m,=1}( 0L, INS ) = LELP_{n,=1}( 0L, INS ) bármely n, m ≥ 1 esetén,

• LELP_{n,=k}(0L, INS) ⊂ LELP_{m,=k}(0L, INS), ha k > 1 és m > n,

• különben az LELP_{n,=k}(0L, INS) és LELP_{m,=l}(0L, INS) nyelvosztályok összehasonlíthatatlanok.

2. • LELP_{m,≤1}( 0L, INS ) = LELP_{n,≤1}( 0L, INS ) bármely n, m ≥ 1 esetén,

• LELP_{n,≤k}(0L, INS) ⊂ LELP_{m,≤k}(0L, INS), ha k > 1 és m > n,

• LELP_{n,≤n}( 0L, INS ) ⊂ LELP_{m,≤l}( 0L, INS ), ha n ≤ l ≤ m és l ≠ n vagy l ≠ m,

• különben az LELP_{n,≤k}(0L, INS) és LELP_{m,≤l}(0L, INS) nyelvosztályok összehasonlíthatatlanok.

3. Az LELP_{n,=k}(0L, INS) és LELP_{m,≤l}(0L, INS) nyelvosztályok összehasonlíthatatlanok.

Bizonyítás A tétel állításai a 5, 6, 7 állítások közvetlen következményei.

4.3 Az LELP ( 0L, REP ) nyelvek hierarchiája

Az eddig vizsgált kérdéseket tekintjük az LELP ( 0L, REP ) nyelvek esetén is; az LELP ( 0L, INS) esettel teljesen megegyező eredményre fogunk jutni. A bizonyítások nagyrészt megegyeznek az INS esetben látotakkal , ezért csak akkor térek ki rájuk, ha valami eltérés mutatkozik. Az LELP ( 0L, REP ) nyelvek esetén is teljesül a szokásos lemma:

Lemma 3 Legyen L az { R_{n,=k}, I_{n,≤k} | 1 ≤ k ≤ n } halmaz eleme és legyen L_{1} = L ∩ { a_{1} }^{∗}, illetve L_{2} = L ∩ { a_{2}, c_{1}, …, c_{n} }^{∗}. Ha L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, REP ) rendszer esetén, akkor

1. v ∈ L_{2} és w⇒_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ}v esetén w ∈ L_{2} áll.

Bizonyítás (1) Először N-nél hosszabb L_{2}-beli szavakra látjuk be az állítást, ahol N = l + k max_{1≤i≤n} max_{(c_{i}→t)∈P_{E}} |t|. Tegyük fel, hogy létezik v ∈ L_{2}, amelyre |v| > N, w⇒_{Σ}v, de w ∈ L_{2}. Ekkor a w⇒_{Σ}v lépésben P_{E}-ből a_{2} → u, u ∈ alphL_{2}^{+} alakú szabályt is alkalmaztunk (különben |v| ≤ N állna). Tehát P_{E} nem tartalmazhat a_{2} → u′, u′ ∈ alphL_{1}^{+} alakú szabályt, a vegyes indexű szavak tilalma miatt. Mivel L_{1}-ben bármilyen hosszú szavak előfordulnak, P_{E} tartalmaz a_{1} → u′, u′ ∈ alphL_{1}^{+} szabályt (mert a_{2} → u′, u′ ∈ alphL_{1}^{+} alakút nem tartalmazhat). Ha w ∈ L_{j}, j = 1 vagy j = 2 esetén, akkor egy L_{i}-beli szó Σ-beli levezetése során (ha i ≠ j) létezik olyan w_{1}⇒_{Σ}w_{2} lépés, amikor w_{1} ∈ L_{j} és w_{2} ∈ L_{i}. Ebben a lépésben az ágensek alphL_{j}-beli környezetben alphL_{i}- beli betűre helyettesítettek egy alphL_{j}-beli betűt, ezt a környezet a_{j} → u, u ∈ alphL_{j}^{+} szabályával együtt alkalmazva vegyes indexű betűket tartalmazó szót tudunk levezetni, ami nem lehet. Ezzel ellentmondásra jutottunk az R_{n,=k} nyelv definíciójával. Teljesen hasonlóan az is belátható, hogy minden elég hosszú L_{1}-beli v szó esetén, ha u⇒_{Σ}v teljesül, akkor u ∈ L_{1} is áll. Ha pedig v ∈ L_{2} tetszőleges szó és w⇒_{Σ}v, de w ∈ L_{2}, akkor a P_{E}-beli a_{2} → u, u ∈ alphL_{1}^{+} szabály és a w⇒_{Σ}v során használt szabályok segítségével vegyes indexű szavakat lehetne levezetni Σ-ban ( létezik a fenti P_{E}-beli szabály, mert az előbb mondottak értelmében hosszú L_{2}-beli szavakat csak L_{1}- beliekből lehet levezetni).

(3) Az (1) bizonyítását szóról szóra megismételve kaphatjuk a (2) pont állítását, azzzal a kivétellel, hogy N helyett N′ = l írható.

1. • 1 ≤ k ≤ n esetén, ha n ≤ m akkor LELP_{n,=k}( 0L, REP ) ⊆ LELP_{m,=k}( 0L, REP ).

• 1 ≤ n, m esetén LELP_{n,=1}( 0L, REP ) = LELP_{m,=1}( 0L, REP ).

2. Minden 2 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha m < n vagy l < k, akkor L_{n,=k} ∈ LELP_{n,=k}( 0L, REP ) \ LELP_{m,=l}( 0L, REP ). (R_{n,=k} definíciójáért lásd a 3.9 példát)

3. Minden 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha l > k, akkor létezik olyan L nyelv, melyre: L ∈ LELP_{n,=k}( 0L, REP ) \ LELP_{m,=l}( 0L, REP ).

Bizonyítás

(1) A bizonyítás az 5. állítás (1) pontjának bizonyításával teljesen megegyezik, azzal az apró kivétellel, hogy a szimuláló-rendszerbeli fiktív, a levezetésben soha részt nem vevő ágensek ( d, d, d) szabályok helyett ( d, d, d) → ( d, d, d) szabályokkal rendelkeznek.

(2) Ha R_{n,=k} = L(Σ, = l) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, REP) rendszerrel, akkor a 3. lemma miatt minden v ∈ L_{2} szóra és minden w⇒_{Σ}v lépésre w ∈ L_{1} teljesül. Nézzük az ilyen lépések során felhasznált olyan szabályokat, amelyek c betűt hoznak be.

• Ezek között nem lehet P_{E}-beli szabály, mert ekkor k-nál több c betű fordulhatna elő L(Σ, = l)-beli szavakban.

• Ha l ≥ 2, akkor nem létezhet két olyan ágens, amely ugyanazon c betűt be tudná hozni, mert ekkor két egyforma c betűt tartalmazó szót kaphatnánk. l = 1 pedig nem állhat, ha k ≥ 2, mert ekkor legfeljebb egy c betű fordulhatna elő az L_{2}-beli szavakban, ami nem igaz.

• Semelyik Σ-beli ágens sem hozhat be két különféle c betűt, mert ekkor nem tudnánk biztosítani Σ-ban azt, hogy a c betűk bármilyen kombinációban előfordulhassanak.

Az eddigiekből az következik, hogy ha R_{n,=k} = L(Σ, = l), akkor m ≥ n és l ≥ k is fennáll.

(3) Az L = { a^{k+2}, b^{k+2} } nyelvre L ∈ LELP_{n,=k}( 0L, REP ) áll, mert L = L(Σ, = k) a Σ = (V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP (0L, REP) rendszerrel, melyre:

• V_{E} = { a, b }

• P_{E} = { a → b, b → a }

• R_{i} = { ( a, a, a) → ( a, b, a) }, ha 1 ≤ i ≤ n

• w = a^{k+2}.

Másrészt k-nál több ágens nem tud helyettesíteni egyszerre az L-beli szavakon, tehát L ∉ LELP_{m,=l}( 0L, REP ), ha l > k.

Állítás 10 1 ≤ k ≤ n és 1 ≤ l ≤ m

1. • n ≤ m esetén LELP_{n,≤k}( 0L, REP ) ⊆ LELP_{m,≤k}( 0L, REP ).

• 1 ≤ n, m esetén LELP_{n,≤1}( 0L, REP ) = LELP_{m,≤1}( 0L, REP ).

2. Minden 2 ≤ k ≤ n és 1 ≤ l ≤ m esetén, ha m < n vagy l < k, akkor I_{n,≤k} ∈ LELP_{n,≤k}( 0L, REP ) \ LELP_{m,≤l}( 0L, REP ). (R_{n,≤k} definíciójáért lásd a 3.9. példát)

3. • Minden 1 ≤ k < n és 1 ≤ l ≤ m esetén, ha l > k, akkor I_{n,≤k} ∈ LELP_{n,≤k}( 0L, REP ) \ LELP_{m,≤l}( 0L, REP ).

• 1 ≤ n ≤ l ≤ m esetén LELP_{n,≤n}( 0L, REP ) ⊆ LELP_{m,≤l}( 0L, REP ).

Bizonyítás

(1) Pontosan úgy megy, mint az INS esetben, tehát lásd az 6. állítás bizonyítását, annyi különbség van csupán, hogy a fiktív, a levezetésben soha részt nem vevő ágensek ( d, d, d ) szabályok helyett ( d, d, d ) → ( d, d, d ) szabályokkal rendelkeznek. A bizonyítás további része szintén megegyezik az 6. állítás bizonyításával , ezért nem részletezem.

1. Bármely 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén I_{n,=k} ∈ LELP_{n,=k}( 0L, REP ) \ LELP_{m,≤l}( 0L, REP ).

2. Minden 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén létezik olyan L nyelv, melyre: L ∈ LELP_{m,≤l}( 0L, REP ) \ LELP_{n,=k}( 0L, REP ).

Bizonyítás

(1) Lásd a 7. állítás bizonyítását, az szó szerint alkalmazható erre az esetre is.

(2) Az L = { a, b } nyelv a keresett nyelv, az indoklás ugyanaz, mint a 7. állítás bizonyításánál.

A REP nyelvosztályok és az 0L nyelvek kapcsolatáról a következőket állítjuk:

Állítás 12

1. Minden 1 ≤ l ≤ m esetén 0L ⊂ LELP_{m,≤l}( 0L, REP ).

2. Minden 1 ≤ k ≤ n esetén 0L és LELP_{n,=k}( 0L, REP )

összehasonlíthatatlanok.

Bizonyítás Lásd a 8. állítás bizonyítását.

Összefoglalva az eddigieket:

Tétel 3 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén

1. • LELP_{m,=1}( 0L, REP ) = LELP_{n,=1}( 0L, REP ) bármely n, m ≥ 1 esetén,

• LELP_{n,=k}(0L, REP) ⊂ LELP_{m,=k}(0L, REP) ha k > 1 és m > n,

• különben az LELP_{n,=k}(0L, REP) és LELP_{m,=l}(0L, REP) nyelvosztályok összehasonlíthatatlanok.

2. • LELP_{m,≤1}( 0L, REP ) = LELP_{n,≤1}( 0L, REP ) bármely n, m ≥ 1 esetén,

• LELP_{n,≤k}(0L, REP) ⊂ LELP_{m,≤k}(0L, REP) ha k > 1 és m > n,

• LELP_{n,≤n}( 0L, REP ) ⊂ LELP_{m,≤l}( 0L, REP ) ha n ≤ l ≤ m és l ≠ n vagy l ≠ m,

• különben az LELP_{n,≤k}(0L, REP) és LELP_{m,≤l}(0L, REP) nyelvosztályok összehasonlíthatatlanok.

3. Az LELP_{n,=k}(0L, REP) és LELP_{m,≤l}(0L, REP) nyelvosztályok összehasonlíthatatlanok.

Bizonyítás A tétel állításai a 9., 10., 11. állítások közvetlen következményei.

A fejezetben bizonyított állítások azt mutatják, hogy az LELP_{,}( 0L, CF ), LELP ( 0L, INS ), LELP ( 0L, REP ) nyelvek hierarchiája igen hasonló.

A CF, INS és REP nyelvosztályok kapcsolata

Ezen fejezetben azt vizsgáljuk, hogy mi a kapcsolat az LELP ( 0L, CF ), az LELP ( 0L, INS ) és az LELP ( 0L, REP ) nyelvosztályok között. Vannak-e olyan nyelvek, melyeket például csak ELP ( 0L, CF ) rendszerrel lehet előállítani, de ELP (0L, INS) illetve ELP (0L, REP) rendszerrel nem? Erre és ehhez hasonló kérdésekre keresünk választ az 5. fejezetben.

Állítás 13 1 ≤ k ≤ n esetén L_{INS}(n, = k) ∈ LELP_{n,=k}( 0L, INS ) \ LELP ( 0L, CF )

Bizonyítás Először egy lemmát fogalmazunk meg, mely teljesen analóg az előző fejezet 1. lemmájával. A lemmában és a továbbiakban is fontos szerepet játszó L_{INS}(n, = k) és L_{INS}(n, ≤ k) nyelvek definíciójáért lásd a 3.7 példát.

Lemma 4 Ha L az { L_{INS}(n, = k), L_{INS}(n, ≤ k) | 1 ≤ k ≤ n } halmaz eleme, L_{1} = L ∩ { a_{1}, b_{1} }^{∗}, L_{2} = L ∩ { a_{2}, b_{2}, c_{1}, …, c_{n} }^{∗} és L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, CF ) rendszer esetén, akkor

1. v ∈ L_{2} és w⇒_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ}v esetén w ∈ L_{2} áll.

A lemma bizonyítása: Az 1. lemma bizonyításával analóg módon történik: Először azt lehet megmutatni, hogy ha v ∈ L_{2}, w⇒_{Σ}v és |v| > N = l max_{1≤i≤m}max_{(u→t)∈R_{i}}|t|+max_{b_{2}→t∈P_{E}}|t|+k max_{1≤i≤n}max_{(c_{i}→t)∈P_{E}}|t|, akkor w ∈ L_{1}. Ugyanúgy belátható az is, hogy ha v ∈ L_{1}, w⇒_{Σ}v és |v| > N′ = l max_{1≤i≤m}max_{(u→t)∈R_{i}}|t| + max_{b_{1}→t∈P_{E}}|t|, akkor w ∈ L_{2}. Innen pedig ugyanúgy fejezhető be a bizonyítás, mint az 1. lemma esetén.

Ha tehát L_{INS}(n, = k) = L(Σ, = l) vagy L_{INS}(n, = k) = L(Σ, ≤ l) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, CF ) rendszer és 1 ≤ l ≤ m esetén, akkor a fenti lemma értelmében minden v ∈ L_{2} szót csak L_{1}-beli szóból lehet levezetni Σ-ban. Nézzük, hogyan kerülhetnek c betűk egy L_{2}-beli szóba az utolsó lépés során:

• P_{E} nem tartalmazhat a_{1} → α c_{i}β alakú szabályt, ahol α, β ∈ (alphL_{2})^{∗} és 1 ≤ i ≤ n, mert akkor k-nál több c betű fordulna elő L(Σ)-beli szavakban.

• Minden i, 1 ≤ i ≤ n esetén lennie kell a_{1} → α c_{i}β szabálynak Σ-ban, valamilyen α, β ∈ (alphL_{2})^{∗} esetén, mert ha lenne olyan i, 1 ≤ i ≤ n, melyre c_{i}-t csak b_{1}-ből lehet levezetni, akkor ez a c_{i} nem fordulhatna elő bármilyen messze a szó elejétől ( hiszen b_{1} helye rögzített) .

• Tehát minden i, 1 ≤ i ≤ n esetén létezik a_{1} → α c_{i}β ágensszabály, valamely α, β ∈ (alphL_{2})^{∗}-val. Az ilyen szabályokban |α|_{b_{2}} = 0, különben egy hosszú L_{1}-beli szó utolsó a_{1} betűjére alkalmazva a fenti a_{1} → α c_{i}β ágensszabályt, az ágensek által nem érintett a_{1} betűkre pedig az a_{1} → u, u ∈ (alphL_{1})^{∗} környezetszabályt, olyan szót vezetnénk le, ahol a b betű nem a harmadik helyen áll.

• Így viszont, ha az a_{1} → α c_{i}β ágensszabályt egy L_{1}-beli szó első a_{1} betűjére alkalmazzuk, akkor olyan szót tudunk levezetni, melyben b betű előtt c betű áll, de ilyen szó nincsen L_{INS}(n, = k)-ban.

Ezzel a bizonyítást befejeztük.

A fenti állításban az L_{INS}(n, = k) nyelvnek csak olyan tulajdonságait használtuk, amelyek az L_{INS}(n, ≤ k) nyelvnek is megvannak, tehát L_{INS}(n, = k) helyett L_{INS}(n, ≤ k)-ra is kimondhatjuk az előző állítást; a bizonyítást pedig szó szerint átvehetjük a fenti állításból:

Állítás 14 1 ≤ k ≤ n esetén L_{INS}(n, ≤ k) ∈ LELP_{n,≤k}( 0L, INS ) \ LELP ( 0L, CF )

Láttuk, hogy bizonyos LELP (0L, INS) nyelveket nem lehet ELP (0L, CF ) rendszerrel generálni. Ez megfordítva is igaz:

Állítás 15 1 ≤ k ≤ n esetén L_{CF} (n, = k) ∈ LELP_{n,=k}( 0L, CF ) \ LELP ( 0L, INS )

Bizonyítás Most is egy lemmával kezdjük a bizonyítást. (Az L_{CF} (n, = k) és L_{CF} (n, ≤ k) nyelvek definíciójáért lásd a 3.4 . példát.)

Lemma 5 Ha L az { L_{CF} (n, = k), L_{CF} (n, ≤ k) | 1 ≤ k ≤ n } halmaz eleme, L_{1} = L ∩ { a_{1}, b_{1} }^{∗}, L_{2} = L ∩ { a_{2}, b_{2}, c_{1}, …, c_{n} }^{∗} és L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, INS ) rendszer esetén, akkor

1. v ∈ L_{2} és w⇒_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ}v esetén w ∈ L_{2} áll.

A lemma bizonyítása: Az eddigi lemmák bizonyításával analóg módon történik: Először azt lehet megmutatni, hogy ha v ∈ L_{2}, w⇒_{Σ}v és |v| > N = l max_{1≤i≤m}max_{(x,t,y)∈R_{i}}|t| + max_{+}k max_{1≤i≤n}max_{(c_{i}→t)∈P_{E}}|t|, akkor w ∈ L_{1}. Ez azért igaz, mert ekkor a w⇒_{Σ}v lépésben P_{E}-ből a_{2} → u, u ∈ (alphL_{2})^{+} vagy b_{2} → u′ u′ ∈ (alphL_{2})^{+} szabályt használtunk. Bármelyik eset is áll elő, nem lehet P_{E}-ben sem a_{2} → u, u ∈ (alphL_{1})^{+}, sem b_{2} → u′, u′ ∈ (alphL_{1})^{+} alakú szabály a vegyes indexű betűs szavak tilalma miatt. Tehát a kellően hosszú L_{1}-beli szavak levezetésére léteznie kell vagy a_{1} → u ∈ (alphL_{1})^{+}, vagy b_{1} → u ∈ (alphL_{1})^{+} alakú szabálynak P_{E}-ben (mert sem a_{2} → u ∈ (alphL_{1})^{+}, sem b_{2} → u′ ∈ (alphL_{1})^{+} nem létezhet) . Ha w ∈ L_{j}, (j = 1 vagy j = 2), akkor az L_{i}-beli (i ≠ j) szavak levezetése során létezik u⇒_{Σ}u′ lépés, ahol u ∈ L_{j}, u′ ∈ L_{i}. Létezik L_{j}-ben olyan u′′ szó, melyre u ⪯ u′′ és |u′′| > l; u′′-n az u⇒_{Σ}u′ során használt szabályokat és a létező a_{j} → u, u ∈ (alphL_{j})^{+} vagy b_{j} → u, u ∈ (alphL_{j})^{+} környezetszabályokat végrehajtva vegyes indexű betűket tartalmazó szót vezethetünk le Σ-ban. Ez pedig nem lehetséges. Ha v ∈ L_{1}, w⇒_{Σ}v és |v| > N′ = l max_{1≤i≤m}max_{(x,t,y)∈R_{i}}|v|, akkor ugyanígy belátható, hogy w ∈ L_{2}. Innen pedig a szokásos módon fejezhető be a bizonyítás. (Lásd az 1. lemma bizonyítását.) Tehát, ha L_{CF} (n, = k) = L(Σ, = l) vagy L_{CF} (n, = k) = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w ) ∈ ELP ( 0L, INS ) rendszer esetén, akkor L_{2}- beli szavakat csak L_{1}-beliekből lehet Σ-ban levezetni. Először megvizsgáljuk, hogy P_{E}-ben milyen szabályok lehetnek, amelyeket a levezetés során arra használhatunk, hogy L_{1}-beli szavakból L_{2}-beli szavakat nyerjünk.

Az összes ilyen szabály a_{1} → α, α ∈ (alphL_{2})^{∗} illetve b_{1} → α, α ∈ (alphL_{2})^{∗} alakú.

1. Sem α, sem β nem tartalmazhat c betűt, különben k-nál több c betű fordulhatna elő L(Σ)-beli szavakban.

2. Sem α, sem β nem tartalmazhat a_{2} és b_{2} betűt egyszerre, különben olyan szavakat lehetne levezetni Σ-ban, amelyekben a_{2}xb_{2}ya_{2} részszó szerepel, valami x, y ∈ (alphL_{2})^{∗} esetén.

3. α nem lehet b_{2}^{i} alakú i ≥ 1 esetén, β pedig nem lehet a_{2}^{j} alakú j ≥ 1 esetén, mert ezekben az esetekben b_{2} állhatna a szó elején, vagy a_{2} állhatna a szó végén, de ilyen szavak L_{CF} (n, = k)-ban nincsenek.

4. Tehát α = a_{2}^{i} és β = b_{2}^{j} lehet csak . Lennie kell viszont olyan szabályoknak P_{E}-ben, ahol i ≥ 1 és j ≥ 1, különben nem lehetne bármilyen sok a_{2} illetve b_{2} betűt tartalmazó szavakat levezetni Σ-ban.

Láttuk, hogy csak az ágensek hozhatnak be c_{i} betűket a levezetés során. Azok a szabályok, amik következtében a c_{i} betűk megjelennek beszúrószabályok, tehát az alábbi öt alak valamelyikébe írhatók:

1. ( b_{1}^{i_{1}}a_{1}^{i_{1}}, γ c_{i}δ, a_{1}^{i_{3}} )

2. ( b_{1}^{i_{1}}, γ c_{i}δ, b_{1}^{i_{2}} )

3. ( b_{1}^{i_{1}}, γ c_{i}δ, b_{1}^{i_{2}}a_{1}^{i_{3}} )

4. ( a_{1}^{i_{1}}, γ c_{i}δ, a_{1}^{i_{2}} )

5. ( b_{1}^{i_{1}}, γ c_{i}δ, a_{1}^{i_{2}} )

ahol i_{1}, i_{2}, i_{3} ≥ 1 és γ, δ ∈ (alphL_{2})^{∗}. A (2),(3) és (5) esetben c_{i} betű b betű előtt is szerepelhetne, ha a létező b_{1} → b_{2}^{j}, j ≥ 1 P_{E}-beli szabályt használjuk. (Az (5) esetben azért, mert közvetlenül a szó elején lévő i_{1} darab b_{1} betű után is beszúrhatjuk a γ c_{i}δ szót.) Így minden c_{i}-t behozó szabálynak (1) vagy (4) alakúnak kell lennie, de ekkor P_{E}-nek a_{1} → λ szabályt kell tartalmaznia, különben c_{i} nem fordulhatna elő közvetlenül a b_{2} betűk után. Ha viszont létezik a_{1} → λ szabály P_{E}-ben, akkor egy elég hosszú L_{1}-beli szóból olyan L_{2}-beli szót lehetne levezetni Σ-ban (a létező P_{E}-beli b_{1} → b_{2}^{j}, j ≥ 1 szabállyal), amelyben sok b_{2} áll a szó elején, de amely csak kevés a_{2}-t (maximum annyit, amennyit az l darab ágens elő tud állítani) tartalmaz.

Ez pedig nem lehet, hiszen az L_{CF} (n, = k)-beli szavakban az a betűk száma legalább a fele a b betűk számának.

Jól látható, hogy a bizonyítás során az L_{CF} (n, = k) nyelvnek csak olyan tulajdonságait használtuk, amelyek az L_{CF} (n, ≤ k) nyelvnek is megvannak, tehát L_{CF} (n, = k) helyett L_{CF} (n, ≤ k)-ra is kimondhatjuk az előző állítást; a bizonyítás pedig szó szerint ugyanaz, mint az előbb:

Állítás 16 1 ≤ k ≤ n esetén L_{CF} (n, ≤ k) ∈ LELP_{n,≤k}( 0L, CF ) \ LELP ( 0L, INS ).

Most az LELP (0L, CF) és az LELP (0L, REP) nyelvosztályok kapcsolatát vizsgáljuk meg. Az R_{n,=k} és R_{n,≤k} nyelvek definíciójáért lásd a 3.9. példát, az L_{R}(n, = 1) és L_{R}(n, ≤ 1) nyelvek definíciójáért lásd a 3.10. példát.

Állítás 17

1. 2 ≤ k ≤ n esetén R_{n,=k} ∈ LELP_{n,=k}( 0L, REP ) \ LELP ( 0L, CF )

2. 1 = k ≤ n esetén L_{R}(n, = 1) ∈ LELP_{n,=1}( 0L, REP ) \ LELP ( 0L, CF )

Bizonyítás

(1) A bizonyítás a szokásos lemma alkalmazásával történik::

Lemma 6 Ha L az { R_{n,=k}, R_{n,≤k} | 1 ≤ k ≤ n } halmaz eleme, L_{1} = L ∩ { a_{1} }^{∗}, L_{2} = L ∩ { a_{2}, c_{1}, …, c_{n} }^{∗} és L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, CF ) rendszer esetén, akkor

1. v ∈ L_{2} és w⇒_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ}v esetén w ∈ L_{2} áll.

A lemma bizonyítása: Ugyanúgy történik, mint eddig, N = l max_{1≤i≤m}max_{(u→t)∈R_{i}}|t| + k max_{1≤i≤n}max_{(c_{i}→t)∈P_{E}}|t| és N′ = l max_{1≤i≤m}max_{(u→t)∈R_{i}}|t| választással.

Tehát, ha R_{n,=k} = L(Σ, = l) vagy R_{n,=k} = L(Σ, ≤ l) áll valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, CF) rendszer esetén, akkor L_{2}-beli szavakat csak L_{1}-beliekből lehet Σ-ban levezetni. A c betűket csak az ágensek hozhatják be, különben k-nál több c betű lehetne L(Σ)-beli szavakban. Tehát a c betűket csak a_{1} → αc_{i}β alakú ágensszabályok hozhatják be, ahol α, β ∈ (alphL_{2})^{∗}.

1. Mivel k ≥ 2, ezért létezik két különböző c betű, c_{1} és c_{2} V_{E}-ben és ezek bármilyen messze előfordulhatnak egymástól az L_{2}-beli szavakban. Így l = 1 nem lehetséges, mert ekkor c_{1} és c_{2} minden együttes előfordulására külön ágensszabály kellene Σ-ban, de az csak véges sokat tartalmaz. Ha pedig l ≥ 2, akkor minden egyes c_{i} betűre (1 ≤ i ≤ n) csak egy ágens lehet, amely őt behozza, különben olyan szavak lennének L(Σ)- ban, melyekben egynél több c_{i} fordul elő.

2. Nem lehetséges, hogy valamely R_{i} ágens (1 ≤ i ≤ m) kétféle c betűt is be tudjon hozni, mert ekkor ez a két betű nem fordulhatna elő egyszerre, bármilyen messze egymástól.

Így egy a_{1} → αc_{i}β ágensszabályban (1 ≤ i ≤ m) α nem tartalmazhat c betűt, tehát α = a_{1}^{j} alakú, j ≥ 0 -val. De j = 0 nem állhat, mert ekkor a c_{i} betűt szó elejére is behozhatná a szabály, de R_{n,=k}-ban nincsenek ilyen szavak. Tehát minden ilyen szabály a_{1} → a_{1}^{j}c_{i}β, j ≥ 1 és β ∈ (alphL_{2})^{∗} jelöléssel. De ekkor az xc_{j}c_{i}y, x, y ∈ (alphL_{2})^{∗} alakú szavakat nem lehet levezetni Σban.

(2) A (2) állítás esetén is fennáll a szokásos lemma.

Lemma 7 Ha L az { L_{R}(n, = 1), L_{R}(n, ≤ 1) | 1 ≤ k ≤ n } halmaz eleme, L_{1} = L ∩ { a_{1}, b_{1} }^{∗}, L_{2} = L ∩ { a_{2}, b_{2}, c_{1}, …, c_{n} }^{∗} és L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, CF ) rendszer esetén, akkor

1. v ∈ L_{2} és w⇒_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ}v esetén w ∈ L_{2} áll.

A lemma bizonyítása: Ugyanúgy történik, mint eddig, N = l max_{1≤i≤m}max_{(u→t)∈R_{i}}|t| + k max_{1≤i≤n}max_{(c_{i}→t)∈P_{E}}|t| és N′ = l max_{1≤i≤m}max_{(u→t)∈R_{i}}|t| választással.

A fenti lemma értelmében, ha L_{R}(n, = 1) = L(Σ, = l) vagy L_{R}(n, = 1) = L(Σ, ≤ l) valamely Σ = (V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP (0L, CF) rendszer esetén, akkor L_{2}-beli szavakat csak L_{1}-beliekből lehet Σ-ban levezetni.

Először megvizsgáljuk, hogy P_{E}-ben milyen szabályok lehetnek, amelyeket a levezetés során arra használhatunk, hogy L_{1}-beli szavakból L_{2}-beli szavakat nyerjünk. Az összes ilyen szabály a_{1} → α ∈ (alphL_{2})^{∗}, illetve b_{1} → α ∈ (alphL_{2})^{∗} alakú.

1. Sem α, sem β nem tartalmazhat c betűt, különben k-nál több c betű fordulhatna elő L(Σ)-beli szavakban.

2. Sem α, sem β nem tartalmazhat a_{2} és b_{2} betűt egyszerre, különben olyan szavakat lehetne levezetni Σ-ban, amelyekben a_{2}xb_{2}ya_{2} részszó szerepel, valami x, y ∈ (alphL_{2})^{∗} esetén.

3. α nem lehet b_{2}^{i} alakú i ≥ 1 esetén, β pedig nem lehet a_{2}^{j} alakú j ≥ 1 esetén, mert ezekben az esetekben b_{2} állhatna a szó végén, vagy a_{2} állhatna a szó elején, de ilyen szavak L_{R}(n, = 1)-ben nincsenek.

4. Tehát α = a_{2}^{i} és β = b_{2}^{j} lehet csak . Lennie kell viszont olyan szabályoknak P_{E}-ben, ahol i ≥ 1 és j ≥ 1, különben nem lehetne bármilyen sok a_{2} illetve b_{2} betűt tartalmazó szót levezetni Σ-ban.

Az ágensek a_{1} → αc_{i}β vagy b_{1} → αc_{i}β szabállyal hozhatnak be c_{i} betűt, ahol α, β ∈ (alphL_{2})^{∗}. De a b_{1} → αc_{i}β szabályt egy L_{1}-beli szó első b_{1} betűjére alkalmazva, az ágensek által nem érintett b_{1} betűkre pedig a b_{1} → b_{2}^{j}, j ≥ 1 P_{E}-beli szabályt végrehajtva, c betű kerül b betű elé; ha pedig az a_{1} → αc_{i}β ágensszabályt alkalmazom egy L_{1}-beli szó utolsó a_{1} betűjére, és a P_{E}-beli a_{1} → a_{2}^{j}, j ≥ 1-t is használom, akkor a betű kerül c betű elé. Mindkét esetben olyan szót kapunk L(Σ)-ban, ami nem szerepel L_{R}(n, = 1)-ben.

Ebben a bizonyításban sem használtuk az R_{n,=k} illetve az L_{R}(n, = 1) nyelvek semmilyen olyan tulajdonságát, melyekkel a R_{n,≤k} illetve az L_{R}(n, ≤ 1) nyelvek ne rendelkeznének. Ezért az előző bizonyítást szó szerint elmondhatjuk a következő állítás bizonyítására is:

Állítás 18

1. 2 ≤ k ≤ n esetén R_{n,≤k} ∈ LELP_{n,≤k}( 0L, REP ) \ LELP ( 0L, CF )

2. 1 = k ≤ n esetén L_{R}(n, ≤ 1) ∈ LELP_{n,≤1}( 0L, REP ) \ LELP ( 0L, CF )

Tehát minden 1 ≤ k ≤ n esetén vannak LELP ( 0L, REP ) nyelvek, melyeket nem lehet ELP ( 0L, CF ) rendszerrel előállítani. Ebben az esetben is igaz a megfordítás is:

Állítás 19 Minden 1 ≤ k ≤ n esetén létezik olyan L nyelv, melyre L ∈ LELP_{n,=k}( 0L, CF ) \ LELP ( 0L, REP )

Bizonyítás Legyen Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w ) ∈ ELP ( 0L, CF ) olyan rendszer, melyre

• V_{E} = { a_{1}, a_{2}, c_{1}, …, c_{n} }

• P_{E} = { a_{1} → a_{2}, a_{2} → a_{1} }∪_{1≤i≤n}{ c_{i} → a_{2} }

• R_{i} = { a_{1} → c_{i}^{2}, c_{i} → a_{2} }, ha 1 ≤ i ≤ n

• w = a_{1}^{k}.

Ekkor

L = L(Σ, = k) = \{ a_{1}^{tk} | t ≥ 1 \} ∪ \{ [c_{i_{1}}^{2}, …, c_{i_{k}}^{2}, \underbrace{a_{2}^{2}, …, a_{2}^{2}}_{s k}]^{P} | s ≥ 1 \}

L′ = L(Σ, ≤ k) == { a_{1}^{k+s_{1}+...+s_{t}} | t ≥ 1, k ≥ s_{i} ≥ 0, t ≥ i ≥ 1 }∪

∪ \{ [c_{i_{1}}^{2}, …, c_{i_{s}}^{2}, \underbrace{a_{2}^{2}, …, a_{2}^{2}}_{k+s_{1}...+s_{t}}]^{P} | t ≥ 1, k ≥ s_{i} ≥ 0, t ≥ i ≥ 1 \}

ahol s_{i} jelöli azt, hogy a levezetés 2i − 1-edik lépésében hány ágens dolgozott Σ-ban. Mind L-nek, mind L′-nek az a fontos tulajdonsága van, hogy szavaikban a c_{i} betűk csak c_{i}^{2} alakban fordulnak elő. Azt állítom, hogy az így definiált nyelvre L ∉ LELP ( 0L, REP ) áll. A szokásos lemma:

Lemma 8 Ha L vagy L′ ( az előbb definiáltak) előáll L(Σ′, = l) vagy L(Σ′, ≤ l) alakban valamely Σ′ = (V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′) ∈ ELP (0L, INS) rendszer esetén, és L_{1} = L ∩ { a_{1}, b_{1} }^{∗}, illetve L_{2} = L ∩ { a_{2}, b_{2}, c_{1}, …, c_{n} }^{∗} , akkor

1. v ∈ L_{2} és w⇒_{Σ′}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ′}v esetén w ∈ L_{2} áll.

A lemma bizonyítása: Ugyanúgy megy, ahogy az eddigi lemmáké. Most az N = l + 2k max_{1≤i≤n}max_{(c_{i}→t)∈P_{E}′}|t| illetve az N′ = l választás jó.

Ha tehát L előáll L(Σ′, = l) vagy L(Σ′, ≤ l) alakban valamely Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) ∈ ELP ( 0L, INS ) rendszer esetén, akkor L_{2}-beli szavakat csak L_{1}-beliekből lehet levezetni Σ′-ban.

1. Csak ágensek hozhatnak be c betűt, különben 2k-nál több c betű is előfordulhatna L(Σ′)-beli szavakban.

2. Mivel Σ′ ∈ ELP ( 0L, REP ), ezért minden ágens maximum egy darab új betűt, tehát maximum egy c betűt hozhat be. Ezért minden i, 1 ≤ i ≤ n esetére legalább két ágens kell, amelyek a levezetés során a c_{i} betűt behozzák és l ≥ 2 is szükséges. Ezek az ágensszabályok ( a_{1}, a_{1}, a_{1} ) → ( a_{1}, c_{i}, a_{1} ) alakúak lehetnek. De ekkor a két c_{i} betű szeparáltan is előfordulhat, azaz xc_{i}yc_{i}z alakú szót lehet levezetni Σ′-ben, valami x, z ∈ (alphL_{2})^{∗}, y ∈ (alphL_{2})^{+} esetén.

Ezzel beláttuk, hogy a feltételünk hamis volt.

Jól látható, hogy az L nyelvnek csak azokat a tulajdonságait használtuk, amelyekkel az L′ nyelv is rendelkezik, így kimondhatjuk a következő állítást, melynek bizonyítása teljesen megegyezik az előbbi állítás bizonyításával:

Állítás 20 Minden 1 ≤ k ≤ n esetén az előbb definiált L′ nyelv olyan, melyre L′ ∈ LELP_{n,≤k}( 0L, CF ) \ LELP ( 0L, REP )

Nincs más hátra, mint az, hogy megvizsgáljuk az LELP ( 0L, REP ) és LELP ( 0L, INS ) nyelvosztályok viszonyát.

Állítás 21 1 ≤ k ≤ n esetén L_{INS}(n, = k) ∈ LELP_{n,=k}( 0L, INS ) \ LELP ( 0L, REP )

Bizonyítás A szokásos lemma alkalmazásával történik.

Lemma 9 Ha L ∈ { L_{INS}(n, = k), L_{INS}(n, ≤ k) | 1 ≤ k ≤ n } , L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, REP ) rendszer esetén, és L_{1} = L ∩ { a_{1}, b_{1} }^{∗}, illetve L_{2} = L ∩ { a_{2}, b_{2}, c_{1}, …, c_{n} }^{∗} , akkor

1. v ∈ L_{2} és w⇒_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ}v esetén w ∈ L_{2} áll.

A lemma bizonyítása: Ugyanúgy megy, ahogy az eddigi lemmáké. Most az N = l + k max_{1≤i≤n}max_{(c_{i}→t)∈P_{E}}|t|, illetve az N′ = l választás megfelelő.

Ha tehát L_{INS}(n, = k) előáll L(Σ, = l) vagy L(Σ, ≤ l) alakban valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w ) ∈ ELP ( 0L, REP ) rendszer esetén, akkor L_{2}-beli szavakat csak L_{1}-beliekből lehet levezetni Σ-ban.

1. Csak ágensek hozhatnak be c betűt, különben k-nál több c betű is előfordulhatna L(Σ)-beli szavakban.

2. Ezek az ágensszabályok a következő alakok egyikébe írhatók:

• ( a_{1}, a_{1}, a_{1} ) → ( a_{1}, c_{i}, a_{1} )

• ( a_{1}, b_{1}, b_{1} ) → ( a_{1}, c_{i}, b_{1} )

• ( a_{1}, a_{1}, b_{1} ) → ( a_{1}, c_{i}, b_{1} )

• ( b_{1}, a_{1}, a_{1} ) → ( b_{1}, c_{i}, a_{1} )

Az első eset nem lehetséges, mert ekkor az L_{1}-beli szókezdő a_{1}^{3}-re alkalmazva, c betű kerülne b betű elé, hiszen a szókezdő a_{1} betűn ágens nem tud hatni, a környezet pedig nem írhatja át b betűt tartalmazó szóvá, mert ha ilyen szabály lenne P_{E}-ben, akkor egynél több b betűt tartalmazó szó lenne L(Σ)-ban. Tehát csak a másik három ágensszabály lehetséges, de ekkor c_{i} nem fordulhatna elő bármilyen messze a szó elejétől.

Ezzel ellentmondásra jutottunk.

Ugyanígy lehet érvelni a következő állítás bizonyítására is, mivel az L_{INS}(n, = k) nyelvnek csak azokat a tulajdonságait használtuk ki, amelyekkel az L_{INS}(n, = k) nyelv is rendelkezik.

Állítás 22 1 ≤ k ≤ n esetén L_{INS}(n, ≤ k) ∈ LELP_{n,≤k}( 0L, INS ) \ LELP ( 0L, REP )

Az is igaz, hogy vannak olyan LELP (0L, REP) nyelvek, melyeket ELP (0L, INS) rendszerrel nem lehet előállítani.

Állítás 23 1 ≤ k ≤ n esetén létezik olyan L_{REP} (n, = k) nyelv, melyre L_{REP} (n, = k) ∈ LELP_{n,=k}( 0L, REP ) \ LELP ( 0L, INS ).

Bizonyítás Először azt mutatjuk meg, hogy a 3.10. példában definiált L_{R}(1, = 1) nyelvre teljesül, hogy L_{R}(1, = 1) ∈ LELP_{1,=1}( 0L, REP ) \ LELP ( 0L, INS ) (Ez egyben az állítás bizonyítása is lesz n = k = 1 esetén, L_{REP} (1, = 1) = L_{R}(1, = 1) választással.) Vegyük a szokásos lemmát:

Lemma 10 Ha L ∈ { L_{R}(1, = 1), L_{R}(1, ≤ 1) | 1 ≤ n } , L = L(Σ, = l) vagy L = L(Σ, ≤ l) valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w) ∈ ELP ( 0L, INS ) rendszer esetén, és L_{1} = L ∩ { a_{1}, b_{1} }^{∗}, illetve L_{2} = L ∩ { a_{2}, b_{2}, c_{1}, …, c_{n} }^{∗}, akkor

1. v ∈ L_{2} és w⇒_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒_{Σ}v esetén w ∈ L_{2} áll.

A lemma bizonyítása: Ugyanúgy történik, ahogy az eddigi lemmáké. Most az N = l max_{1≤i≤m}max_{(x,t,y)∈R_{i}}|t| + k max_{1≤i≤n}max_{(c_{i}→t)∈P_{E}}|t| illetve az N′ = l max_{1≤i≤m}max_{(x,t,y)∈R_{i}}|t| választás megfelelő.

Ha tehát L_{R}(1, = 1) előáll L(Σ, = l) vagy L(Σ, ≤ l) alakban valamely Σ = ( V_{E}, P_{E}, R_{1}, …, R_{m}, w ) ∈ ELP ( 0L, INS ) rendszer esetén, akkor L_{2}- beli szavakat csak L_{1}-beliekből lehet levezetni Σ-ban. Először megvizsgáljuk, hogy P_{E}-ben milyen szabályok lehetnek, amelyeket a levezetés során arra használhatunk, hogy L_{1}-beli szavakból L_{2}-beli szavakat nyerjünk. Az összes ilyen szabály a_{1} → α ∈ (alphL_{2})^{∗} illetve b_{1} → α ∈ (alphL_{2})^{∗} alakú.

1. Sem α, sem β nem tartalmazhat c_{1} betűt, különben k-nál több c_{1} betű fordulhatna elő L(Σ)-beli szavakban.

2. Sem α, sem β nem tartalmazhat a_{2} és b_{2} betűt egyszerre, különben olyan szavakat lehetne levezetni Σ-ban, amelyekben a_{2}xb_{2}ya_{2} részszó szerepel, valamilyen x, y ∈ (alphL_{2})^{∗} esetén.

3. α nem lehet b_{2}^{i} alakú i ≥ 1 esetén, β pedig nem lehet a_{2}^{j} alakú j ≥ 1 esetén, mert ezekben az esetekben b_{2} állhatna a szó végén, vagy a_{2} állhatna a szó elején, de ilyen szavak L_{R}(1, = 1)-ben nincsenek.

4. Tehát α = a_{2}^{i} és β = b_{2}^{j} lehet csak . Lennie kell viszont olyan szabályoknak P_{E}-ben, ahol i ≥ 1 és j ≥ 1, különben nem lehetne bármilyen sok a_{2}, illetve b_{2} betűt tartalmazó szavakat levezetni Σ-ban.

Azok a szabályok, melyekkel az ágensek a c_{1} betűt behozhatják, az alábbi alakok egyikébe írhatók:

• ( a_{1}^{i_{1}}, γc_{1}δ, a_{1}^{i_{2}} )

• ( b_{1}^{i_{1}}, γc_{1}δ, a_{1}^{i_{2}} )

• ( b_{1}^{i_{1}}, γc_{1}δ, b_{1}^{i_{2}} )

• ( b_{1}^{i_{1}}a_{1}^{i_{2}}, γc_{1}δ, a_{1}^{i_{3}} )

• ( b_{1}^{i_{1}}, γc_{1}δ, b_{1}^{i_{2}}a_{1}^{i_{3}} )

ahol i_{1}, i_{2}, i_{3} ≥ 1 és 1 ≤ i ≤ n. A második szabálycsoport kivételével mindegyik fenti alak lehetetlen, mert ekkor c_{1} betű állhatna a illetve b betűk között ( használva a környezet a_{1} → a_{2}^{i} illetve b_{1} → b_{2}^{i} szabályait , ahol i, j ≥ 1) . De a második szabály lehetővé teszi, hogy az első i_{1} darab b_{1} után szúrjuk be a γc_{1}δ szót, tehát a c_{i} betű ekkor is b betűk között szerepel. Ilyen szó pedig nincsen L_{R}(1, = 1)-ben, azaz ellentmondásra jutottunk.

Az L_{R}(1, = 1) nyelv segítségével és mintájára definiáljuk az L_{REP} (n, = k) nyelvet 1 ≤ k ≤ n esetére a következőképpen: Legyen Σ = (V_{E}, P_{E}, R_{1}, …, R_{n}, w) ∈ ELP (0L, REP) az a rendszer, melyre:

• V_{E} = { a_{1}^{(i)}, a_{2}^{(i)}, b_{1}^{(i)}, b_{2}^{(i)}, c^{(i)}, …, c^{(i)} | 1 ≤ i ≤ n }

• P_{E} = { c^{(i)} → a_{1}^{(i)} | 1 ≤ i ≤ n } ∪ ∪ { a_{1}^{(i)} → a_{2}^{(i)}^{2}, a_{2}^{(i)} → a_{1}^{(i)}^{2}, b_{1}^{(i)} → b_{2}^{(i)}^{2}, b_{2}^{(i)} → b_{1}^{(i)}^{2} | 1 ≤ i ≤ n }

• R_{i} = { (b_{1}^{(i)}, a_{1}^{(i)}, a_{1}^{(i)}) → (b_{1}^{(i)}, c^{(i)}, a_{1}^{(i)}) }∪ ∪{ (b_{2}^{(i)}, c^{(i)}, a_{2}^{(i)}) → (b_{2}^{(i)}, a_{2}^{(i)}, a_{2}^{(i)}) }, ha 1 ≤ i ≤ n

• w = b_{1}^{(1)}a_{1}^{(1)}a_{1}^{(1)}b_{1}^{(2)}a_{1}^{(2)}a_{1}^{(2)} … b_{1}^{(n)}a_{1}^{(n)}a_{1}^{(n)}.

Ekkor az L_{REP} (n, = k) = L(Σ, = k) nyelv olyan, hogy szavait két csoportba lehet osztani, az első csoport elemei az alábbi halmazból kerülnek ki:

{[b_{1}^{(1)}]^{4^{t}}a_{1}^{(1)}[a_{1}^{(1)}]^{f(s_{1}^{(1)},...,s_{t}^{(1)})} … [b_{1}^{(n)}]^{4^{t}}a_{1}^{(n)}[a_{1}^{(n)}]^{f(s_{1}^{(n)},...,s_{t}^{(n)})}|0 ≥ t, 0 ≤ s_{r}^{(i)} ≤ 1}

ahol f(s_{1}^{(i)}, …, s_{t}^{(i)}) = 4^{t} + 3∑_{r=1}^{t}4^{t−r}s_{r}^{(i)}, s_{r}^{(i)} = 1, ha az i-edik ágens a 2r − 1-edik lépésben nem dolgozott, különben s_{r}^{(i)} = 0. A fenti halmazból azok a szavak tartoznak a generált L(Σ, = k) nyelvbe, ahol minden 1 ≤ i ≤ t esetén ∑_{l=1}^{n}s_{i}^{(l)} = n − k teljesül. A másik csoportba ugyanilyen felépítésű szavak tartoznak, csak a 4^{t} kitevő helyett 2 4^{t} , és k helyen a b betűk után következő a_{1}^{(i)} helyett c^{(i)} irandó. A generált nyelvbe itt is azok a szavak tartoznak bele, ahol minden 1 ≤ i ≤ t esetén ∑_{l=1}^{n}s_{i}^{(l)} = n − k teljesül. Úgy érthetjük meg legjobban a generált nyelvet, ha úgy gondolunk rá, mint egy olyan nyelvre, amit n darab, diszjunkt ábécéjű L_{R}(1, = 1) nyelv megfelelő szavainak egymás után írásával kaptunk. Az L_{REP} (n, ≤ k) = L(Σ, ≤ k) nyelv szavai teljesen hasonlók a fenti nyelv szavaihoz, azzal a különbséggel, hogy ebbben az esetben az első csoport és a második csoport elemeire is a ∑_{l=1}^{n}s_{i}^{(l)} ≥ n − k egyenlőtlenség teljesül, és a második csoport elemeiben nem k, hanem ≤ k helyen áll c betű. Mindkét nyelv azzal a fontos tulajdonsággal rendelkezik (és ez világosan látható, a bonyolult konstrukció ellenére is), hogy a c betűk csak közvetlenül a megfelelő b és a betűk határán helyezkedhetnek el. Azt állítjuk, hogy az így definiált nyelvekre: L_{REP} (n, = k) ∈ LELP_{n,=k}( 0L, REP ) \ LELP ( 0L, INS ) teljesül. A szokásos lemma:

Lemma 11 Ha L ∈ { L_{REP} (n, = k), L_{REP} (n, ≤ k) | 1 ≤ k ≤ n }, L = L(Σ, = l) vagy L = L(Σ′, ≤ l) valamely Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) ∈ ELP ( 0L, INS ) rendszer esetén, és L_{1} = L ∩ { a_{1}^{(i)}, b_{1}^{(i)} | 1 ≤ i ≤ n }^{∗}, illetve L_{2} = L ∩ { a_{2}^{(i)}, b_{2}^{(i)}, c_{1}^{(i)}, …, c_{n}^{(i)} | 1 ≤ i ≤ n }^{∗}, akkor

1. v ∈ L_{2} és w⇒′_{Σ}v esetén w ∈ L_{1} is áll,

2. v ∈ L_{1} és w⇒′_{Σ}v esetén w ∈ L_{2} áll.

A lemma bizonyítása: Az eddigiekkel analóg módon történik, azért részletezzük mégis, mert a kettős indexezés miatt kissé bonyolultabb a megszokottnál. Először azt mutatjuk meg, hogy ha v ∈ L_{2}, w⇒_{Σ′}v és |v| > N = l max_{1≤i≤m}max_{(x,t,y)∈R_{i}}|t| + k max_{1≤i≤n}max_{(c^{(i)}→t)∈P_{E}}|t|, akkor w ∈ L_{1}. Tegyük fel, hogy létezik v ∈ L_{2}, amelyre |v| > N, w⇒_{Σ}v, de w ∈ L_{2}. Mivel |v| > N, ezért a w⇒_{Σ′}v lépésben P_{E}′-ből a_{2}^{(i)} → u, u ∈ alphL_{2}^{+} vagy b_{2}^{(i)} → u, u ∈ alphL_{2}^{+} alakú szabályt is alkalmaztunk (különben |v| ≤ N állna). Így viszont P_{E}′ nem tartalmazhat sem a_{2}^{(i)} → u′, u′ ∈ alphL_{1}^{+} sem b_{2}^{(i)} → u, u ∈ alphL_{1}^{+} alakú szabályt, semmilyen 1 ≤ i ≤ n esetén sem, mert ekkor vegyes alsó indexű betűket tartalmazó szavak is előfordulnának L(Σ′, = l)- ben. Mivel L_{1}-ben bármilyen hosszú szavak előfordulnak, P_{E}′-nek tartalmaznia kell a_{1}^{(i)} → u, u ∈ alphL_{1}^{+} vagy b_{1}^{(i)} → u, u ∈ alphL_{1}^{+} alakú szabályt valamely 1 ≤ i ≤ n esetén (különben az L_{1}-beli szavak hossza maximálva lenne). Legyen w ∈ L_{j}, j = 1 vagy j = 2 esetén. Ekkor egy L_{i}-beli szó Σ′-beli levezetése során (ha i ≠ j) létezik olyan w_{1}⇒_{Σ′}w_{2} lépés, amikor w_{1} ∈ L_{j} és w_{2} ∈ L_{i}. Ebben a lépésben csupa (j) → (i) alakú szabályt használtunk (azaz csupa u_{1} → u_{2} szabályt, ahol u_{1} ∈ alphL_{j}^{+} és u_{2} ∈ alphL_{i}^{+}). De ekkor vegyes alsó indexű betűket tartalmazó szót lehetne levezetni a P_{E}′-beli a_{1}^{(i)} → u, u ∈ alphL_{1}^{+} vagy b_{1}^{(i)} → u, u ∈ alphL_{1}^{+} alakú és a fenti lépés során használt szabályok kombinálásával. Ezzel a részállítás bizonyítását befejeztük.. Ugyanezt mondhatjuk el N′ = l max_{1≤i≤m}max_{(x,t,y)∈R_{i}}|t| jelöléssel a fordított esetben, innen pedig a szokásos módon fejezhető be a lemma bizonyítása.

Ezek után tehát, ha L_{REP} (n, = k) előáll L(Σ′, = l) vagy L(Σ′, ≤ l) alakban valamely Σ′ = ( V_{E}′, P_{E}′, R_{1}′, …, R_{m}′, w′ ) ∈ ELP ( 0L, INS ) rendszer esetén, akkor L_{2}-beli szavakat csak L_{1}-beliekből lehet levezetni Σ′-ben. Vizsgáljuk a Σ′ rendszert, nézzük P_{E}′ milyen szabályokat tartalmazhat:

1. A környezet a_{1}^{(i)}-t és b_{1}^{(i)}-t csak { a_{2}^{(i)}, b_{2}^{(i)}, c^{(i)} } feletti szóvá írhatja újra ( minden 1 ≤ i ≤ n esetén). Azaz, ha (a_{1}^{(i)} → α) ∈ P_{E}′ vagy (b_{1}^{(i)} → β) ∈ P_{E}′ akkor α, β ∈ { a_{2}^{(i)}, b_{2}^{(i)}, c^{(i)} } áll. Ez a következők miatt igaz:

• Sem α sem β nem tartalmazhat két, különböző felső indexű betűt egyszerre, mert ekkor olyan szót lehetne levezetni L(Σ′)-ben, amely szóban keverten fordulnak elő a felső indexek.

• Az sem állhat elő, hogy α vagy β {a_{2}^{(j)}, b_{2}^{(j)}, c^{(j)}} és {a_{2}^{(t)}, b_{2}^{(t)}, c^{(t)}} (j ≠ t) feletti szó is lehessen, (azaz, hogy kétféle felső indexű szót is le lehessen vezetni a_{1}^{(i)}-ből illetve b_{1}^{(i)}-ből), mert ekkor is lennének kevert felső indexű szavak a Σ′ által generált nyelvben.

• Sem α, sem β nem tartalmazhat a_{2}^{(j)} és b_{2}^{(t)} betűt egyszerre semmilyen j, t, 1 ≤ j, t ≤ n felső indexekre, különben olyan szavakat lehetne levezetni Σ′-ben, amelyekben a_{2}^{(j)}xb_{2}^{(t)}ya_{2}^{(j)} részszó szerepel, valami x, y ∈ (alphL_{2})^{∗} esetén.

• Az sem lehet, hogy valamely 1 ≤ i ≤ n esetén a_{1}^{(i)}-ből vagy b_{1}^{(i)}- ből { a_{2}^{(j)} } és { b_{2}^{(j)} } feletti szavakat is le lehessen vezetni, mert ekkor keverten fordulhatnának elő a (j) felső indexű a és b betűk.

• Nem állhat elő az a helyzet sem, hogy valamely 1 ≤ i ≤ n esetén a_{1}^{(i)}-ből az üres szót le lehessen vezetni, mert ekkor valamely másik t, 1 ≤ t ≤ n felső indexű betűből kétféle felső indexű betűkből álló szót kellene levezetni (mert pótolni kell a törlődött a_{1}^{(i)} betűket). Ez pedig az előző pontok értelmében nem lehetséges. Hasonló okok miatt b_{1}^{(i)}-ből sem lehet levezetni az üres szót.

• Tehát minden 1 ≤ i ≤ n esetén, pontosan egy j és t ( 1 ≤ j, t ≤ n) felső index létezik, melyre a_{1}^{(i)} → u és b_{1}^{(i)} → v esetén u ∈ { a_{2}^{(j)}, b_{2}^{(j)}, c^{(j)} }^{+} illetve v ∈ { a_{2}^{(t)}, b_{2}^{(t)}, c^{(t)} }^{+} fennáll. Belátjuk indukcióval, hogy j = t = i . i = 1 esetén igaz az állítás, mert a generált nyelvbeli szavak a_{1}^{(1)} betűvel kezdődnek, a b betűk közül pedig b_{1}^{(1)} fordul elő először. Ha valamely i-re (1 ≤ i ≤ n − 1) már beláttuk az állítást, akkor i + 1-re azért igaz, mert az i-edik féle a illetve b betű után az i + 1-edikek következnek L_{REP} (n, = k)-ban.

2. Csak ágensek hozhatnak be c betűt, különben k-nál több c betű fordulhatna elő L(Σ′)-beli szavakban.

3. a_{1}^{(i)}-t nem lehet b_{2}^{(i)} feletti, illetve b_{1}^{(i)}-t nem lehet a_{2}^{(i)} feletti szóvá újraírni az L_{REP} (n, = k) szavainak felépítése miatt.

Tehát eddig azt láttuk be, hogy P_{E}′ a_{1}^{(i)}-t csak a_{2}^{(i)} feletti, b_{1}^{(i)}-t pedig csak b_{2}^{(i)} feletti szóvá írhatja újra; sőt azt is láttuk, hogy bármely 1 ≤ i ≤ n esetén léteznie kell olyan P_{E}′-beli szabálynak, amely a fenti betűket nem üres szóvá írja újra. Mivel a c^{(i)} betűket csak ágensek hozhatják be a levezetés során, ezért ezek beszúró szabállyal kerülnek a levezetett szavakba. Ezek a szabályok a következő három alak valamelyikébe írhatók.

1. ( αb_{1}^{(j)}, γc^{(i)}δ, b_{1}^{(t)}β )

2. ( αb_{1}^{(j)}, γc^{(i)}δ, a_{1}^{(t)}β )

3. ( αa_{1}^{(j)}, γc^{(i)}δ, a_{1}^{(t)}β )

ahol α, β ∈ alphL_{1}^{∗}, γ, δ ∈ alphL_{2}^{∗} és 1 ≤ j ≤ t ≤ n. Az első alak azért nem lehetséges mert ekkor c^{(i)} előtt és mögött is szerepelhet b_{2}^{(j)} betű ( a környezet b_{1}^{(j)} → [b_{2}^{(j)}]^{q} szabályát használva, ahol q ≥ 1.) A második esetben ugyanez a helyzet, ezért ez sem lehetséges. A harmadik esetben pedig a_{2}^{(j)} betű szerepelhetne c^{(i)} előtt és mögött is. Tehát minden esetet kizártunk, azaz ellentmondásra jutottunk a kezdeti feltétellel.

Mivel a bizonyítás során az L_{REP} (n, = k) nyelvnek csak azokat a tulajdonságait használtuk, amelyekkel az L_{REP} (n, ≤ k) nyelv is rendelkezik, így kimondhatjuk a következő állítást, melynek bizonyítása teljesen megegyezik az előbbi állítás bizonyításával:

Állítás 24 1 ≤ k ≤ n esetén L_{REP} (n, ≤ k) ∈ LELP_{n,≤k}( 0L, REP ) \ LELP ( 0L, INS )

Összefoglalva az eddigi eredményeket:

Tétel 4

1. Bármely 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén az LELP_{n,=k}( 0L, CF ) és LELP_{n,≤k}(0L, CF) nyelvosztályok mindegyike összehasonlíthatatlan az LELP_{m,=l}( 0L, INS ) és LELP_{m,≤l}( 0L, INS ) nyelvosztályok mindegyikével.

2. Bármely 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén az LELP_{n,=k}( 0L, CF ) és LELP_{n,≤k}(0L, CF) nyelvosztályok mindegyike összehasonlíthatatlan az LELP_{m,=l}( 0L, REP ) és LELP_{m,≤l}( 0L, REP ) nyelvosztályok mindegyikével.

3. Bármely 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén az LELP_{n,=k}( 0L, REP ) és LELP_{n,≤k}( 0L, REP ) nyelvosztályok mindegyike összehasonlíthatatlan az LELP_{m,=l}( 0L, INS) és LELP_{m,≤l}( 0L, INS) nyelvosztályok mindegyikével.

Azt kaptuk tehát, hogy egyrészt az (n, = k) és (n, ≤ k) nyelvosztályok nagyon hasonló hierarchiát mutatnak a CF, INS illetve REP esetben (lásd 4. fejezet), de mégis annyira különbözőek, hogy semelyik két nyelvosztály között, melyeket különböző ágensekkel (CF, INS, REP) dolgozó EG rendszerek állítanak elő, nincs tartalmazás.

Nyitott kérdések és további variánsok

6.1 Nyitott kérdések

Bár az előző fejezetekben vizsgált kérdésekre pontos választ kaptunk, megismertük a különféle EG rendszerek által generált nyelvosztályok kapcsolatát, mégis számos kérdés maradt megválaszolatlanul. Az egyik legfontosabb az, hogy hol helyezkednek el ezek a nyelvosztályok. Jó volna minél szorosabban behatárolni mind alulról, mind felülről a helyüket az ismert nyelvosztályokhoz képest. Másrészt látható néhány furcsaság az alkalmazott bizonyításokban. Az első ilyen a fiktív ágensek esete. Arról van szó, hogy az eredeti definíció nem zárja ki ilyen ágensek létezését, azaz olyan ágensek létezését, melyek soha nem vehetnek részt a levezetésben alkalmazhatatlan szabályaik miatt. Nyitott kérdés, mennyiben módosulnának a 4. és 5. fejezet eredményei, ha a definícióban kikötnénk, hogy ilyen ágensek nem lehetnek az EG rendszerekben.

Szintén érdekes kérdés az, hogy mennyiben változtatná meg a kapott hierarchiát az, ha a ≤ k mód definícióját úgy módosítanánk, hogy a ≤ k ezentúl a következőt jelentse: legfeljebb k , de legalább 1 ágens dolgozik minden lépésben.

Sokszor fordult elő az is, hogy két nyelvosztály összehasonlíthatatlanságát egy véges nyelv segítségével mutattuk meg. Érdekes volna vizsgálni azt az esetet, mikor két nyelvosztályt nem tekintünk különbözőnek, ha csak véges sok nyelvben, illetve ha csak véges nyelvekben különböznek. Kérdezhetjük, hogy hogyan alakul a vizsgált hierarchia ebben az esetben.

Vizsgálhatunk továbbá hibrid EG rendszereket, azaz olyan egyszerű EG rendszereket, ahol INS, REP illetve CF szabályokat használó ágensek vegyesen fordulnak elő. Ez a modell adekvátabb leírását adja a genetikai jelenségeknek, mint az eddigiek.

Természetesen az egyszerű EG rendszerek vizsgálata mellett az eredeti definíció szerinti EG rendszereket ( tehát ahol a φ_{i} és ψ_{i} leképezések is szerepet kapnak ) is vizsgálnunk kellene. Legalábbis jó volna egy olyan változatukat leírni, amely bonyolultabb az egyszerű EG rendszerek eseténél, de valami korlátozást mégis tartalmaz ( hogy a probléma kezelhető maradjon). Erről lásd még [CVKKP97]-t, illetve a következő alpontot.

6.2 Az EG rendszerek további variánsai

6.2.1 Kiterjesztett EG rendszerek

Az egyszerű, kiterjesztett ( extended ) EG rendszerek abban különböznek az egyszerű, nem-kiterjesztett EG rendszerektől, hogy a környezet ábécéjének egy Δ ⊆ V_{E} részhalmazát megkülönböztetjük: ez a terminális betűk halmaza, más szóval a terminális ábécé. A Σ = ( V_{E}, P_{E}, R_{1}, …, R_{n}, w_{0}, Δ ) kiterjesztett, egyszerű EG rendszer által generált nyelvnek azon terminális szavak halmazát nevezzük, melyek w_{0}-ból véges sok lépésben elérhetők. Azaz:

L_{E}(Σ, a) = { v ∈ Δ^{∗} | w_{0}⟹_{Σ}^{∗}v }

ahol a ∈ { = 1, = 2, …, = n, ≤ 1, ≤ 2, …, ≤ n }. Az, hogy a levezetés során előforduló szavak közül nem mindegyik kerül be a generált nyelvbe, a kiterjesztett EG rendszerek erejét nagyon megnöveli. A CF szabályokat használó ágensekkel dolgozó EG rendszerek esetén, a generált nyelvekre – a nem-kiterjesztett eset ismeretében – meglepő eredményt kapunk. Az n ágenssel = k illetve ≤ k módban dolgozó kiterjesztett, egyszerű EG rendszerek által generált nyelvek osztályát ELELP_{n,=k}(0L, CF)-fel jelöljük, ha sem P_{E}, sem az ágensek nem tartalmaznak λ-szabályt, különben a nyelvosztály jelölése ELELP_{n,=k}^{λ}(0L, CF). Ezen jelölésekkel a következőképp foglalhatjuk össze az eredményeket:

1. ELELP_{n,≤k}(0L, CF) = ELELP_{m,≤l}(0L, CF) minden 1 ≤ l ≤ m és 1 ≤ k ≤ n esetén.

2. ELELP_{t_{1},1}(0L, CF) ⊃ ELELP_{t_{2},=2}(0L, CF) ⊃ ⊃ ELELP_{t_{3},=3}(0L, CF) ⊃ … minden t_{i} ≥ i, i ≥ 1 esetén.

3. ELELP_{n,=k}^{λ}(0L, CF) = ELELP_{m,≤l}^{λ}(0L, CF) minden 1 ≤ k ≤ n és 1 ≤ l ≤ m esetén.

Azaz a kiterjesztett esetben nincsen valódi hierarchia, a generált nyelvosztályok egybeesnek. A (2) pont is ezt tükrözi; az, hogy = k módban kevesebb nyelvet lehet generálni, mint = l módban, ha k > l, abból adódik, hogy a k-nál rövidebb szavakon k darab ágens nem tud dolgozni, ezért azokat a nyelveket, melyekben ilyen szavak előfordulnak nem lehet λ-mentesen előállítani = k módban.

A kapott eredmények azt mutatják, hogy a kiterjesztett EG rendszerek túl erősek, már egy ágenssel is generálni tudnak mindent. Ha nem egybeeső struktúrát akarunk kapni, akkor finomabb eszközökhöz kell nyúlni. A pontos bizonyításokért lásd [Csi]-t. Az EG rendszerek egy másik speciális esete is jól rávilágít arra, hogy a Δ ábécé megkülönböztetése milyen jelentősen növeli a generatív erőt. Az eredeti (“nem egyszerű”) EG rendszerek esetén is tekinthetünk kiterjesztett rendszereket. Ekkor nem csak V_{E}-nek, hanem 1 ≤ i ≤ n esetén V_{i}- nek is kitüntetjük egy-egy részhalmazát, ezek lesznek a Δ_{E}, Δ_{1}, Δ_{2}, …,Δ_{n} terminális ábécék. [CVKKP93]-ban és [CVKKP94a]-ben bizonyításra kerül, hogy a megszorított, kiterjesztett EG rendszerek ( ez az összes EG rendszerek halmazának egy speciális részhalmaza ) által λ-mentesen generált nyelvek osztálya megegyezik a CS nyelvek osztályával. Ha λ-szabályokat is megengedünk, akkor pedig a RE nyelvosztályt kapjuk. A fenti eredmények CF szabályokat használó ágensekkel dolgozó EG rendszerekről szólnak, a többi esetet még nem vizsgálták. A fenti rendszerek egy további vizsgálata található [DM95]-ban.

6.2.2 Előre megadott team-ekkel dolgozó EG rendszerek

Az eddigiekben az EG rendszerek = k vagy ≤ k módban dolgoztak. Ez azt jelentette, hogy minden egyes lépésben egy pontosan k, illetve egy ≤ k ágensből álló team dolgozott, újraírta a környezetet néhány helyen. Ezekben a team-ekben bármely ágens szerepelhetett, az ágensek kiválasztására nem volt feltétel, csak a számukra.

Az előírt team-ekkel dolgozó rendszerek esetén nem ez a helyzet. A rendszer leírásakor azt is megadjuk, mik a lehetséges team-ek, melyek azok az ágensek, amelyek együtt dolgozhatnak egy lépés során. Ebben a rendszerben a levezetés hasonlóan történik, mint az eredeti esetben, azzal a kivétellel, hogy míg az = k módban bármely k ágens válsztható volt, most minden lépésben egy team-et kell választanunk az előre megadottak közül. Ez a team fogja az adott lépésben végrehajtani a párhuzamos, részleges újraírást a környezeten. Az előírt team-ekkel dolgozó, kiterjesztett EG rendszerek különféle változatairól és az elért eredményekről lásd [tB96]-t. Az eddigi vizsgálatok csak a CF szabályokat használó ágensekkel dolgozó EG rendszereket érintették, az INS és a REP eset itt is további munkát igényel.

6.2.3 További lehetőségek még...

Ebben a részben néhány életszerű jelenséget sorolunk fel a teljesség igénye nélkül, melyeket – az EG rendszerek eredeti definíciójánk módosításával– jól le lehet írni a vizsgált modell keretein belül. Azt mondhatjuk, hogy egy ágens elérte a felnőtt állapotot, ha az őt leíró szó nem, vagy nem nagyon változik, lényegében állandó. Megkülönböztetünk öreg ágenseket illetve úgynevezett élő fosszílíákat. (Lásd [CVKKP94a]-t.)

Az ágensek halmazát populációnak tekintve, a legalapvetőbb életjelenséget, a születést is bevehetjük modellünkbe. (Lásd [CVKKP94b].) Egy reproduktív EG rendszer olyan Σ = ( A_{1}, …, A_{n} ) rendszer, ahol E a környezet, amely ugyanúgy van definiálva, mint eddig, A_{i} pedig 1 ≤ i ≤ n esetén az i-edik típusú ágensek halmaza. Azaz minden A_{i}-beli A_{i} ágens A_{i} = ( V_{i} ∪ {⊔}, P_{i}, R_{i}, φ_{i}, ψ_{i} ) alakú, ahol V_{i}, P_{i}, R_{i}, φ_{i}, ψ_{i} a szokásos jelentéssel bírnak; egyetlen kivétel van : P_{i}-ben α → β_{1} ⊔ β_{2} ⊔ … ⊔ β_{k} alakú szabályok vannak ( α ∈ V_{i}, β_{j} ∈ V_{i}^{∗}, ⊔ ∉ ∪_{i=1}^{n}V_{i}, k ≥ 2, 1 ≤ j ≤ k ), ⊔-t reprodukciós karakternek nevezzük. A Σ = ( E, A_{1}, …, A_{n} ) reproduktív EG rendszer állapotának a σ = ( w_{E}, W_{1}, W_{2}, …, W_{n} ) (n + 1)-est tekintjük, ahol w_{E} ∈ V_{E}^{∗}, W_{i} =< w_{i_{1}}, …, w_{i_{k_{i}}} >, w_{i_{j}} ∈ V_{i}^{∗}, 1 ≤ j ≤ k_{i}, 1 ≤ i ≤ n. Tehát w_{E} írja le a környezet állapotát, w_{i_{1}}, …, w_{i_{k_{i}}} pedig az i-edik típusú ágensek állapotait. Új ágens akkor születik, ha valamely ágens állapotában a ⊔ jel megjelenik. Ha ekkor az ágens állapota w_{1} ⊔ w_{2} ⊔ … ⊔ w_{s}, akkor az eredeti ágens A^{(1)}, A^{(2)}, …, A^{(s)} ágensek formájában születik újjá, mindegyik új ágens típusa (azaz akciószabályaik, fejlődési szabályaik, és a két függvény, φ és ψ ) ugyanaz lesz, mint a szülőé, állapotaik pedig rendre w_{1}, w_{2}, …, w_{s}. Ebben a rendszerben a túlnépesedést az jelenti, ha már több ágens van az A_{1}, …, A_{n} halmazokban összesen, mint ahány betűből a környezetet leíró szó áll. Az ágenst halottnak tekintjük, ha φ nem választ fejlődési szabályt, vagy a kiválasztott szabályok egyike sem alkalmazható. Bevezethetjük azt is, hogy az ágensek nem csak a környezeten, hanem egymáson is végrehajthatnak akciószabályokat. Mindkét eset ( ha csak egymáson, illetve ha egymáson és a környezeten is hathatnak az ágensek) tárgyalásra kerül [CV95]-ban. Egy Σ = ( E, A_{1}, …, A_{n}, ρ) EG rendszerben szimbiózis fordul elő, ha ρ szimmetrikus bináris reláció az { A_{1}, …, A_{n} } halmazon. Egy A_{i} ágens akkor és csak akkor hajthat végre akciót egy lépés során, ha minden olyan A_{j} ágens is dolgozik az adott lépésben, melyre A_{i}ρA_{j} áll fenn. Továbbá az A_{i} és A_{j} ágenseknek közvetlenül egymás mellett kell dolgozniuk, azaz az általuk átírt betűknek szomszédosaknak kell lenni.

Egy Σ = ( E, A_{1}, …, A_{n}, κ) EG rendszerben parazitizmus fordul elő, ha κ aszimmetrikus bináris reláció az { A_{1}, …, A_{n} } halmazon. Az A_{j} ágens az A_{i} ágens parazitája, ha A_{i}κA_{j} áll fenn. A két ágens soha nem hajthat végre egyszerre akciót a környezeten, még ha mindketten aktívak is egy adott lépésben. Ezenkívül, A_{j} csak a környezetet leíró szó azon részszaván hathat, ami az előző lépésben jelent meg, A_{i} hatására. A fenti két változat megtalálható [CVKKP94a]-ben.

A táplálkozási piramist is modellezhetjük az EG rendszerek nyelvén. (A modell [CV95]-ben került bevezetésre.) Egy szintezett EG rendszer olyan Σ = ( E, A_{1}, …, A_{n} ) struktúra, ahol E a szokásos környezet, A_{i} =< A_{i_{1}}, …, A_{i_{k_{i}}} > pedig azonos típusú ágensek halmaza, ahol A_{i_{j}}-k a szokásos ágenseknek felelnek meg 1 ≤ j ≤ k_{i} esetén; A_{i}-t 1 ≤ i ≤ n esetén az i-edik szintnek nevezzük. A_{i} ∩ A_{j} = ∅. A Σ = ( E, A_{1}, …, A_{n} ) rendszer állapotán a σ = ( w_{E}, W_{1}, W_{2}, …, W_{n} ) (n + 1)-est értjük, ahol w_{E} ∈ V_{E}^{∗}, W_{i} =< w_{i_{1}}, …, w_{i_{k_{i}}} >, w_{i_{j}} ∈ V_{i}^{∗}, 1 ≤ j ≤ k_{i}, 1 ≤ i ≤ n. A σ = (w_{E}, W_{1}, W_{2}, …, W_{n}) állapotból a rendszer a σ′ = (w_{E}′, W_{1}′, W_{2}′, …, W_{n}′) állapotba megy át akkor, ha az alábbi feltételek teljesülnek:

• w_{n_{j}}⟹_{φ_{n}(w_{E})}w′_{n_{j}} teljesül, ha 1 ≤ j ≤ r_{n}, azaz a legfelső szinten csak fejlődési szabályok okoznak változást.

• Ha w_{j_{k}} = x_{1} … x_{p} … x_{s}, ahol x_{i} ∈ V_{j} (1 ≤ j < n) és w_{j_{k}}′ = y_{1} … z_{p} … y_{s}, ahol y_{i}-t x_{i}-ből deriváltuk (i ≠ p esetén ) φ_{j}(w_{E})-beli fejlődési szabállyal, z_{p} pedig x_{p}-ből jön az j +1-edik szint, A_{j+1} valamely ágensének akciója következtében ( 1 ≤ i ≤ s, 1 ≤ k ≤ r_{j}, 1 ≤ j ≤ n − 1 ).

• Minden aktív ágens pontosan egy akciószabályt hajt végre a lépés során.

• w_{E}′ a w_{E}-ből deriválódik, az A_{1}-beli aktív ágensek akciójának és a környezet fejlődési szabályainak együttes eredményeként.

Azaz az ágensek nem a környezeten, hanem az egy szinttel lejjebb álló ágenseket leíró szavakon hatnak, a környezetet közvetlenül csak az első szinten, a hierarchia legalján álló ágensek érintik.

Az eddigiekben az ágensek definícióját változtattuk, ezáltal jutottunk az EG rendszerek újabb és újabb változataihoz. Módosíthatjuk a környezet definícióját is, például úgy, hogy 0L rendszerek helyett T 0L rendszereket nézünk. A táblás EG rendszerekkel [CVPS95] foglalkozik.

Jól látható, mennyi féle lehetőség kínálkozik a további kutatásra. A fenti lehetőségek közül ki kell választanunk azokat, melyek matematikai vagy biológiai szempontból valami érdekességgel bírnak, ezek lesznek a kutatás új irányai.