3. fejezet - Formális rendszer és néhány főbb típusa

Formális rendszernek (vagy átírási rendszernek) nevezünk minden olyan W = ( V, H ) párt, amelyben V egy ábécé, H pedig a V * × V * direkt szorzat egy véges részhalmaza. A H elemeit helyettesítési szabályoknak hívjuk és ha ( p , q ) ∈ H, akkor a p → q (ejtsd: p nyíl q) jelölést használjuk.

3.1. példa - Átírási rendszer

W = ( { a, b , d, e, é , f, k, l , ő, s, v , z }, { akedle, levesfőzelék } ). ★


Legyen r, sV *. Akkor mondjuk, hogy r - ből az s közvetlenül (vagy egy lépésben) levezethető W-ben, jelekben: r W s, vagy ha nem vezet félreértéshez, W elhagyásával rs, ha léteznek olyan p ', p, p '' , q ∈ V * szavak, hogy r = p ' pp '', s = p ' qp '' és p → q ∈ H. (Természetesen megengedett, hogy akár a p ', akár a p '', vagy akár mindkettő az üresszó legyen.) Szemléletesen, r W s azt jelenti, hogy az s szó megkapható az r szóból úgy, hogy r-ben valamely H-beli szabály baloldalán álló p rész-szó helyébe az e szabály jobboldalán álló q szót írjuk (lásd ábra).

Azt mondjuk, hogy a p - ből a q levezethető W-ben, jelekben p W * q, vagy ha nem vezet félreértéshez, W elhagyásával: p* q ha léteznek olyan p 0 , p 1, … , p k V * szavak, hogy p 0 = p , p k = q és p i W p i+1 ( i = 0, …, k-1 ). Emellett, amint szokásos, megállapodunk abban, hogy minden p ∈ V * szóra p W * p fennáll. Használni fogjuk még a p W + q jelölést is abban az esetben, ha azt akarjuk hangsúlyozni, hogy léteznek olyan p 0 , p 1, … , p k V * szavak, hogy p 0 = p , p k = q és p i W p i+1 ( i = 0, …, k-1 ). Világos, hogy a két jelölés p = q esetén kap eltérő értelmet.

3.2. példa - Levezetés átírási rendszerben

Tekintsük a fenti példában megadott formális rendszert és a babakedves szót. Ekkor a babakedvesbablevesbabfőzelék levezetés alkalmazásával látjuk, hogy például a W-beli babakedves szóból a bableves közvetlenül levezethető, a babfőzelék pedig levezethető. ★


Amennyiben olyan formális rendszereket tekintünk, melyekben a helyettesítési szabályok szimmetrikusak, eljutunk az asszociatív kalkulus fogalmához. Ha tehát valamely asszociatív kalkulus esetén egy p szó helyettesíthető q - val, akkor a q szó is helyettesíthető p - vel. Emiatt nem is helyettesítési szabályokról, hanem megengedett cserékről szokás beszélni. Továbbá, ha egy p szóból egy q szó levezethető az asszociatív kalkulusban, akkor azt mondjuk hogy p ekvivalens q - val.

Legyen W = ( { a, c , k, m, ó , u, s, t , y }, { acs - ó , ka - kus } ). Asszociatív kalkulus esetén a szabályok bal és jobboldalát  → helyett - - el (kötőjellel) szokás elválasztani, ezzel is hangsúlyozva, hogy a szabályok szimmetrikusak. Példánknál maradva, az acs helyettesíthető az ó - val és az ó is helyettesíthető acs - csal. Ugyanígy, a ka helyettesíthető kus - sal és a kus a ka - val. Tekintsük a m acska ka mókus levezetést. Ekkor a macska ekvivalens W-ben a mókus - sal. Ehhez ⇒ W * helyett ≃ W - t, vagy ha nem okoz félreértést, akkor egyszerűen (az ekvivalencia egyik szokásos jelét,) ≃-t szokás használni, azaz macskamókus. Vizsgáljuk meg most ezt az ≃-t mint relációt. Ez az ≃reláció reflexív, azaz minden V *-beli p szóra pp. Például, macskamacska. Az ≃szimmetrikus, azaz minden V *-beli p, q szópárra pq akkor és csak akkor, ha qp. Például, macskamókus következménye mókusmacska és viszont. Ugyanígy, példánkban kutyamacska következménye macskakutya és viszont. Az ≃ tranzitív, azaz minden V *-beli p, q, r szó-hármasra pq és qr esetén pr. Példánkban macskamóka és mókamókus miatt macskamókus. (De ugyanígy igaz, hogy macskamókus és mókusmóka miatt macskamóka. )

1. Megjegyzés. a reflexív és tranzitív tulajdonság közvetlenül következik a levezethetőség definíciójából. A szimmetria a szabályok szimmetrikus volta miatt, továbbá a tranzitivitás miatt áll fenn, melynek igazolását az olvasóra bízzuk.)

