Számítástudomány Gyakorlati Jegyzet I. - Reguláris Nyelvek Hajgató Tamás 2014 Lektorálta: Dr. Iván Szabolcs Ezen oktatási segédanyag elkészítése a TÁMOP 4.2.4.A/ 2 - 11 - 1 - 2012 - 0001 azonosító számú Nemzeti Kiválóság Program - Hazai hallgatói, illetve kutatói személyi támogatást biztosító rendszer kidolgozása és működtetése országos program című kiemelt projekt keretében zajlott. A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg.
A Motiváció Kávéautomata VS Pacman Tegyük fel, hogy adott egy kávéautomata, mely 100 Ft-osokat és 50 Ft-osokat fogad el. Egy pohár kávé ára 150 Ft. Egy pohár tea ára 100 Ft. Amint 150 Ft-ot bedobtunk az automata nem engedi, hogy több pénzt bedobjunk, csak azt engedi, hogy kiválasszuk, hogy kávét vagy teát kérünk. Hogyan lehetne ezen automata működését modellezni? Például így:
A pacman játék egy labirintusban zajlik. A labirintust szellemek lakják, melyek véletlenszerű mozgást végeznek. Továbbá, a labirintusban bogyók illetve szuperbogyók vannak elhelyezve. A játékos célja az, hogy pacman-t a labirintuson keresztül vezérelje úgy, hogy az minél több bogyót megegyen és ne találkozzon szellemmel. Ha pacman szuperbogyót eszik, akkor ennek hatására egy rövid ideig a szellemeket is megeheti. A szellemek viselkedését leíró mesterséges intelligenciának tehát négy lehetséges állapota van: 1
1. véletlenszerű bolyongást végez; 2. pacman-t üldözi, amikor látja; 3. pacman elől menekül, amikor az szuperbogyót evett; 4. visszatér a szellembázisra, hogy regenerálódjon egy traumatikus élmény után. Hogyan lehetne ezen mesterséges intelligencia működését modellezni? Hát, mondjuk így:
A közös a kávéautomatában és pacman-ben az, hogy címkézett gráfokkal lehet modellezni bizonyos ágensek működését. Ilyen gráfokkal, tulajdonságaikkal fogunk foglalkozni.
A Módszer A való életben ha valakivel vitatkozunk, könnyen előfordulhat, hogy ahelyett, hogy arról lenne szó, hogy mi hogyan működik , vagy hogy mi hogyan van valójában, a vita egy pont után önértékelési kérdésbe csap át. Azaz valamelyik félnek kell , hogy igaza legyen, mert különben rosszul fogja érezni magát, mert nem tudja feldolgozni azt, hogy tévedett. Valaki például próbálhat úgy védekezni, hogy módosítja a szavak jelentését, majd úgy állítja be, hogy azt nem úgy értette, az alatt valami mást értett , azok a szavak nem azt jelentik . Hogy ezt elkerüljük szükségünk lesz definíciókra : meg kell egyeznünk, hogy mely szavak pontosan mit jelentenek. Azt is csinálhatja valaki, hogy annyit beszél, hogy ne hagyja a másikat szóhoz jutni vagy olyan hangsúlyt használ a véleménye hangoztatásához, mintha valami nagy bölcsességet mondana. Ekkor valójában pöffeszkedően tekintélyesebbnek állítja be magát vitapartnerénél , hogy ne legyen szabad kritizálni azt, amit mond. Hogy ezt elkerüljük, kifejezetten támogatni fogjuk azt, ha valaki kételkedik, kérdéseket tesz fel, kritizál. Esetleg csinálhatja azt valaki, hogy gyorsan tereli a témát, hogy ne derüljön ki, hogy nincs igaza. Ezt is csak azért teszi, mert bizonytalannak érzi magát - úgy érzi, hogy nincs igaza. Hogy ezt elkerüljük, kifejezetten támogatni fogjuk azt, ha valaki teljesen, a legapróbb részletekig elmenően végiggondol valamit, ha részletkérdésekkel szöszmötöl. Ha vitapartnerünk már mindegyik efféle módszert bevetette és még mindig nem nyerte meg a vitát, akkor a végső védekezésképp lemond az egész álláspontjáról és úgy állítja be, mintha a vita központi kérdése érdektelen lenne a számára. 2
Hasonlóan, ahogy a bukásra álló diák is úgy próbál meg védekezni, hogy bemagyarázza saját magának, hogy értéktelen az egész amit tanítanak - így valójában tehát az az okosabb, aki nem tanulja meg az anyagot.1 Ilyen esetekben sokszor arról van szó, hogy valaki emberileg nem elég erős ahhoz, hogy vitatkozni lehessen vele, ezért az érdemi vita helyett levegőbe beszélés történik. De ha bármi olyasmit akarunk csinálni, ami a valóságban is működik, ragaszkodni kell hozzá, hogy egy vita soha ne csapjon át önértékelési kérdésbe és mindig felfedezzük azt, hogy hogyan is van valami, ne pedig megszavazzuk, vagy előre eldöntsük azt, csak az érzéseinkre hagyatkozva. A gyakorlat során megállapítjuk majd, hogy a definícióinkat használva milyen állítások igazak azaz tételeket fogunk felfedezni, feladatokat megoldani.
Első gyakorlat Nyelvek, szavak, műveletek rajtuk Definíció: Ábécének nevezzük szimbólumoknak egy tetszőleges, véges, nemüres halmazát. Példa: Σ = {a, b, c} egy ábécé. Σ = {a} is ábécé. ∅ nem ábécé. Definíció: Legyen Σ egy ábécé. Szavaknak nevezzük a Σ elemeiből képzett a1a2 an alakú sorozatokat, ahol a1, a2, , an a Σ elemei és n > 0. Az n = 0 esetén kapott szót üres szónak hívjuk és ε-al jelöljük. Példa: Legyen Σ = {a, b, c} ábécé, ekkor például aaabca, aa, c, abc, ε szavak.
Definíció: Legyen Σ egy ábécé. A Σ elemiből képezhető összes szó halmazát Σ∗-gal jelöljük. Tehát Σ∗ = {a1a2 an |n > 0 és a1, a2, , an ∈ Σ}.2 Definíció: Legyenek u és v szavak. A v szó u után írásából kapott szót uv-vel jelöljük és az u és v konkatenációjának nevezzük. Példa: Az aaabca és a cc konkatenációja aaabcacc. Az aaabca és ε konkatenációja aaabca. A cc és az aaabca konkatenációja ccaaabca. Az ε és ε konkatenációja ε.
Definíció: Legyen w ∈ Σ∗ és n > 0. Ekkor w n-el jelöljük azt a szót, amelyet w n-szeri konkatenációjával kapunk. Tehát w 2 = ww és w 3 = www. Speciálisan3 : w 0 = ε. Példa: a3 = aaa, (ab)2 = abab, (abb)0 = ε.
Észrevehető, hogy a konkatenáció asszociatív , azaz (uv)w = u(vw) minden u, v, w ∈ Σ∗ szavakra. Továbbá ε egységelem a konkatenációra nézve, azaz εv = v és vε = v minden v ∈ Σ∗ szóra. 1. Gondoljunk bele, hogy milyen lenne az élet, ha senki sem foglalkozna tudománnyal. Nem lenne internet, hűtőszekrény, védőoltás, antibiotikum, stb. Számítástudomány nélkül pedig nehézségekbe ütközne programozási nyelveket tervezni, szintaktikus elemzőket ill. fordítóprogramokat írni. Vagy egy olyan programot, amely leellenőrzi, hogy egy repülőgépforgalom irányító rendszerben vagy egy új processzorban végtelen időn belül bekövetkezhet-e hiba. Ez utóbbival foglalkozik a modellvizsgálat, de addig nem jutunk el a kurzuson, hogy azt tárgyaljuk. 2. Σ∗ való jában a Σ által szabadon generált szabad monoid. Csak mondom. 3. Így lehet megjegyezni: wn : a w szót n-szer írjuk le. Tehát, w 0 : a w szót 0-szor írjuk le.
3
Feladat: Mely x ∈ {a, b}∗ szavakra igaz, hogy ax = xa ?
Hogyan fogjunk hozzá egy ilyen feladat megoldásához? Először is vegyük észre, hogy nem a feladat nem azt kéri, hogy mutassunk olyan x szót, amelyre a x = x a, hanem azt kéri, hogy mutassuk meg az összeset !
Tippek: Lehet választani: 1. x = anbm, minden n, m > 0-ra, 2. x = bman, minden n, m > 0-ra, 3. x = an, minden n > 1-re, 4. x = an, minden n > 0-ra. Melyik lehet a megoldás? 1. Legyen n = m = 1. Ekkor x = a1b1 = ab. Viszont ekkor ax = aab és xa = aba. Tehát ax xa. Ez a lehetőség nem megoldás. 2. Hasonlóan, legyen m = n = 1. Ekkor x = b1a1 = b a. Viszont ekkor a x = a b a és x a = b aa. Tehát ax xa. Ez a lehetőség sem megoldás. 3. Legyen x = an, valamilyen n > 1-re. Ekkor a x = an+1 = x a. Jónak tűnik, de megadtuk az összes megoldást? Mi van akkor, ha n = 0? Tehát ha x = a0 = ε akkor ax = a = x a. A 3-mal a gond az, hogy nem adtuk meg az összes megoldást. 4. Ez már jól néz ki, de honnan is tudhatnánk biztosan, hogy megadtuk az összes megoldást? Csak mert ezúttal úgy látszik , még nem biztos, hogy az összes megoldást megadtuk, nem?
Meg kell tanulnunk, hogy hogyan gondolkodjunk úgy, hogy ha el kell dönteni valamiről, hogy igaz-e, helyes eredményre jussunk. Csináljuk azt, hogy állítások egy olyan sorozatát készítjük el, hogy minden állításra igaz legyen, hogy: beláttuk már, hogy igaz; vagy annyira elemi állítás, amelynek érvényességét közvetlenül le lehet ellenőrizni; vagy logikusan következik a megelőző állításokból. Amire most szükségünk van az egy olyan gondolatmenet, amely igazolja, hogy a 4-es lehetőség felsorolja az ax = xa egyenlet *összes* megoldását. (Itt x a változó. ) Ennyi az egész:
Megoldás: Ha x = an, valamilyen n > 0-ra, az egyenlőség fennáll. Ha viszont x-ben szerepel b betű, akkor ax-ben az első b betű eggyel jobbra lesz majd, mint xa-ban. Tehát x ∈ {a}∗. Vagyis a helyes megoldás 4.
Kész. Könnyű volt? Próbáljuk megtanulni az efféle gondolkodásmódot - még akkor is, ha nehezebb, mint ráérezni a megoldásra, vagy elhinni valamiről, hogy igaz! 4
Feladat: Mely x ∈ {a, b}∗ szavakra igaz, hogy a) ax = xb ? b) axb = xab ? c) xbx = xxb ? d) xx = x ? Megoldás: a) Tetszőleges x-re a bal oldalon eggyel több a-betű szerepel, mint a jobb oldalon, tehát ennek az egyenletnek nincs megoldása. b) Vegyük észre, hogy a x b = x a b akkor és csak akkor igaz, ha a x = x a, ezt pedig már megoldottuk. c) Vegyük észre, hogy x b x = x x b akkor és csak akkor igaz, ha b x = x b igaz. Egy hasonlót pedig már megoldottunk: x ∈ {b}∗. d) Bármely x-re az egyenlet bal oldalán kétszer annyi betű szerepel, mint a jobb oldalon. Tehát ez az egyenlet csak x = ε esetében lehet igaz... és ebben az esetében igaz is.
Definíció: Legyen Σ egy ábécé. Σ∗ részhalmazait nyelveknek hívjuk. Példa: Legyen Σ = {a, b}. {a, aa a, a b a, ε} egy nyelv. ∅ is egy nyelv. Σ∗ is egy nyelv. {an |n prím } egy nyelv. {a, aba, {aa}} viszont nem nyelv. Miért? Mert {aa} Σ∗. Definíció: Az L1 és L2 nyelvek konkatenáltja az L1 · L2 nyelv, melyet úgy kapunk, hogy az összes L1-beli szót az összes L2-beli szóval minden lehetséges módon konkatenáljuk. Azaz: L1 · L2 = {vw |v ∈ L1, w ∈ L2}.
Példa: {aa, ab} · {a} = {aaa, aba}, {aa, ab} · {ε, a} = {aa, ab, aaa, aba}, ∅ · {ε, a} = ∅. Továbbá {an |n > 0} · {bm |m > 0} = {an bm |n > 0, m > 0}.
Vegyük észre, hogy a konkatenáció nyelvek esetében is asszociatív és egységelemes, az egységelem a csak az üres szót tartalmazó nyelv: {ε}. Az üres nyelv pedig zéruselem, azaz ∅ · L = ∅ = L · ∅.
Definíció: Legyen L egy nyelv. konkatenálásával kapunk.
Ekkor Ln jelenti azt a nyelvet, melyet L n-szeri
Példa: {ab}2 = {abab}, {a, ε}2 = {aa, a, ε}, {a, b}3 = {aaa, aab, aba, baa , abb, bba, bab, bbb}. Továbbá minden L nyelvre igaz, hogy L0 = {ε}. Tehát ∅0 = {ε}.
Definíció: Az L nyelv Kleene-iteráltja a következőképpen definiált L∗ nyelv: 5
L∗ = Példa: {a}∗ =
S
k>0
{a}k. {ab, c}∗ =
S
k>0
S
k>0
Lk
{ab, c}k.
Speciálisan: Σ Kleene-iteráltja Σ∗, azaz az összes szavak halmaza.
Feladat: Mutassunk olyan L nyelvet, amelyre L∗ = L ! S S Megoldás: Például {ε}∗ = k>0 {ε}k = k>0 {εk } = {ε}. Feladat: Mutassunk olyan L nyelvet, amelyre ε L ∗ ! Vagy mutassunk olyat, amelyre L∗ = ∅ ! Megoldás: Ilyen nincs, hiszen {ε} = L0 ⊆ L∗. Feladat: Igaz-e minden L nyelvre, hogy (L0)∗∗ = L0 ? Megoldás: Az előző két feladat megoldásából következik. Egyrészt L0 = {ε}, másrészt {ε}∗ = {ε}.
Feladat: Igaz-e minden L nyelvre, hogy L∗ = L∗∗ ? Megoldás: Igaz. Ennek igazolásához szükség lesz a bónusz anyagra:
Bónusz anyag5 Feladat: Mutassuk meg, hogy x ∈ L∗ akkor és csak akkor, ha létezik m > 0 és x1, , xm ∈ L úgy, hogy x = x1x2 xm. Idézzük fel, hogy ha A, B valamilyen állítások, akkor az “A akkor és csak akkor, ha B” azzal ekvivalens, hogy: “(ha A akkor B) és (ha B akkor A)” ami az A ↔ B és (A → B) ∧ (B → A) igazságtáblázatainak összehasonlításából látszik. Tehát a feladat megoldásához elég az (A → B), (B → A) állításokat igazolni. Azaz ezen feladat esetében azt kell belátni, hogy “ ha x ∈ L∗ , akkor létezik m > 0 és x1, , xm ∈ L úgy, hogy x = x1x2 xm ”, valamint azt, hogy “ ha létezik m > 0 és x1, , xm ∈ L úgy, hogy x = x1x2 xm, akkor x ∈ L∗ ”. Megoldás: Tegyük fel, hogy létezik m > 0 és x1, , xm ∈ L úgy, hogy x = x1x2 xm. Ekkor nyilván x ∈ Lm. S Mivel L∗ = k>0 Lk, ezért Lm ⊆ L∗, tehát x ∈ L ∗. S Most tegyük fel, hogy x ∈ L∗. Mivel L∗ = k>0 Lk, van olyan m > 0, hogy x ∈ Lm. Ekkor viszont vannak olyan x1, x2, , xm ∈ L szavak, hogy x = x1x2 xm.
5. Gyakorlaton nem tértünk ki rá. Azért nem árt elolvasni.
6
Feladat: Igaz-e minden L nyelvre, hogy L∗∗ = L∗ ? Megoldás: Igaz. A Kleene-iterált definíciója miatt L∗ ⊆ L∗∗. Most belátjuk, hogy L∗∗ ⊆ L∗ is teljesül, ezekből L∗ = L∗∗ következik. Az előző feladat alapján x ∈ L∗∗ akkor és csak akkor, ha létezik m > 0 és x1, hogy x = x1x2 xm.
, xm ∈ L∗ úgy,
Megint, az előző feladat m-szeri alkalmazásával adódik, hogy ekkor léteznek ℓ1, ., ℓm > 0 számok és x1,1, x1,2, , x1,ℓ1 ∈ L, x2,1, x2,2, , x2,ℓ2 ∈ L, ..., xm,1, xm,2, , xm,ℓm ∈ L szavak úgy, hogy x1 = x1,1 x1,2 x1,ℓ1,
xm = xm,1xm,2 .xm,ℓm. Viszont ekkor x = x1x2 xm = x1,1 x1,2 x1,ℓ1 xm,1 xm,2 xm,ℓm. S De ekkor x ∈ Lℓ1 +ℓ2 + +ℓm. Mivel L∗ = k>0 Lk, következik, hogy x ∈ L∗. Mivel x megválasztása tetszőleges volt, L∗∗ ⊆ L∗ teljesül.
Feladat: Igaz-e, hogy tetszőleges L1, L2 ⊆ {a, b}∗ nyelvekre a) (L1 ∪ L2)∗ = L∗1 ∪ L∗2 ? b) (L1 ∩ L2)∗ = L∗1 ∩ L∗2 ? c) L∗1 · (L2 · L∗1)∗ = (L∗1 · L2)∗ · L∗1 ? d) (L∗1 · L2)∗ · L∗1 = (L1 ∪ L2)∗ ? e) (L∗2 · L1)∗ · L∗2 = L∗1 · (L2 · L∗1)∗ ? Megoldás: a) Nem igaz. Például ha L1 = {a} és L2 = {b}, akkor ab eleme a bal oldalnak, a jobbnak viszont nem. b) Nem igaz. Ha L1 = {a} és L2 = {aa}, akkor a bal oldal csak az ε szót tartalmazza, a jobb oldal pedig az {aa}∗ nyelv. c) Igaz. Mivel L∗1 · (L2 · L∗1)∗ = (L∗1) ·
S
m>0
(L2 · L∗1)m
ezért egy x szó akkor és csak akkor van benne L∗1 · (L2 · L∗1)∗-ban, ha létezik m > 0 úgy, hogy x felírható wv1 x1 vmxm alakban, ahol w, xi ∈ L∗1, vi ∈ L2 minden i ∈ {1, , m}-re. Mivel (L∗1 · L2)∗ · L∗1 =
S
m>0
(L∗1 · L2)m · L∗1
egy x szó akkor és csak akkor van benne (L∗1 · L2)∗ · L∗1 -ban, ha létezik m > 0 úgy, hogy x felírható x1 v1 xm vm w alakban, ahol w, xi ∈ L∗1, vi ∈ L2 minden i ∈ {1, , m}-re. 7
Figyeljük meg, hogy ezen feltételek ekvivalensek, ebből adódik az egyenlőség. d) Igaz. Csak hasonlítsuk a következőt az előző ponthoz. Mivel minden szó véges hosszú, egy x szó akkor és csak akkor van benne (L1 ∪ L2)∗-ban, ha létezik m > 0 úgy, hogy x felírható wv1 x1 vmxm alakban, ahol w, xi ∈ L1, vi ∈ L2 minden i ∈ {1, , m}-re. Mivel L1 ⊆ L∗1, az állítás adódik. e) Igaz. Következik az előző két pontból és abból, hogy ∪ kommutatív, azaz L1 ∪ L2 = L2 ∪ L1.
Második gyakorlat Determinisztikus automaták Idézzük fel, hogy nyelv alatt valamely ábécé feletti szavak halmazának egy részhalmazát értjük. Tehát, ha Σ egy ábécé és L ⊆ Σ∗, akkor azt mondjuk, hogy L egy nyelv . Nyelveket különféleképpen meg lehet adni. Ha véges, akkor egyszerűen felsoroljuk az elemeit. Például így: L = {aa, ababa, ε} Node mi a helyzet akkor, ha L nem véges? Meg lehet adni végesen egy nem véges nyelvet? Milyen módon? Ez ugye akkor kezd érdekes lenni, ha az ábécénk például a bináris ábécé: {0, 1}. Ekkor ugyanis a nyelveink “bitsztringeket” fognak tartalmazni! Meg lehet adni “végtelen sok” információt valahogyan véges módon? ——————————————————————————————————————————— A véges (determinisztikus) automata definíciója: Véges automata alatt egy (Q, Σ, δ, q0, F ) rendezett ötöst értünk, ahol •
Q egy véges(!) halmaz, az állapotok halmaza,
•
Σ egy ábécé, az inputábécé,
•
δ: Q × Σ → Q leképezés, az átmenetfüggvény,
•
q0 ∈ Q a kezdőállapot,
•
F ⊆ Q a végállapotok halmaza.
——————————————————————————————————————————— Megjegyzés: Figyeljük meg, hogy δ leképezés, azaz teljesen definiált! (Ez ugye6 azt jelenti, hogy minden (q, a) ∈ Q × Σ -ra meg van adva, hogy δ(q, a) ∈ Q melyik állapot!) ——————————————————————————————————————————— Egy véges automatát meg lehet adni címkézett, irányított gráfként reprezentálva is. Legyen (Q, Σ, δ, q0, F ) egy véges automata. Az automata gráfjának csúcshalmaza Q, élei pedig: minden a ∈ Σ-ra és minden q, p ∈ Q-ra: az automata gráfjában szerepeljen egy a-val címkézett q
6. Diszkrét Matek I.
8
p él
⇔
δ(q, a) = p
Példa: (Q, Σ, δ, q0, F ) egy véges automata, ahol Q = {q0, q1, q2}
Σ = {a, b}
F = {q1}
valamint δ: Q × Σ → Q a következő táblázattal adott: δ q0 q1 q2
a q0 q0 q2
b q1 q2 q0
——————————————————————————————————————————— Vegyünk egy (Q, Σ, δ, q0, F ) véges automatát. Most definiálni fogunk egy δ-től függő δ ∗: Q × Σ ∗ → Q leképezést. A definíció a következő. Legyen minden q ∈ Q-ra, minden a ∈ Σ-ra és minden w ∈ Σ∗-ra: δ ∗(q, aw) = δ∗(δ(q, a), w) és δ ∗(q, ε) = q. ———————————————————————————————— Ennyi a definíció. Most pedig megállapítunk valamit a δ∗ leképezésről.
Feladat: Egészítsük ki az alábbi összefüggést úgy, hogy igaz legyen a következő állítás:
Minden w ∈ Σ∗-ra és minden q, p ∈ Q-ra: az automata gráfjában
⇔
δ ∗(q, w) = p
Ellenőrizzük le néhány konkrét példára, hogy igaz-e az így kapott állítás! ——————————————————————————————————————————— A δ ∗ függvény segítségével definiálni tudjuk a (Q, Σ, δ, q0, F ) automata által felismert nyelv fogalmát. A (Q, Σ, δ, q0, F ) automata a következő nyelvet ismeri fel: {w ∈ Σ∗ |δ ∗(q0, w) ∈ F } ———————————————————————————————— 9
Ennyi a definíció7 . Próbáljuk meg értelmezni és mondjuk ki hangosan, hogy mit jelent. Én ezt így fogalmaznám meg: Egy automata által felismert nyelvben pontosan azon szavak vannak, amelyek előállnak úgy, hogy valamelyik, az automata kezdőállapotából egy végállapotába vezető séta éleinek címkéit összeolvassuk. Megjegyzés: Ha az automatát M -el jelöljük, akkor az általa felismert nyelvet L(M )-mel jelöljük. Figyeljük meg, hogy egy adott M automata pontosan egy nyelvet ismer fel. Nem kettőt, egyet. Azt is figyeljük meg, hogy egy nyelv felismerhető több, különböző automatával is. ——————————————————————————————————————————— Feladat: Adjunk meg egy automatát, amely az L ⊆ {a, b}∗ nyelvet ismeri fel, ahol... a) L = {abna | n > 0}, b) L = {an | n > 0}, c) L = {an | n > 0}, d) L = {w | |w|a ≡ 0 ( mod 3)}, e) L = {w | |w|a ≡ 1 ( mod 5)}, f) Lk = {w | |w|a = k}, ahol k > 0 konstans, g) L = {aaba , ε, ba}.
Megoldás: a)
b)
7. A δ ∗ definíciója is jár hozzá.
10
c)
d)
e)
11
f) A következő k = 2 -re megoldás:
Próbáljuk meg ez alapján felírni úgy, hogy k egy paraméter! g)
Feladat: Igaz-e, hogy minden véges nyelv felismerhető véges automatával?8
Feladat: Tegyük fel, hogy az automata állapotainak halmaza végtelen is lehet. Igaz-e ekkor, hogy minden nyelv felismerhető végtelen sok állapottal rendelkező automatával?
Megjegyzés: Egyébként például az {anbn |n > 0} nem ismerhető fel véges automatával. Majd a hatodik gyakorlaton látni fogjuk, hogy miért.
Tétel: Legyen M = (Q, Σ, δ, q0, F ) egy determinisztikus véges automata9 és L ⊆ Σ∗ egy nyelv. M akkor és csak akkor ismeri fel L-et, ha M = (Q, Σ, δ, q0, F ) felismeri L-et. Itt F ⊆ Q az F halmaz Q-ra vett komplementere és L ⊆ Σ∗ pedig az L nyelv Σ∗-ra vett komplementere. 8. Az f) megoldásából induljunk ki. 9. Itt fontos az, hogy determinisztikus az automata és az is kell, hogy az átmenetfüggvény teljesen definiált legyen.
12
Bónusz anyag
Definíció: Legyenek (Q, Σ, δ, q0, F ) és (Q ′, Σ, δ ′, q0′ , F ′) véges automaták. Ezen automaták egy direkt szorzata a következő automata: (Q × Q ′, Σ, δ ′′, (q0, q0′ ), F ′′) ahol minden q ∈ Q, q ′ ∈ Q ′ és a ∈ Σ-ra: δ ′′((q, q ′), a) = (δ(q, a), δ ′(q ′, a)) valamint F ′′ ⊆ Q × Q ′ tetszőleges.
Tétel: Legyenek M és M ′ automaták és legyen M ′′ egy direkt szorzatuk. Ekkor - ha F ′′ = F × F ′ akkor L(M ′′) = L(M ) ∩ L(M ′); - ha F ′′ = (Q × F ′) ∪ (F × Q ′) akkor L(M ′′) = L(M ) ∪ L(M ′).
Feladat: Adjunk meg egy automatát, mely a következő nyelvet ismeri fel: L ′′ = {w ∈ {a, b, c}∗ | |w|a ≡ 0 (mod 2) vagy |w|a + |w|c < 2}. Megoldás: Megadunk egy M automatát, mely felismeri az L = {w ∈ {a, b, c}∗ | |w|a ≡ 0 (mod 2)} nyelvet, majd megadunk egy M ′ automatát, mely felismeri az L ′ = {w ∈ {a, b, c}∗ | |w|a + |w|c < 2} nyelvet. Az L ′′ nyelvet M és M ′ direkt szorzata ismeri fel, feltéve, hogy F ′′ = (Q × F ′) ∪ (F × Q ′)
Legyen M a következő:
Legyen M ′ a következő:
Ekkor M × M ′ a következő: 13
Az előző állítás alapján ekkor L ′′ = L(M ′′). A feladat kész. Feladat: Adjunk meg egy automatát, mely az {w | |w|a ≡ 0 ( mod 3)} − {w | |w|a = k } nyelvet ismeri fel. Megoldás: Hogy is csináljuk? Az uniót és a metszetet le tudjuk kezelni. Meg a komplementert is. A különbséget ki tudjuk fejezni a metszettel és a komplementerrel a dimatból jól ismert A−B =A∩B azonosságot használva, ahol A, B halmazok. Ezt pontosan kiírni házi feladat.
Harmadik gyakorlat Nemdeterminisztikus Automaták —————————————————————————————————————————–– A nemdeterminisztikus automata definíciója. Nemdeterminisztikus automata alatt egy M = (Q, Σ, δ, q0, F ) rendezett ötöst értünk, ahol Q, Σ, q0 és F ugyanazok, mint determinisztikus automata esetén, továbbá δ: Q × Σ → P (Q) egy leképezés (vagyis teljesen definiált), ahol P (Q) a Q részhalmazainak halmaza. ———————————————————————————————— Nemdeterminisztikus automatákat is meg lehet adni címkézett irányított gráfokkal. Legyen (Q, Σ, δ, q0, F ) egy nemdeterminisztikus automata. Az automata gráfjának csúcshalmaza Q, az élek pedig a következőképpen legyenek definiálva: minden a ∈ Σ-ra és minden q, p ∈ Q-ra: az automata gráfjában szerepeljen egy a-val címkézett q
p él
⇔
p ∈ δ(q, a)
———————————————————————————————— A különbség determinisztikus automata gráfjához képest az, hogy nemdeterminisztikus automata esetén egy állapotból egy betű hatására több állapotba is mehet él, vagy akár nullába. —————————————————————————————————————————–– Vegyünk egy (Q, Σ, δ, q0, F ) nemdeterminisztikus automatát. Most definiálni fogunk egy δ-tól függő 14
δ ∗: Q × Σ∗ → P (Q) leképezést. A definíció a következő: legyen minden q ∈ Q-ra, minden a ∈ Σ-ra és minden w ∈ Σ∗-ra: S δ ∗(q, aw) = p∈δ(q,a) δ ∗(p, w) és δ ∗(q, ε) = {q }. ———————————————————————————————— Megjegyzés: Namost, zavarodottságot okozhat, hogy kétszer definiáltuk δ ∗-ot. De vegyük észre, hogy egyszer determinisztikus automatákra definiáltuk, egyszer pedig nemdeterminisztikus automatákra. Ez kettő, különböző értelmezése a δ∗ jelölésnek - azaz kettő, különböző fogalom. Csak ugyanúgy jelöljük, hogy könnyebb legyen megjegyezni. Ugyanez a helyzet az automata által felismert nyelv fogalmával is. —————————————————————————————————————————– A δ∗ függvény segítségével definiálni tudjuk a (Q, Σ, δ, q0, F ) nemdeterminisztikus automata által felismert nyelv fogalmát. A (Q, Σ, δ, q0, F ) nemdeterminisztikus automata a következő nyelvet ismeri fel: {w ∈ Σ∗ |δ ∗(q0, w) ∩ F
∅}
Ennyi a definíció. Értelmezzük, mondjuk ki hangosan, hogy mit jelent. Ne a krix-kraxot mondjuk ki, hanem, hogy mit jelent. Én ezt így fogalmaznám meg: Egy nemdeterminisztikus automata által felismert nyelvben pontosan azon szavak vannak, amelyek előállnak úgy, hogy valamelyik, az automata kezdőállapotából egy végállapotába vezető séta éleinek címkéit összeolvassuk.
Feladat: Adjunk meg egy nemdeterminisztikus automatát, amely az L ⊆ {a, b}∗ nyelvet ismeri fel, ahol... a) L = {ab2na |n > 0} ∪ {ab2n+1aa|n > 0}, b) L = {uabav |u, v ∈ {a, b}∗}, c) L = {abnamb |n, m > 0} ∪ {abn am |n > 1, m ≡ 1 (mod 5)}. Megoldás: a) Erre kettő megoldást is adunk. Egyik:
15
Másik:
b)
c)
Intuitív magyarázat: mi a lényeges különbség determinisztikus és nemdeterminisztikus automata között? Egy determinisztikus automata egy q állapotból egy a betű hatására pontosan egy darab q ′ állapotba megy át. Azaz, δ: Q × Σ → Q egy leképezés, így δ(q, a) a Q egy eleme. Egy determinisztikus automata által felismert nyelv azon szavakból áll, amelyeket az automata feldolgoz úgy, hogy a feldolgozás végén végállapotba kerül. Ezzel szemben nemdeterminisztikus automata esetén δ: Q × Σ → P (Q). Így δ(q, a) egy részhalmaza Q-nak. δ(q, a) elemei azon állapotok, amelyekbe az automata átmehet a q-ból a betűt olvasva. Egy nemdeterminisztikus automata által felismert nyelv azon szavakból áll, melyeket fel tud dolgozni úgy, hogy a feldolgozás végén végállapotba kerüljön. Fontos! Az imént leírtak nem definíciók, csak intuitív magyarázat !10 A definíciót nézzük le az előadásfóliákról/jegyzetből/órán elmondtam! Csak akkor érthetjük meg! 10. Az egyik különbség a kettő között az, hogy ha a definíciót kell leírni akkor az intuitív magyarázat nulla pontot ér.
16
—————————————————————————————————————————–– A spontán átmenetekkel ellátott nemdeterminisztikus automata definíciója. Spontán átmenetekkel ellátott nemdeterminisztikus automata alatt egy M = (Q, Σ, δ, q0, F ) rendezett ötöst értünk, ahol Q, Σ, q0 és F ugyanazok, mint nemdeterminisztikus automata esetén, továbbá δ: Q × Σε → P (Q) egy leképezés (vagyis teljesen definiált), ahol P (Q) a Q részhalmazainak halmaza. Itt és ez a lényeg: Σε = Σ ∪ {ε}
Intuitív magyarázat: mi a lényeges különbség nemdeterminisztikus és spontán átmenetekkel ellátott nemdeterminisztikus automata között? Hát az, hogy az utóbbiban megengedettek az εátmenetek is. Vagyis nem csak betűvel, hanem ε-nal címkézett élek is szerepelhetnek a gráfjában. A spontán átmenetekkel ellátott automata által felismert nyelv fogalmát hasonlóan definiáljuk mint (spontán átmenetek nélküli) nemdeterminisztikus automata esetén: a kezdőállapotból végállapotokba vezető utakban szereplő élek címkéit olvassuk össze. ———————————————————————————————— Felmerül a kérdés, hogy minden nyelv, amely felismerhető spontán átmenetekkel ellátott nemdeterminisztikus automatával, felismerhető-e determinisztikus automatával; és fordítva. A válasz mindkettő esetben igen! Ha M egy nemdeterminisztikus automata és δ(q, a) minden esetben pontosan egyelemű, akkor ez az automata (lényegében) determinisztikus. Tehát a determinisztikus automaták pont azon nemdeterminisztikus automaták, melyekre igaz, hogy δ(q, a) pontosan egyelemű, minden q állapot és a betű esetén. Vagyis minden determinisztikus automata által felismerhető nyelv felismerhető nemdeterminisztikus automatával is.11 Minden nemdeterminisztikus automata tekinthető spontán átmenetekkel ellátott nemdeterminisztikus automatának, ahol δ(q, ε) = ∅ minden q állapot esetén. Vagyis minden nemdeterminisztikus automata által felismerhető nyelv felismerhető spontán átmenetekkel ellátott nemdeterminisztikus automatával is.
Fordítva: adott egy M spontán átmenetekkel ellátott nemdeterminisztikus automata. Az érdekel bennünket, hogy létezik-e egy olyan P (M ) determinisztikus automata, melyre igaz, hogy ugyanazt a nyelvet ismeri fel, mint M ...
...ami azt illeti, M alapján meg is lehet adni egy ilyen P (M )-et. Így:
Legyen M = (Q, Σ, δ, q0, F ) egy tetszőleges, spontán átmenetekkel ellátott nemdeterminisztikus automata. Továbbá, legyen P (M ) = (P (Q), Σ, δ ′, Q0, F ′), ahol Q0 = {q0} és F ′ = {X ∈ P (Q)|X ∩ F
∅},
′
δ : P (Q) × Σ → P (Q), δ ′(Y , a) =
S
q∈Y
δ(q, a),
11. δ(q, a) = p determinisztikus automatára ⇔ δ(q, a) = {p} nemdeterminisztikus automatára
17
ahol minden X ∈ P (Q)-ra X az X ε-lezárása:
X = X ∪ {q ∈ Q | létezik q ′ ∈ X, amelyből elérhető q; csak ε-átmeneteket használva}
Vagyis X -ot úgy kapjuk X-ből, hogy hozzávesszük X-hez azokat az állapotokat, amelyek εátmenetekkel elérhetőek valamely X-beli állapotból. Biztos mindenki érti, de csak hogy megjegyezzük még jobban leírom: S
q∈X
δ(q, a) a
S
q ∈X
δ(q, a) ε-lezárása.
Tétel: L(M ) = L(P (M )). Proof. Legyen w ∈ Σ∗. w hosszára való teljes indukcióval kell igazolni, hogy: minden S ∈ P (Q)-ra: δ ′∗(S , w) =
[
δ ∗(s, w)
(1)
s∈S
Ha w hossza 1, akkor w egyetlen betű. Ekkor viszont (1) éppen δ ′ definíciója. Most tegyük fel, hogy (1) teljesül minden n hosszú w szóra, ahol n > 1. Legyen a ∈ Σ, w ∈ Σ∗ és X ∈ P (Q). Tegyük fel, hogy w hossza n. Ekkor ∗
∗
δ ′ (X , aw) = δ ′ (δ ′(X , a), w) Értelmezzük a képletet apránként. Itt δ ′ a P (M ) automata átmenetfüggvénye. δ ′(X , a) az az állapot, amelybe P (M ) kerül az X állapotból a betű hatására. Az indukciós hipotézis miatt [
δ ′∗(X , aw) = δ ′∗(δ ′(X , a), w) =
δ(s, w)
s∈δ ′(X ,a)
δ ′ definíciója miatt pedig [ s∈δ ′(X ,a)
ahol
δ∗
[
δ∗(s, w) = s∈
S
q ∈X
δ ∗(s, w) δ(q,a)
definíciója miatt [ s∈
S
q ∈X
δ ∗(s, w) =
[
δ ∗(q, aw)
q ∈X
δ(q,a)
Ezzel igazoltuk (1)-et w hosszára való teljes indukcióval.
Mivel P (M ) determinisztikus, ezért ezen tétel alapján minden spontán átmenetekkel ellátott nemdeterminisztikus M automatához létezik olyan determinisztikus P (M ), hogy M ugyanazt a nyelvet ismeri fel, mint P (M ).
18
Példa: Legyen M = ({q0, q1}, {a, b}, δ, q0, {q0}), ahol b ε δ a q0 {q0, q1} {q0} ∅ q1 ∅ {q1} {q0}
Ekkor L(M ) = {a, b}∗ Továbbá P (M ) = (P ({q0, q1}), {a, b}, δ ′, Q0, F ′), ahol Q0 = {q0} = {q0}, ′
F = {{q1}, {q0, q1}} és P ({q0, q1}) = {∅, {q0}, {q1}, {q0, q1}}, δ ′({q0}, a) =
S
δ ′({q0}, b) =
q ∈{q0}
S
q ∈{q0}
δ ′(∅, b) = δ ′({q1}, a) = δ ′({q1}, b) =
S
S
δ(q, a) = δ(q0, a) = {q0, q1},
S
q∈∅
q∈{q1}
q ∈{q1}
δ(q, b) = δ(q0, b) = {q0}, δ(q, b) = ∅ = ∅,
δ(q, a) = δ(q1, a) = ∅ = ∅,
δ(q, b) = δ(q1, b) = {q1} = {q0, q1},
valamint δ ′({q0, q1}, a) =
S
q ∈{q0, q1}
δ(q, a) = δ(q0, a) ∪ δ(q1, a) = {q0, q1} ∪ ∅ = {q0, q1}
δ ′({q0, q1}, b) =
S
q ∈{q0,q1}
δ(q, b) = δ(q0, b) ∪ δ(q1, b) = {q0} ∪ {q1} = {q0, q1}.
és
Az előző tétel alapján ekkor L(M ) = L(P (M )). Azaz L(P (M )) = {a, b}∗.
Vegyük észre, hogy elég P (M )-nek az összefüggő részét venni, azaz azoktól az állapotoktól megszabadulhatunk, amelyek nem érhetőek el a kezdőállapotból.
Továbbá, ha megfigyeljük δ ′({q0, q1}, a) = δ ′({q0}, a) ∪ δ ′({q1}, a) és δ ′({q0, q1}, b) = δ ′({q0}, b) ∪ δ ′({q1}, b).
19
Hmm. Lemma. Legyen (Q, Σ, δ, q0, F ) egy spontán átmenetekkel ellátott nemdeterminisztikus automata és X , Y ⊆ Q. Ekkor X ∪Y = X ∪ Y . Bizonyítás vázlat. Figyeljük meg, hogy minden q ∈ Q-ra igaz, hogy: (q ∈ Q-hoz létezik q ′ ∈ X ∪ Y amelyből elérhető q csak ε-átmeneteket használva) akkor és csak akkor, ha ′
(q-hoz létezik q ∈ X, melyre igaz, hogy q ′-ből elérhető q csak ε-átmeneteket használva, vagy q-hoz létezik q ′ ∈ Y , melyre igaz, hogy q ′-ből elérhető q csak ε-átmeneteket használva)
Tehát az előző lemma alapján a példában δ ′({q0, q1}, a)-t nem kell kiszámítani, ha már megvan δ ′({q0}, a) és δ ′({q1}, a), mert δ ′({q0, q1}, a) =
S
q ∈{q0, q1}
δ(q, a) = δ(q0, a) ∪ δ(q1, a) = δ(q0, a) ∪ δ(q1, a) = δ ′({q0}, a) ∪ δ ′({q1}, a).
AHÁN! Tehát két dolgot jegyeztünk meg: 1. elég P (M ) összefüggő részét venni, 2. elég egyelemű X-ekre kiszámítani δ ′(X , a)-t, ebből meg lehet kapni tetszőleges X-ekre. Nézzük meg hát az előbbi példát ezt a két pontot észben tartva!
Az előző Példa, még egyszer: Legyen M = ({q0, q1}, {a, b}, δ, q0, {q0}), ahol b ε δ a q0 {q0, q1} {q0} ∅ q1 ∅ {q1} {q0}
Figyeljük meg, hogy determinisztikus automaták átmenetfüggvényeit is meg lehet adni táblázatos formában. Ezt fogjuk csinálni. Namost {q0} = {q0} lesz a kezdőállapota P (M )-nek, tehát a δ ′ átmeneti táblázatnak kell legyen egy ilyen sora: a b δ′ {q0} {q0, q1} {q0} A táblázat eddigi elemeit a következő egyenlőségek alapján töltöttük ki: 20
δ ′({q0}, a) = δ(q0, a) = {q0, q1}, δ ′({q0}, b) = δ(q0, b) = {q0}.
Látjuk, hogy a kezdőállapotból elérhető {q0, q1}, tehát bővítjük a táblázatunkat: δ′ a b {q0} {q0, q1} {q0} {q0, q1} {q0, q1} {q0, q1} Az új sor onnan jön, hogy δ ′({q0, q1}, a) = δ(q0, a) ∪ δ(q1, a) = {q0, q1}, δ ′({q0, q1}, b) = δ(q0, b) ∪ δ(q1, b) = {q0} ∪ {q0, q1} = {q0, q1}. Mivel nem keletkezett új állapot, ennyi. Véget ért az algoritmus. Az utolsó táblázattal megadott átmenetfüggvényű automata determinisztikus. Ezen automata állapotainak halmaza: {{q0}, {q0, q1}} ezek közül {q0} kezdőállapot12 {q0, q1} végállapot13 Továbbá, ezen automata ugyanazt a nyelvet ismeri fel, mint M és determinisztikus.
—————————————————————————————————————————— Megjegyzés. Ha valamiért időközben felvettük volna a {q1} állapotot is, a következő táblázatot kaptuk volna: δ′ a b {q0} {q0, q1} {q0} {q1} ∅ {q0, q1} melyet a következő sorok alapján töltöttünk volna ki δ ′({q1}, a) = δ(q1, a) = ∅ = ∅ δ ′({q1}, b) = δ(q1, b) = {q1} = {q0, q1} aztán felvéve végül a {q0, q1} állapotot ezt kaptuk volna a δ′ {q0} {q0, q1} {q1} ∅ {q0, q1} {q0, q1}
b {q0} {q0, q1} {q0, q1}
itt δ ′({q0, q1}, a) = δ ′({q0}, a) ∪ δ ′({q1}, a) = {q0, q1} ∪ ∅ 12. Q0 definíció ja 13. H definíció ja
21
δ ′({q0, q1}, b) = δ ′({q0}, b) ∪ δ ′({q1}, b) = {q0} ∪ {q0, q1} tehát a {q0, q1} sorát megkaptuk volna úgy, hogy elemenként összeúniózzuk a {q0} és a {q1} sorát. Ez a módszer általánosan is működik, az tehát ahhoz, hogy {q0, q1} sorát megkapjuk elég elemenként összeúniózni {q0} és {q1} sorait. Sokkal praktikusabb viszont az EREDETI táblázatban összeuniózni a sorokat és ott ε-lezárni, cellánként. Ebben a példában {q1} felvétele egy plusz állapotot jelentett volna, hiszen {q1} nem érhető el {q0}-ból. Fölösleges felvenni. Amit még meg akartam mutatni ezzel az az, hogy nem szabad elfelejteni ε-lezárni a halmazokat. Más automatához juthatunk:
amely ugyanazt a nyelvet ismeri fel ugyan, de többet dolgoztunk {q1} felvétele miatt. Azt még figyeljük meg, hogy amely automata az ábrán van az nem egy determinisztikus automata. Ugyanis az üres halmaz is egy állapot lesz, annak is ki kell tölteni a sorát a táblázatban.
Negyedik és ötödik gyakorlat Reguláris kifejezések Eddig automatáztunk, de most visszatérünk a kérdéshez, hogy hogyan lehet egy (esetleg nem véges) L ⊆ Σ∗ nyelvet véges eszközökkel megadni. Ezen célból definiáljuk a reguláris kifejezés fogalmát is. ——————————————————————————————————————————– A Σ ábécé feletti reguláris kifejezések halmaza az a legszűkebb H halmaz, melyre igaz, hogy: ∅ ∈ H, minden a ∈ Σ betűre:
a ∈ H,
minden R1, R2 ∈ H-ra: (R1 + R2), (R1 · R2), (R1)∗ ∈ H. ——————————————————————————————————————————– Vagyis reguláris kifejezést betűkből és az üres halmazból képezhetünk úgy, hogy össze + -ozunk kettőt, össze · -olunk kettőt, vagy meg ∗-ozunk egyet.
Legyen R egy Σ feletti reguláris kifejezés. Az R reguláris kifejezés által jelölt |R| ⊆ Σ∗ nyelv a következőképpen van definiálva: |∅| = ∅ |a| = {a} |(R1 + R2)| = |R1| ∪ |R2| |(R1 · R2)| = |R1| · |R2| |R∗1| = |R1|∗ ——————————————————————————————————————————– 22
Vagyis a + az uniót, a · a konkatenációt, a ∗
∗
pedig a Kleene-iterációt jelöli.
∗
Példa: (((a + b) · a) + ∅ ) reguláris kifejezés {a, b, c} fölött. Az általa jelölt nyelv pedig: |(((a + b) · a)∗ + ∅∗)| = |((a + b) · a)∗| ∪ |∅∗| = |((a + b) · a)|∗ ∪ |∅|∗ = {aa, ab}∗ mivel |∅|∗ =
S
k>0
∅k = ∅0 ∪ ∅1 ∪ ∅2 ∪ = ∅0 = {ε}
és |(a + b)| = |a| ∪ |b| = {a} ∪ {b} = {a, b} |((a + b) · a)| = |(a + b)| · |a| = {a, b} · {a} = {aa, ab} valamint {ε} = {aa, ab}0 ⊆ {aa, ab}∗
Feladat. Írjuk ki expliciten, hogy a ((a + b)∗ · (b + a)) · (b + a) reguláris kifejezés mely nyelvet jelöli!
Reguláris kifejezések VS automaták Vessük össze a reguláris kifejezések által jelölhető nyelveket az automaták által felismerhető nyelvekkel! Két kérdés merül fel: Kérdés 1. Igaz-e, hogy minden reguláris kifejezés által jelölt nyelv felismerhető automatával? Válasz: Igen. Miért is? Lássuk csak: 1. |∅|, |a| felismerhetőek automatával, minden a ∈ Σ-ra, ugyanis: az üres nyelvet minden olyan automata felismeri, amelynek nincs végállapota, pl.:
egy, az egyetlen a betűből álló szót tartalmazó nyelvet felismerő (nemdeterminisztikus) automata pedig:
2. Ha |R1| és |R2| felismerhetőek automatával, akkor |R1| ∪ |R2| is: lásd az automaták direkt szorzatát a második órai anyagban. Vagy vegyük az |R1|-et felismerő M1 és az |R2|-t felismerő M2 automaták diszjunkt unióját. Vegyünk fel egy új állapotot, legyen ez az így konstruált automata kezdőállapota. Ebből az állapotból M1 és M2 kezdőállapotaiba ε-átmenetket húzunk. A megkonstruált automata végállapotai legyenek M1 végállapotai valamint az M2 végállapotai. 3. Ha |R1| és |R2| felismerhetőek automatával akkor |R1| · |R2| is az: elég az |R1|-et felismerő M1 és az |R2|-t felismerő M2 diszjunkt unióját venni, a kezdőállapot legyen M1 kezdőállapota, a végállapotok legyenek M2 végállapotai és vegyünk fel εátmeneteket M1 végállapotaiból M2 kezdőállapotába. 23
4. Ha |R1| felismerhető, akkor |R1|∗ is az: elég egy új q^0 állapotot bevezetni, legyen ez a kezdőállapot és az egyetlen végállapot is egyben, majd vegyünk fel ε-átmeneteket qˆ0-ból az |R1|-et felismerő M1 kezdőállapotába és annak végállapotaiból qˆ0-ba.
Feladat: Mutassunk egy, az |((a + b)∗ · (a + a))| nyelvet felismerő automatát. Megoldás: Először megadunk egy olyan automatát, amely felismeri az a által jelölt nyelvet.
Majd egy olyat, ami felismeri a b által jelölt nyelvet.
Majd vesszük a 2. pontban leírt uniós konstrukciót.
Ezután a 4. pontban leírt ∗-os konstrukciót.
Most pedig kétszer veszünk egy olyan automatát, mely az a által jelölt nyelvet ismeri fel.
Most a 2. pontban leírtakat alkalmazzuk ezen a két automatán, hogy kapjunk egy automatát, amely az (a + a) által jelölt nyelvet ismeri fel. 24
És most alkalmazzuk a 3. pontban leírt konstrukciót, hogy megkapjunk egy automatát, mely a |((a + b)∗ · (a + a))| nyelvet ismeri fel.
És a feladat kész is. ——————————————————————————————————————————– Kérdés 2. Igaz-e, hogy minden automatával felismerhető nyelv jelölhető reguláris kifejezéssel? Válasz: Igen. Legyen M egy tetszőleges, spontán átmenetekkel ellátott nemdeterminisztikus automata. Meg fogunk adni egy reguláris kifejezést ami azt a nyelvet jelöli amelyet M felismer. Az algoritmus végrehajtása négy lépésben történik: 1. Felveszünk egy új kezdő és egy új végállapotot. Az új kezdőállapotból a régi kezdőállapotba ε-átmenetet húzunk. A régi végállapotokból az új végállapotba ε-átmeneteket húzunk. 2. Az automata gráfjában minden ε-nal címkézett él címkéjét átírjuk ∅∗-ra14 . A kapott gráf már nem egy automata gráfja, csak egy gráf, melynek az élei reguláris kifejezésekkel címkézettek. Eztán minden be nem húzott él helyébe egy ∅-el15 címkézett élt húzunk. Ez az utolsó lépést praktikus kihagyni, elég, ha hallucináljuk, hogy be vannak húzva ezek az élek. 3. A belső csúcsokat “kilőjük” a következő transzformációt használva:
ahol a bal oldali gráfot transzformáljuk a jobb oldali gráfra. Itt 1 a csúcs, melyet eltávolítunk és 2, 3 illeszkedő csúcsok. Pontosabban fogalmazva: ha az 1 csúcsot távolítjuk el, akkor minden 2 és 3 csúcsra, úgy, hogy 2-ből megy él 1-be és 1-ből megy él 3-ba, a fenti transzformációt végezzük el. 14. csillaggal! 15. csillag nélkül!
25
Fontos! hogy egy csúcs eltávolításakor ezt a transzformációt minden, az adott 1 csúcsra illeszkedő 2 1 3 élpárra végrehajtsuk!
A 3. lépést addig folytatjuk, amíg nem marad belső csúcs. Azaz addig, amíg csak az 1.-es lépésben újonnan felvett csúcsok maradtak. Ha ez a helyzet áll fent, akkor következik a 4.-es lépés. Az az eset is előfordulhat, hogy a 2 és a 3 csúcsok egybeesnek. 4. Amikor már csak az új kezdő és az új végállapot maradt, egyetlen egy él lesz az új kezdőállapotból az új végállapotba, melynek címkéje egy reguláris kifejezés. Ez a kifejezés azt a nyelvet jelöli, melyet az automata felismer. ——————————————————————————————————————————– Egy példán keresztül szemléltetjük, az a legjobb. Induljunk ki a következő automatából:
Meg szeretnénk adni egy reguláris kifejezést, mely azt a nyelvet jelöli, amit ez az automata felismer. Az 1. lépést elvégezzük:
Most jöhet a 2. lépés:
Amint látható, az ε-okat ∅∗-ra cseréltem.16 Továbbá, a sok be nem húzott él mind ∅ -al van megcímkézve. Nehézségekbe ütközött volna szemléltetni az algoritmust, ha mindet behúzom, úgyhogy ezeket most hallucináljuk oda. Most a 3. lépés következik. Először q0-át lőjük ki:
16. Azért nulla csillagokat látsz, mert könnyebb volt így jelölni a ra jzolóprogramban.
26
....megtörtént. Most vegyük észre, hogy a csúnya (∅ + (∅∗ · ∅∗ · a)) reguláris kifejezés helyett írhatjuk azt is, hogy a, mivel ezek ugyanazt a nyelvet jelölik. Ugyanis a ∅ az üres halmazt jelöli, a + az uniónak felel meg, ∅∗ a {ε} nyelvet jelöli és igaz, hogy L · {ε} = {ε} · L = L, bármely L nyelvre.17 Tehát a fenti gráfot a következőre egyszerűsítjük:
Most folytassuk a 3. lépéssel. Ezúttal q1-től szabadulunk meg.18
A q2-n levő hurokél címkéje azért változott meg, mert az előző gráfban q2-ből megy egy a-val címkézett él q1-be, q1-ből egy b-vel címkézett él q1-be, majd pedig q1-ből c-vel címkézett él q2q1 q2 illeszkedő élpár, melyen a 3. lépésben leírt transzformáció végrehabe. Tehát q2 jtható.
Figyeljük meg, hogy a q3
q2 él címkéjén egyszerűsíthetünk. Az eredmény:
Már csak egyszer kell végrehajtani a 3. lépésben leírt transzformációt:
és kész.
A kapott reguláris kifejezés ∅ + ((a · b∗ · c) · (∅∗ + (a · b∗ · c))∗ · ∅∗)
melyet egyszerűsítve megkapjuk a feladat megoldását: (a · b∗ · c) · (∅∗ + (a · b∗ · c))∗ azaz ez utóbbi egy olyan reguláris kifejezés, mely ugyanazt a nyelvet jelöli, amelyet a kiindulási automata felismer.19 ——————————————————————————————————————————– 17. Efféle egyszerűsítések a zh-ban is megengedettek. 18. Az, hogy milyen sorrendben távolítjuk el a belső csúcsokat mindegy kell legyen. A végeredmény mindenképpen olyan reguláris kifejezés, mely a kiindulási automata által felismert nyelvet jelöli. 19. Ilyen feladat biztosan lesz a zh-ban.
27
Tehát, az eddigieket összefoglalva
Tétel. Determinisztikus véges automatákkal pontosan azok a nyelvek ismerhetőek fel, amelyek
felismerhetőek nemdeterminisztikus automatákkal. Ezek pedig pontosan azok a nyelvek, amelyek felismerhetőek spontán átmenetekkel ellátott nemdeterminisztikus automatákkal. Ezek pedig pontosan azok a nyelvek, amelyek jelölhetőek reguláris kifejezésekkel. ——————————————————————————————————————————– Tehát, ha azt mondom, hogy egy L nyelv reguláris , az azt jelenti, hogy L felismerhető determinisztikus automatával. És azt is jelenti, hogy L felismerhető (spontán átmenetekkel ellátott) nemdeterminisztikus automatával. És még azt is jelenti, hogy L jelölhető reguláris kifejezéssel. Fontos megjegyezni! NEM MINDEGY, hogy azt a szót használom, hogy felismerhet® vagy azt, hogy jelölhet® . Egy automata felismer nyelvet, nem jelöli! Egy reguláris kifejezés jelöl nyelvet, nem felismeri! Ezt ne keverjük már össze a zh-ban!
Hatodik gyakorlat Pumpáló Lemma Lemma. Legyen L ⊆ Σ∗ reguláris nyelv. Ekkor létezik k > 0, hogy bármely w ∈ L-re: ha |w| > k, akkor léteznek w1, w2, w3 ∈ Σ∗ szavak, melyekre igaz, hogy: 1. w = w1 w2 w3, 2. 0 < |w1w2| 6 k és 0 < |w2|, 3. minden n > 0-ra: w1 w2n w3 ∈ L. Mit is mond ki ez a lemma? Ha adott egy nyelv és az reguláris, akkor létezik olyan k szám, hogy minden k-nál hosszabb szó a nyelvben felbontható w1 w2 w3 alakba úgy, hogy w2 nem az üres szó és minden n > 0-ra w1 w2n w3 eleme a nyelvnek. Hogyan is lehetne igazolni ezt a lemmát? Legyen L reguláris, ekkor van L-t felismerő determinisztikus automata. Legyen k ezen automata állapotainak száma. Most vegyünk egy w szót, melynek hossza legalább k. Hogyan dolgozza fel ezt a szót az automata? Kezdetben a q0 kezdőállapotban van, majd egy betű beolvasása után a q1-be kerül, majd a q2-be, ..., majd a qmbe, ahol m = |w| > k. Összesen tehát legalább k + 1 darab állapotot érint a w feldolgozása közben, lennie kell hát olyan qi és q j állapotoknak, melyek ugyanazon állapotok - a k megválasztása miatt. Ez azt jelenti, hogy az automata qi-ből indulva feldolgoz valami w2 ( ε) szót, majd a q j = qi-be tér vissza. Ezért lesz igaz, hogy minden n > 0-ra w1 w2n w3 ∈ L. A lényeg kb ennyi. Ez a lemma egy olyan tulajdonságot ad, amely többek között reguláris nyelvekre igaz. Ha L reguláris, akkor teljesül rá valami. Ha A igaz, akkor B igaz. Egy A → B implikáció pedig akkor igaz, ha a premisszája és a konklúziója is teljesül vagy, ha a premisszája nem teljesül. Vagyis, ha adott egy L ⊆ Σ∗ és L nem reguláris, akkor tök mindegy, hogy igazak-e rá a lemmában leírt tulajdonságok - amit a lemma állít az igaz, mivel A → B premisszája hamis. Ha azonban L reguláris, akkor az A → B implikáció premisszája igaz, így a konklúziónak is teljesülnie kell. Tehát, ha valami L nyelvre megmutatjuk, hogy B nem teljesül, akkor A sem teljesülhet. 28
Végső soron ez a lemma egy jó eszköz rá, hogy leellenőrizzük valamely nyelvről, hogy reguláris-e: vegyük az L nyelvet és ellenőrizzük le, hogy teljesülnek-e rá a lemma által leírtak20 . Ha nem, akkor L nem lehet reguláris nyelv. Ha igen - akkor L lehet reguláris nyelv is, de nem biztos, hogy az.
Feladat:
Igazoljuk, hogy az L = {an bn |n > 0} nyelv nem reguláris!
Megoldás: Tegyük fel, hogy L reguláris. Ekkor a pumpáló lemma alapján létezik olyan k > 0, hogy minden w ∈ Σ∗ szóra: ha |w| > k akkor vannak w1, w2, w3 ∈ Σ∗ szavak, melyekre az 1., 2., 3., tulajdonságok teljesülnek. Nézzük meg w = ak bk-t. Ekkor w ∈ L, az L definíciója szerint. Vagyis a pumpáló lemma alapján kell legyenek w1, w2, w3 ∈ Σ∗ szavak úgy, hogy 1., 2., 3. teljesülnek.21 Több eset lehetséges: a) w2 = aℓ, valamely ℓ > 0-ra, b) w2 = bj , valamely j > 0-ra, c) w2 = aℓ b j , valamely ℓ, j > 0-ra. Vizsgáljuk meg egyenként ezeket az eseteket! a) Ekkor w1 w22 w3 = ak−ℓa2 ℓbk = ak+ℓ bk, ami nem eleme L-nek. b) Ekkor w1 w22 w3 = akb2 jbk− j = ak bk+ j , ami nem eleme L-nek. c) Ekkor w1 w22 w3 = ak−ℓ aℓ bj aℓ b j bk −j , ami nem eleme L-nek. Vagyis nincsenek w1, w2, w3 szavak úgy, hogy 1., 2., 3. teljesülnek. Ellentmondás. Ebből az következik, hogy a feltevésünk nem teljesül, miszerint L reguláris. Vagyis L nem reguláris.
Feladat: Igazoljuk, hogy az L = {a2n bn |n > 0} nyelv nem reguláris! Megoldás: Tegyük fel, hogy L reguláris. Ekkor a pumpáló lemma alapján létezik olyan k > 0, hogy minden w ∈ Σ∗ szóra: ha |w| > k akkor vannak w1, w2, w3 ∈ Σ∗ szavak, melyekre az 1., 2., 3., tulajdonságok teljesülnek. Nézzük meg w = a2 k bk-t. Ekkor w ∈ L, az L definíciója szerint. Vagyis a pumpáló lemma alapján kell legyenek w1, w2, w3 ∈ Σ∗ szavak úgy, hogy 1., 2., 3. teljesülnek. Több eset lehetséges: a) w2 = al, valamely l > 0-ra, b) w2 = bj , valamely j > 0-ra, 20. Azaz B. 21. Egy pumpáló lemmás feladat megoldásához csak akkor elég az, hogy azt írjuk, hogy “1., 2., 3., teljesülnek”, ha ott szerepel a papíron, hogy mit jelölünk 1., 2., 3.-mal. Különben nulla pont a zh-ban.
29
c) w2 = al bj , valamely l, j > 0-ra. Vizsgáljuk meg egyenként ezeket az eseteket! a) Ekkor w1 w22 w3 = a2 k−la2 lbk = a2k+l bk, ami nem eleme L-nek. b) Ekkor w1 w22 w3 = a2 kb2 jbk− j = a2 k bk+ j , ami nem eleme L-nek. c) Ekkor w1 w22 w3 = a2 k−l al bj al bj bk− j , ami nem eleme L-nek. Vagyis nincsenek w1, w2, w3 szavak úgy, hogy 1., 2., 3. teljesülnek. Ellentmondás. Ebből az következik, hogy a feltevésünk nem teljesül, miszerint L reguláris. Vagyis L nem reguláris.
A két feladat megoldását összehasonlítva azt láthatjuk, hogy van egy egyfajta recept , amit követni lehet a pumpáló lemmás feladatok megoldása esetén. Jó taktika azt csinálni, hogy megjegyezzük azt, hogy hogyan kell igazolni azt, hogy {anbn |n > 0} nem reguláris, majd ezt az igazolást írjuk át. Mindkét feladat esetén azt csináltuk, hogy feltettük, hogy L nem reguláris, majd kerestünk egy k-tól függő w-t úgy, hogy w benne legyen L-ben. Majd ezt az egy darab szót vizsgáltuk meg. Ha a pumpáló lemma igaz, akkor w felbontható kell legyen w1w2w3 alakba úgy, hogy a középső (nemüres) szót “pumpálva” kapott w1w2nw3 szó is eleme L-nek, minden n > 0 esetén. Ezután ügyeskedéssel azt mutattuk meg, hogy w2-t nem lehet úgy megválasztani, hogy ez minden n-re teljesüljön. Pl. a fenti feladatoknál n = 2 esetén nem fog teljesülni. Egyes feladatoknál ezt az ügyeskedést nagyon könnyű megtenni, más feladatoknál többet kell gondolkozni. Mivel így ellentmondásra jutottunk, a kezdeti feltevésünk, miszerint L reguláris, nem lehet igaz. Tehát L nem reguláris. Ennyi a pumpáló lemmás feladatokhoz a “recept”.
Fontos! Ha egy pumpáló lemmás feladatban az ellentmondás nem jön ki, az lehet azért van, mert nem is jöhet ki! Ebben az esetben próbáljunk meg egy automatát megadni, amely az adott nyelvet felismeri! Ha van ilyen automata, akkor a pumpáló lemmát akárhogy csavarjuk, nem jöhet ki az, hogy a nyelv nem reguláris!22
Feladat: Igazoljuk, hogy az L = {an bn+1 cn |n > 0} nyelv nem reguláris!
Feladat: Igazoljuk, hogy az L = {an b2 n+1 cn |n > 100} nyelv nem reguláris!
Feladat: Igazoljuk, hogy az L = {an |n prím} nyelv nem reguláris!
Feladat: Adjunk meg olyan f : N → N-t, melyre igaz, hogy {an bf (n)+1|n > 0} reguláris! Megoldás: Legyen f (n) = 0, minden n > 0-ra. Tulajdonképpen bármely f (n) = k jó, ahol k valami rögzített konstans. Még igazolni kell, hogy {an b f (n)+1| n > 0} reguláris, vagyis meg kell adni egy determinisztikus automatát, mely felismeri ezt a nyelvet. 22. Ha mégis kijönne, akkor valamit elrontottunk.
30
Feladat: Határozzuk meg, hogy mely f : N → N leképezésekre igaz, hogy {an bf (n)+1|n > 0} reguláris!
Irodalomjegyzék [1] Ésik Zoltán: Számítástudomány Alapjai, 2011. http://www.tankonyvtar.hu/hu/tartalom/tamop425/0008_esik/Esik_Szamitastudomany.pdf [2] Ésik Zoltán, Gombás Éva, Iván Szabolcs: Automaták és formális nyelvek példatár, Typotex Kiadó, 2011. http://tananyagfejlesztes.mik.uni-pannon.hu/images/stories/vegleges_tananyagok/masodikreszlet/esik_gombas_ivan_automatak.pdf [3] Peter Linz: An Introduction to Formal Languages and Automata, 5th edition, Jones & Bartlett Publishers, Sudbury, MA, USA, 2012. [4] Susan H. Rodger and Thomas W. Finley: JFLAP An Interactive Formal Languages and Automata Package, Jones & Bartlett Publishers, Sudbury, MA, USA, 2006. [5] J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, Reading, 1979. [6] Lovász László: Algoritmusok bonyolultsága, Tankönyvkiadó, 1989. [7] H. R. Lewis, C. H. Papadimitriou: Elements of the Theory of Computation, 2nd ed., Prentice Hall. 1998. [8] C. H. Papadimitriou: Számítási bonyolultság, Novadat Kiadó, 1999. [9] M. Sipser: Introduction to the Theory of Computation, PWS Publishing Co., 1997. [10] JFLAP program: http://www.jflap.org/
31