Emlékeztető. Egy M halmaz önmagával való Descartes szorzatának (jelekben: M × M - nek) részhalmazait M feletti bináris relációnak, vagy röviden, relációnak szokás nevezni. Speciálisan, M × M véges részhalmazait véges relációknak is szokás hívni ( M felett).

Felhasználva az előző példánkban tárgyaltakat, vegyük észre, hogy ha egy adott W = ( V, H ) formális rendszerbeli közvetlen levezethetőséget mint a V * halmaz feletti (véges) bináris relációt tekintjük, úgy a belőle származtatható levezethetőség nem más mint a közvetlen levezethetőség reflexív és tranzitív lezárása, vagyis az a legszűkebb reflexív és tranzitív reláció, melynek a tekintett levezethetőség részrelációja. Asszociatív kalkulus esetén, mint példánkban már említettük, ez a levezethetőség (mint reláció) ekvivalencia reláció lesz, ugyanis a reflexív és tranzitív tulajdonság mellett a szimmetrikus tulajdonsággal is rendelkezni fog. Emiatt szokás egy W = ( V, H ) asszociatív kalkulusban ekvivalensnek hívni a p, qV * szavakat, ha p* q azaz ha pq.

Akkor mondjuk, hogy a W = ( V, H ) asszociatív kalkulusban a szóprobléma algoritmikusan megoldható, ha létezik olyan algoritmus, melynek segítségével tetszőleges p, q párra eldönthető, hogy p és q ekvivalens-e (azaz pq fennáll-e) és ha igen, akkor az algoritmus egy pp 1p 2 ⇒ … ⇒ p n-1q levezetést is szolgáltat. Ezen fogalomnak azért van különös jelentősége, mert kimutatható, hogy nem minden asszociatív kalkulusban oldható meg a szóprobléma algoritmikusan (ami egyúttal azt is igazolja, hogy nincs olyan univerzális módszer, ami minden matematikai problémát képes megoldani). Később még vissza fogunk térni erre az eldönthetőségi kérdésre.

Egy W = ( V, H ) formális rendszert generatív rendszernek nevezünk, ha ki van tüntetve V * egy nem üres és véges részhalmaza, amelyet W axiómarendszerének nevezünk (és rá többnyire az Ax jelölést használjuk). Egy ilyen W generatív rendszert W = ( V, Ax , H ) alakban szokás megadni (aholis V az ábécé, Ax az axiómák, H pedig a szabályok nem üres és véges halmaza). W - hez hozzárendelünk egy L g ( W ) halmazt az L g ( W ) = { pV * | ∃ s  ∈ Ax : s W * p } definícióval, s ezt a halmazt a W generatív rendszer által generált nyelvnek hívjuk. L g ( W ) tehát tartalmazza mindazon V *-beli szavakat, melyek legalább az egyik axiómából levezethetők.

Egy W = ( V, Ax , H ) generatív rendszert úgy is szokás interpretálni (azaz értelmezni), hogy V bizonyos fogalmak rendszere, Ax az axiómarendszer (vagyis az alapigazságok, vagy igaznak tartott alapvető állítások gyűjteménye), V * elemei a V fogalomkörben megfogalmazható (értelmes vagy értelmetlen) formális mondatok halmaza, H a W-ben megengedett elemi bizonyítási lépések halmaza, pp 1 ⇒ … ⇒ p n q a q formális mondat p - ből való bizonyítása, L g ( W ) pedig a V fogalomkörben megfogalmazható és az Ax axiómarendszerből W-ben bebizonyítható formális mondatok (kijelentések) halmaza.

Analóg módon, tekinthetjük az összes olyan szavak halmazát is, melyekből az axiómák közül legalább az egyik levezethető. Ebben az esetben W - t (a generatív rendszer elnevezés helyett) analitikus rendszernek, az L a ( W ) = { pV * | ∃ s  ∈ Ax : p W * s } halmazt pedig a W analitikus rendszer által acceptált, vagy más szóval, a W analitikus rendszer által elfogadott nyelvnek, vagy még másképp a W analitikus rendszer által felismert nyelvnek hívjuk.

Az analitikus rendszer által elfogadott nyelvet a későbbiekben fogjuk interpretálni (azaz értelmezni).

3.3. példa - Generatív rendszer

Vegyük a W = ( { 1, 2, +, = }, { 1 + 1 = 2 }, { = → + 1 = 1 + } ) generatív rendszert. Fogalmaink az 1, 2 természetes számok, továbbá az összeadás és az egyenlőség (jele). Egyetlen axiómánk van, 1 + 1 = 2. Az 1 + 1 + 1 + 1 = 1 + 1 + 2 kijelentés (vagy "tétel"-nek is lehetne mondani) bebizonyítható W-ben. Ime a "bizonyítás:" (Egyetlen) axiómánk 1 + 1 = 2. Ebből indulunk ki :


1 + 1 = 2 ⇒ 1 + 1 + 1 = 1 + 2 ⇒ 1 + 1 + 1 + 1 = 1 + 1 + 2. ★

3.4. példa - Analitikus rendszer

Tekintsük a W = ( { <, >, 0, 1, 2, 3, 4, 5, 6 , 7, 8, 9 }, { < 0 >, < 5 > }, { 00 → 0, 10 → 0, 20 → 0, 30  → 0, 40 → 0, 50 → 0, 60 → 0, 70 → 0 , 80 → 0, 90  → 0, 05 → 5, 15 → 5, 25 → 5, 35 → 5, 45 → 5, 55  → 5, 65 → 5, 75 → 5, 85 → 5 , 95 → 5 } ) analitikus rendszert. Az olvasóra bízzuk annak igazolását, hogy L a ( W ) épp az öttel osztható, < a 1a n > ( a 1, …, a n  ∈ { 0, …, 9 } ) alakban megadott nemnegatív egészek halmaza. W tehát "felismeri" az 5 - tel osztható nemnegatív egészeket. ★


Egy W = ( V, Ax , H ) generatív rendszert szemi-Thue rendszernek (ejtsd: tyué) nevezünk (az angol semi[ejtsd:szemi] = félig-, fél szó alapján), ha ki van tüntetve V * egy olyan F részhalmaza, melyre AxF. Egy ilyen szemi-Thue rendszert W = ( V, Ax , H, F ) alakban adunk meg, ahol F a formulák halmaza, és a W - nek a generatív rendszerhez hasonló értelmezése esetén mondhatjuk még azt is, hogy F az igaz (vagy igaznak tartott) állítások (kijelentések, mondatok, tételek) halmaza (lásd ábra).

Képezzünk egy szemi-Thue rendszert oly módon, hogy a 3.3. Példa (Generatív rendszer)-beli generatív rendszert kiegészítjük formulákkal. Ezzel összhangban tekintsük a következő példát.

3.5. példa - Szemi-Thue rendszer

W = ( { 1, 2, +, = }, { 1 + 1 = 2 }, { = → + 1 = 1 + }, { 1 + 1 = 2, 1 + 1 + 1 + 1 = 2 + 2, 1 + 1 ( + 1 ) n = ( 1 + ) n + 2 , n = 1, 2, … } ).


Amint szokásos, ( + 1 ) n itt azt jelenti, hogy + 1 n-szer van írva. Például: ( + 1 ) 3 = + 1 + 1 + 1. Hasonlóan, ( 1 + ) n jelentése az, hogy 1 + van n - szer írva. Például: ( 1 + ) 2 = 1 + 1 + . A nyilvánvalóan igaz 1 + 1 + 1 + 1 = 2 + 2 összefüggés a példabeli szemi-Thue rendszerben nem bizonyítható. Mint már a bevezetésben elmondtuk, ezen a játékos példán bemutatott probléma a matematika egyes nehezebb fejezeteiben is fennáll. Nevezetesen, vannak precízen megfogalmazható, de nem bizonyítható és nem is cáfolható matematikai kijelentések. ★

Legyen W = ( V, Ax , H, F ) tetszőleges szemi-Thue rendszer, s jelölje Ax* p röviden azt a tényt, hogy létezik olyan p 0 ∈ Ax, melyre p 0* p. Ezt a jelölést használva L( W ) = { pV * | Ax* p } és W-ben absztrakt módon az F halmaz mint elmélet ( = igaz vagy igaznak tartott állítások halmaza, rendszere, vagy gyűjteménye) axiomatizálásának tipikus kérdései a következőképp fogalmazhatók meg:

a.) teljes-e az elmélet, vagyis az Ax axiómarendszerből minden igaz állítás bebizonyítható-e. Jelöléssel: fennáll-e az FL g ( W ) tartalmazás;

b.) ellentmondásmentes (azaz helyes)-e az elmélet, vagyis igaz-e, hogy az axiómarendszerből nem vezethető le egyidejűleg igaz és hamis állítás is. Képletben: igaz-e, hogy akárhogy is adjuk meg a p ∈ F és qF párokat, Ax* p mellett Ax* q nem állhat fenn egyidejűleg. (Vegyük észre, hogy ha Ax* q és qF, akkor felhasználva Ax* q jelentését, lenne olyan p 0 ∈ Ax, hogy p 0* q, ami AxF és p 0* p 0 miatt azt is jelentené, hogy p 0 ∈ F és qF mellett Ax* p 0 és Ax* q. Az ellentmondásmentesség feltétele tehát tulajdonképp azt jelenti, hogy hamis kijelentés nem vezethető le az axiómarendszerből.)

c.) kategórikus (= konzekvens)-e az elmélet, vagyis az Ax axiómarendszerből minden igaz állítás, de csakis az igaz állítások bebizonyíthatók-e. Jelöléssel: F = L g ( W ) fennáll-e; (Vegyük észre, hogy egy elmélet pont akkor konzekvens, ha egyidejűleg teljes és helyes is.)

d.) minimális-e az elmélet, azaz igaz-e, hogy egyik axióma sem bizonyítható be a másikból. Képletben: igaz-e, hogy ha p, q ∈ Ax és p* q, akkor szükségképp p = q.

3.6. példa - Elmélet teljessége, ellentmondásmentessége

Az előző példabeli "elméletünket" vizsgálva megállapíthatjuk, hogy nem teljes, mert az F = { 1 + 1 = 2, 1 + 1 + 1 + 1 = 2 + 2, 1 + 1 ( + 1 ) n = ( 1 + ) n + 2 , n = 1, 2, … } elmélet nem minden kijelentése bizonyítható W-ben (pl. az 1 + 1 + 1 + 1 = 2 + 2 nem). Emiatt "elméletünk" nem is kategórikus. Mivel "hamisnak tartott", azaz F - en kívüli állítás 1 + 1 = 2 - ből (egyetlen axiómánkból) nem vezethető le ( ugyanis minden belőle levezethető "állítás" vagy maga az 1 + 1 = 2 lesz, vagy 1 + 1 ( + 1 ) n = ( 1 + ) n + 2 alakú lesz, ahol n tetszőleges természetes szám), "elméletünk" ellentmondásmentes. Végül, lévén csak egyetlen axiómánk, "elméletünk" nyilvánvalóan minimális. ★


Végül megjegyezzük, hogy lehetett volna a formális rendszer és a belőle származtatott különféle speciális formális rendszer típusok fogalmának kialakításakor a közvetlen levezethetőséget és a levezethetőséget másképp is definiálni. Erre az egyik legnevezetesebb példa a Post-féle normál rendszer.

A Post-féle normál rendszer (hasonlóképp a generatív rendszerhez) egy olyan V ábécéből, Ax axiómarendszerből és H helyettesítési szabályokból felépülő W = ( V, Ax , H ) hármas ( Ax itt is nem üres és véges részhalmaza V *-nak, továbbá H ezesetben is nem üres és véges részhalmaza V * × V *-nak), melyben H elemei pa → aq alakúak, aholis a ∈ V egy olyan betű, mely sem p-ben, sem q-ban nem fordul elő. Akkor mondjuk, hogy a V *-beli p 1 szóból a V *-beli q 1 szó közvetlenül levezethető (jelekben, mint korábban : p 1 W q 1, vagy ha nem vezet félreértéshez, egyszerűen csak p 1q 1 ), ha található olyan V-beli a betű, továbbá találhatók olyan ( V ∖ { a } )*-beli p, q, r szavak, hogy p 1 = pr , q 1 = rq, és pa → aq ∈ H. Ezenkívül, mint korábban, azt mondjuk, hogy p - ből a q levezethető W-ben, jelekben: p W * q, vagy ha nem vezet féreértéshez, W elhagyásával: p* q ha léteznek olyan p 0 , p 1, … , p k V * szavak, hogy p 0 = p , p k = q és p i W p i+1 ( i = 0, …, k-1 ). Emellett, amint szokásos, itt is megállapodunk abban, hogy minden p ∈ V * szóra p W * p fennáll. (Másként mondva, a levezethetőség mint V * feletti reláció, ezesetben is reflexív és tranzitív lezárása a közvetlen levezethetőségnek.) Ugyanúgy mint a generatív rendszer esetén, a Post-féle normál rendszerhez is szokás tekinteni az L g ( W ) = { pV * | ∃ s  ∈ Ax : s W * p } halmazt, amit a W Post-féle normál rendszer által generált nyelvnek hívunk. Természetesen mint a generatív rendszerből "képzett" analitikus rendszer esetén, itt is lehet tekinteni az L a ( W ) = { pV * | ∃ s  ∈ Ax : p W * s } halmazt mint a W által elfogadott nyelvet. (Emlékeztetőül: szerkezetileg a generatív rendszer ugyanaz mint az analitikus rendszer, csak a hozzájuk rendelt nyelvek szerkezete más.)

A Post-féle normál rendszer fogalmának kis módosításával jutunk el a Post-féle tag (tag [ejtsd: teg] = toldalék, vmit vmihez hozzáfűző eszköz vége) rendszer fogalmához. A Post-féle tag rendszer egy olyan W = ( V, s , H ) hármas, ahol V egy ábécé, H helyettesítési szabályok egy halmaza (azaz V * × V * egy nem üres és véges részhalmaza), s pedig egy tetszőleges, rögzített eleme V *-nak. Erre az s elemre a startszó elnevezés használatos. Akkor mondjuk, hogy a V *-beli p szóból az ugyancsak V *-beli q szó közvetlenül (vagy egy lépésben) levezethető W-ben, jelekben: p W q, vagy ha nem vezet félreértéshez, W elhagyásával pq, ha léteznek olyan p 1 , q 1, rV * szavak, hogy p = p 1 r, q = rq 1 és ( p 1 , q 1 ) ∈ H. (Természetesen megengedett, hogy az r az üresszó legyen.) A levezethetőségre (is) ugyanazt a jelölést használjuk mint korábban, továbbá a levezethetőség mint V * feletti reláció, ezesetben is reflexív és tranzitív lezárása a közvetlen levezethetőségnek. Ugyancsak összhangban az előzőekkel, a W által generált nyelv: L g ( W ) = { pV * | s W * p. } Definiálhatjuk a W által elfogadott nyelvet is: L a ( W ) = { pV * | p W * s}.

3.1. Markov-féle normál algoritmus

Az algoritmus intiutív fogalmát körülbelül a következőképp szokás megfogalmazni: A fegyelmezett, egyértelműen előírt elemi lépésekből egyértelműen felépíthető olyan feladatmegoldás modellje, melynek eredménye végrehajtójától függetlenül ugyanazon feladatokra akárhányszor is megismételve ugyanazon eredményt szolgáltatja. Segítségével egy adott feladatosztály minden feladata véges számú lépésben megoldható. (A legáltalánosabb értelemben természetesen egy algoritmus bármilyen emberi vagy nem emberi tevékenységre vonatkozhat, nemcsak matematikai avagy számítástechnikai feladatok megoldására.)

Fontos tulajdonságai közé tartozik tehát a függetlenség, ami azt jelenti, hogy ugyanazon feladatra ugyanaz az eredménye függetlenül attól hogy ki (vagy mi) a végrehajtója, az egyértelműség, ami azt jelenti, hogy ugyanazon feladatra akárhányszor is alkalmazzuk az algoritmust, mindig ugyanazt az eredményt szolgáltatja, az elemi lépésekre bonthatóság, ahol persze ezen elemi lépések, továbbá ezen lépések sorrendje is egyértelműen meg van határozva, valamint a végesség, vagyis az, hogy a feladatosztály minden egyes feladatára mindig véges sok lépésben befejeződik. Amennyiben a véges lépésben történő befejeződés követelményétől eltekintünk, az eljárás fogalmához jutunk. Ezen és ehhez hasonló intiutív megfogalmazások után születtek meg a 30-as évek második felétől a különféle matematikailag is precíz algoritmusfogalmak (tulajdonképpen szigorúan tekintve eljárásfogalmak), melyek közös érdekessége, hogy ekvivalensek. Ez azt jelenti, hogy ha egy algoritmust az egyik algoritmusfogalom segítségével megadtuk, akkor ugyanez az algoritmus a másik algoritmusfogalom segítségével is megadható. Ezen fogalmak egyike a Markov-féle normál algoritmus.

Egy W = ( V, H ) formális rendszert (Markov-féle) normál algoritmusnak nevezünk, ha H rendezett halmaz és ki van tüntetve benne egy H 1 részhalmaz (megengedve, hogy esetleg H 1 = ∅, azaz üres halmaz legyen). A H 1 elemeit záróhelyettesítéseknek hívjuk és p → qH 1 esetén használni fogjuk a p → . q jelölést is. Egy ilyen normál algoritmust W = ( V, H , H 1 ) alakban adunk meg, ahol a H = { p 1q 1, … , p m  → q m } megadás, azaz H elemeinek felsorolása feltételezésünk szerint egyben a H - beli rendezést is mutatja. Legyen p ∈ V * . Azt mondjuk, hogy a p szóra a W = ( V, H , H 1 ) algoritmus alkalmazható, ha van olyan 1 és m közötti i ( 1 ≤ i ≤  m ) index és olyan p ', p '' ∈ V * szópár, hogy p = p ' p i p '' . Legyen i a legkisebb ilyen index és válasszuk meg a p szó p ' kezdőszeletét úgy, hogy p i a p ' p i szóban rész-szóként csak egyszer forduljon elő. Rendeljük hozzá p - hez a q = p ' q i p '' szót és ezt a hozzárendelést jelöljük a következőképpen: legyen p W q ha p i q i H 1 és legyen p W . q ha p i q i H 1 . E hozzárendelést, mely a formális rendszer fogalmánál bevezetett közvetlen levezethetőség fogalmának a H - beli rendezést is figyelembe vevő módosítása, elemi helyettesítésnek szokás nevezni. (Az elemi helyettesítés nem tévesztendő össze a helyettesítéssel, azaz a helyettesítési szabályok halmazának egy elemével.) p W . q esetén elemi záróhelyettesítésről beszélünk.

Ha záróhelyettesítést hajtottunk végre az algoritmus megáll, egyébként az algoritmus helyettesítő lépése újra lefut az imént kapott szóra. Az algoritmus tehát mindaddig fut, amíg vagy záróhelyettesítés be nem következik, vagy nincs alkalmazható helyettesítési szabálya. Itt térünk ki arra, hogy a Markov-féle normál algoritmus a szó eredeti értelmében nem algoritmus, hanem eljárás, mivel - ahogy majd példát is mutatunk rá- nem feltétlenül fejeződik be, tehát a végesség feltétele nem teljesül.

3.7. példa - Elemi helyettesítés

Vegyük a W = ( { a, b , e, i, k , o, r, s , t, ú, z } , { szoba → kerti , bab → szob }, { szoba → kerti } ) normál algoritmust és a bababútor szót. Az i = 2, hiszen a második szabály alkalmazható rá. Vigyázni kell viszont, hisz a bab szó rész-szóként kétszer is előfordul. p ' thehát nem ba lesz (mert ekkor p ' p 1 = babab, aminek első három és utolsó három betűje is a bab szót alkotja ). Így p ' = λ, azaz az üresszó. Ennek megfelelően a bab abútor W szob abútor W . kertibútor levezetéshez jutunk. Itt a bababútor W szobabútor egy elemi helyettesítés, szobabútor W . kertibútor pedig egy elemi záróhelyettesítés. Igaz, hogy a szobabútor szóban is benne van a bab rész-szó, de mindig az első olyan szabályt kell alkalmazni, amit lehet. Emiatt a szobabútor szó után a kertibútor szó következik, nem a szoszobútor. ★


Azt mondjuk, hogy a p ∈ V * szóból kiindulva egy q ∈ V * szó eleme a W algoritmus levezetési láncának, ha teljesülnek az alábbi feltételek: q = p, vagy

(i) W alkalmazható p - re és

(ii) léteznek olyan r 0, … , r k V * szavak, hogy r 0 = p, r k = q, r i W r i+1 ( i = 0, …, k-1 ), ahol az r 0 W … ⇒ W r k-1 lánc nem tartalmaz záróhelyettesítést.

Azt mondjuk, hogy a p ∈ V * szóra egy q ∈ V * szó a W algoritmus eredménye (jelekben: p W * q ), ha q eleme a W p - ből induló ( p = r 0, … , r k = q ) levezetési láncának és vagy r k-1 W . r k , vagy pedig r k-1 W r k , és W az r k ( = q ) szóra már nem alkalmazható.

Emellett megállapodás, hogy ha W a p szóra nem alkalmazható, akkor p W * p .

Ha p W * q, akkor szokás mondani, hogy q a p szóval megadott adatsorozaton a W normál algoritmussal végrehajtott számítás eredménye. Eszerint, egy W = ( V, H , H 1 ) normál algoritmus esetén egy p ∈ V * (input) szóra a következő esetek állhatnak fenn:

(I) W a p - re nem alkalmazható. Ekkor a W - vel p - n végzett számítás eredményének magát a p adatot tekintik.

(II) p - ből kiindulva létezik záróhelyettesítéssel vegződő (azaz p W r 1, r 1 W r 2, …, r k-2 W r k-1, r k-1 W . r k alakú), vagy tovább nem folytatható helyettesítési lánc. (Ez utóbbi azt jelenti tehát, hogy a p W r 1, r 1 W r 2, …, r k-1 W r k láncban r k - ra W már nem alkalmazható.) Ekkor a p adaton a W - vel végzett számítás eredménye az r k = q szó.

(III) p - ből olyan helyettesítési lánc indul ki, mely soha nem fejeződik be. Ilyenkor azt mondjuk, hogy W a p - re nem áll meg, W a p adatból eredményt nem szolgáltat.

3.8. példa - Unáris számok összeadása

Tekintsük a W = ( { 1, + }, { 1 + → + 1, + +  → +, + → λ }, { + → λ } ) normál algoritmust (ahol λ az üresszót jelöli). Ekkor 1 + 1 + 1 + 1 ⇒ W + 11 + 1 + 1 ⇒ W + 1 + 11 + 1 ⇒ W + + 111 + 1 ⇒ W + + 11 + 11 ⇒ W + + 1 + 111 ⇒ W + + + 1111 ⇒ W + + 1111 ⇒ W + 1111 ⇒ W . 1111 .


Vegyük észre, hogy általában is, 1 m + 1 n W * 1 m + n , vagyis a példabeli algoritmus az "egyes számrendszerben" való "összeadás" algoritmusa. Ahány 1 - est "adunk össze", annyi 1 - esből álló sorozatot kapunk a végén záróhelyettesítéssel. Nincs alkalmazható szabálya az algoritmusnak például a 11 szóra. Ekkor eredménynek a korábbi definícióval összhangban magát a 11 - t tekintjük. ★

3.9. példa - Végtelen helyettesítési lánc

Egészítsük ki az előbbi példát az 1 → 11 szabállyal, méghozzá úgy, hogy ez legyen az első szabályunk. Az így kapott újabb W = ( { 1, + }, { 1 → 11, 1 + → + 1, + +  → +, + → λ }, { + → λ } ) algoritmus már nem fog befejeződni az 1 + 1 + 1 + 1 szóra (és sok más szóra sem): 1 + 1 + 1 + 1 ⇒ W 11 + 1 + 1 + 1 ⇒ W 111 + 1 + 1 + 1 ⇒ W 1111 + 1 + 1 + 1 ⇒ W 11111 + 1 + 1 + 1 … A módosított algoritmus tehát az 1 + 1 + 1 + 1 szóra nem áll meg, eredményt nem szolgáltat. ★


3.10. példa - Unáris számok szorzása

Adjon meg olyan Markov algoritmust, amely az 1 m *1 n bemenetre 1 mn kimenettel áll meg!

Megoldás:

W=({1,*,a,b},H,H 1), ahol H a következő:

1. *11 → a*1, 2. *1 → a, 3. 1a  → a1b, 4. ba → ab,

5. b1 →  1b, 6. a1 → a, 7. ab → b, 8. b → 1. H1=∅. ★


3.11. példa - Feladat - Legnagyobb közös osztó előállítása

Legyen W = ( { a , b, c, d , e, & }, { acca, a & a  → c & , a & → & d , da , ce , ea, & → λ }, ∅ ) (azaz H 1 ebben a feladatban is üres halmaz) normál algoritmus. Bizonyítsuk be, hogy tetszőleges i, j pozitív egész számpárra a i & a j W a k , ahol k a legnagyobb közös osztója i - nek és j - nek. ★


3.12. példa - Bináris szó rendezése

Adjon meg olyan Markov algoritmust, amely egy bemenő bináris szó esetén
annyi 1-est, majd annyi 0-ást ír, amennyi a bemenő szóban van!
Például: 001011011 bemenetre 111110000 szót adja eredményül.

Megoldás:

Egyik lehetséges megoldás a következő:

W=({0,1},{01 10}, ∅ ). Az algoritmus a buborékrendezést valósítja meg. Ugyanez a példa három számjegy esetén: W=({0,1,2},{01 10, 02 →  20, 12 →  21}, ∅ ). ★


3.13. példa - Bináris szó tükrözése

Adjon meg olyan Markov algoritmust, amely egy bemenő bináris szó tükörképét adja eredményül!
Például: 0110011 bemenetre 1100110 végeredményt ad.

Megoldás: Egy lehetséges algoritmus a következő: W=({0,1,X,Y,U,V,Z},H,H
               1),
ahol H elemei:
1. Y0 → 0Y, 2. Y1 →  1Y, 3. Y → Z, 4. UZ → Z0, 5. VZ → Z1,
6. U0 → 0U, 7. U1 → 1U, 8. V0 → 0V, 9. V1 → 1V, 10. X0 → XU,
11. X1 → XV, 12. XZ → λ, 13. λ → XY.
H
               1={XZ → λ}.
Az algoritmus a következőképpen működik:

  1. A bemenő szó elejére írja XY-t.

  2. Y-t elvisszük a szó végére és átírjuk Z-re.

  3. Ha az X utáni első számjegy 1, akkor V-t írunk helyette.

  4. Ha az X utáni első számjegy 0, akkor U-t írunk helyette.

  5. U-t vagy V-t elvisszük a szó végére.

  6. Ha a Z elé U kerül, akkor 0-t írunk Z után, és ha van még szám X és Z közt, akkor vissza a 3-as pontra.

  7. Ha a Z elé V kerül, akkor 1-t írunk Z után, és ha van még szám X és Z közt, akkor vissza a 3-as pontra.

  8. XZ törlése.


3.14. példa - Bináris szó megegyező végeinek törlése

Adjon meg olyan Markov algoritmust, amely egy bemenő bináris szó első és utolsó karakterét
addig törli, ameddig azok megegyeznek!
Például: 10110001 esetén a kimenet 1100.

Megoldás: Egy algoritmus lehet ez: W=({0,1,X,Y,U,V,W},H,H
               1), ahol H elemei:
1. 0Y → Y0, 2. 1Y  → Y1, 3. 0W → W0, 4. 1W → W1, 5. XY0 → X,
6. XY1 → X, 7. XW0 → 0, 8. XW1 → 1, 9. U0 → 0U, 10. U1 → 1U,
11. V0 → 0V, 12. V1 → 1V, 13. 0U → Y, 14. 1U → W1, 15. 1V → Y,
16. 0V → W0, 17. X1 → X1W, 18. X0 → X0U, 19. λ → X

               H
               1={XW0 → 0, XW1 → 1 }.
Az algoritmus a következőképpen működik:

  1. A bemenő szó elejére ír egy X-et.

  2. Ha az első számjegy 0, akkor U-t írunk utána.

  3. Ha az első számjegy 1, akkor V-t írunk utána.

  4. U-t vagy V-t elvisszük a szó végére.

  5. Ha az utolsó jegy 0 és U került mellé, vagy ha 1 és V, akkor ezek helyére Y-t írunk.

  6. Ha az utolsó jegy 1 és U került mellé, vagy ha 0 és V, akkor ezek helyére W-t írunk és visszaírjuk az utolsó jegyet.

  7. Y-t vagy W-t az elejére visszük.

  8. Ha az X után Y kerül, akkor az Y-t és az első számjegyet töröljük, és vissza a 2. lépésre.

  9. Ha az X után W kerül akkor töröljük XW-t és megállunk.


3.15. példa - Bináris szám növelése 1-gyel

Adjon meg olyan Markov algoritmust, amely egy bemenő bináris szám esetén
eggyel nagyobb bináris számot szolgáltat eredményül!

Megoldás: W=({0,1,X,Y},H,H
               1), ahol H elemei:
1. X1 → 1X, 2. X0 → 0X, 3. X → Y, 4. 0Y → 1,
5. 1Y → Y0, 6. Y → 1, 7. 1 → X1.
H
               1={0Y → 1, Y → 1}.
Az algoritmus működése:

  1. A szó elejére X-et írunk.

  2. X-et a szó végére visszük és Y-ra cseréljük.

  3. Y előtt 0 van, 1-esre írjuk és kész vagyunk.

  4. Y előtt 1 van, 0-ra írjuk és Y-t írunk elé. Vissza a 3-as pontra.

  5. Ha Y előtt nincs semmi, akkor 1-esre írjuk át.


3.16. példa - Unáris szám bináris alakja

Adjon meg olyan Markov algoritmust, amely 1
                  n
               
 bemenetre az n szám bináris alakját adja eredményül!

Megoldás:W=({0,1,X,Y},H,H
               1), ahol H elemei:
 1. 0Y → 1, 2. 1Y → Y0, 3. Y → 1, 4. X1 → YX, 5. X → λ,
 6. λ → 0X
 
               H
               1={X → λ}
 Az algoritmus lépései:

  1. Az 1-esek elé 0X-et ír.

  2. X1-et YX-re cseréli.

  3. Y előtti bináris számot növeli eggyel és Y-t törli.

  4. Ha van X után 1-es vissza 2-es pontra.

  5. Törli X-et.


3.17. példa - Bináris szám csökkentése 1-gyel

Adjon meg olyan Markov algoritmust, amely egy bemenő bináris szám esetén
eggyel kisebb bináris számot ad eredményül!

Megoldás: W=({0,1,X,Y},H,H
               1), ahol H elemei:
1. X1 → 1X, 2. X0 → 0X, 3. X → Y, 4. 1Y → 0,
5. 0Y → Y1, 6. Y → λ, 7. λ → X, és a záróhelyettesítés:
H
               1={Y → λ}.
Az algoritmus működése:

  1. A szó elejére X-et írunk.

  2. X-et a szó végére visszük és Y-ra cseréljük.

  3. Y előtt 1 van, 0-ra írjuk és kész vagyunk.

  4. Y előtt 0 van, 1-re írjuk, és Y-t írunk elé.

  5. Ha Y előtt nincs semmi, akkor töröljük Y-t, és kész vagyunk.


3.18. példa - Bináris szám unáris alakja

Adjon meg olyan Markov algoritmust, amely egy bemenő bináris szám unáris alakját adja vissza!

Megoldás:W=({0,1,X,Y,Z,V},H,H
               1), ahol H elemei:
1. X1 → 1X, 2. X0 → 0X, 3. X → Y, 4. 1Y → 0Y1, 5. 0Y → Z1V1, 6. 0Z → Z1,
7. 1Z → λ, 8. Z → λ, 9. V → Y, 10. Y → λ, 11. λ → X, és
H
               1={Y → λ }  záróhelyettesítés.
Az algoritmus lépései:

  1. A szó elé X-et ír.

  2. X-et a végére viszi és Y-ra cseréli.

  3. Y előtti bináris számot csökkenti, utáni unárist növeli eggyel.

  4. Ha van Y előtt számjegy, akkor vissza 2-ra.

  5. Törli Y-t.

(A feladatot úgy is meg lehetett volna oldani, hogy a bináris szóból balról jobbra haladva törlünk egy elemet, majd egy elszeparáló szimbólum után lévő 1-eseket duplázzuk, és a törölt elemtől függően vagy adunk hozzá egyet vagy nem, amíg a bináris szám el nem fogy.) ★


Amint láttuk a formális rendszereket algoritusok megadására is használhatjuk, ha egyértelműen megadjuk hogy adott lépésben melyik szabályt és hol kell alkalmazni. Ezzel szemben a generatív rendszerek teljesen nemdeterminisztikusak, általában nem csak az telejsül, hogy több alkalmazható szabály közül választunk, de az alkalmazás helye is lehet többféle. A következő fejezetben a generatív rendszerekből származtatott generatív nyelvtan fogalmát ismertetjük, mely e jegyzet egyik legfontosabb központi fogalma.