Teorie jazyků a automatů I

Sˇa´rka Vavrecˇkova´

Teorie jazyku˚ a automatu˚ I Sbı´rka u´loh pro cvicˇenı´

´ stav informatiky U Filozoficko-prˇ´ırodoveˇdecka´ fakulta v Opaveˇ Slezska´ univerzita v Opaveˇ Opava, poslednı´ aktualizace 5. kveˇtna 2015

Anotace: Tato skripta jsou urcˇena pro studenty prˇedmeˇtu˚ Teorie jazyku˚ a automatu˚ I a Za´klady teoreticke´ informatiky I. Jedna´ se o sbı´rku prˇ´ıkladu˚, ktera´ zahrnuje la´tku probı´ranou na cvicˇenı´ dane´ho prˇedmeˇtu. Zde uvedene´ definice jsou pouze orientacˇnı´, jejich u´kolem je prˇipomenout znacˇenı´ a postupy pouzˇ´ıvane´ v na´slednyćh prˇ´ıkladech.

Teorie jazyku˚ a automatu˚ I Sbı´rka u´loh pro cvicˇenı´ RNDr. Sˇa´rka Vavrecˇkova´, Ph.D. Dostupne´ na: http://vavreckova.zam.slu.cz/formal1.html ´ stav informatiky U Filozoficko-prˇ´ırodoveˇdecka´ fakulta v Opaveˇ Slezska´ univerzita v Opaveˇ Bezrucˇovo na´m. 13, Opava Sa´zeno v syste´mu LATEX

Tato inovace prˇedmeˇtu Teorie jazyku˚ a automatu˚ I, cvicˇenı´ je spolufinancovańa Evropsky´m socia´lnı´m fondem a Sta´tnı´m rozpocˇtem CˇR, projekt cˇ. CZ.1.07/2.2.00/28.0014, „Interdisciplina´rnı´ vzdeˇla´vańı´ v ICT s jazykovou kompetencı´ “.

Obsah

1

2

3

Jazyky a regula´rnı´ vy´razy ˇ eteˇzec, mnozˇina, jazyk . . . 1.1 R 1.2 Regula´rnı´ vy´razy . . . . . . . 1.3 Urcˇenı´ jazyka . . . . . . . . . 1.4 Operace nad jazyky . . . . . . 1.4.1 Regula´rnı´ operace . . 1.4.2 Dalsˇ´ı potrˇebne´ operace 1.4.3 Prefixy a postfixy slov 1.5 K vlastnostem jazyku˚ . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

1 1 4 5 6 7 9 12 14

Konecˇne´ automaty 2.1 Vytva´rˇ´ıme konecˇny´ automat . . . . . . . . . . . . . . . . . . 2.2 Nedeterministicky´ konecˇny´ automat . . . . . . . . . . . . . 2.3 Tota´lnı´ automat . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Konecˇne´ jazyky . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Odstraneˇnı´ nepotrˇebnyćh stavu˚ (redukce) . . . . . . . . . . 2.6 Uza´veˇrove´ vlastnosti – regula´rnı´ operace . . . . . . . . . . 2.6.1 Sjednocenı´ . . . . . . . . . . . . . . . . . . . . . . . . 2.6.2 Zrˇeteˇzenı´ . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.3 Iterace (Kleeneho uza´veˇr) . . . . . . . . . . . . . . . 2.7 Uza´veˇrove´ vlastnosti – dalsˇ´ı operace . . . . . . . . . . . . . 2.7.1 Pozitivnı´ iterace . . . . . . . . . . . . . . . . . . . . . 2.7.2 Zrcadlovy´ obraz (reverze) . . . . . . . . . . . . . . . 2.7.3 Pru˚nik . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7.4 Homomorfismus . . . . . . . . . . . . . . . . . . . . 2.8 Sestrojenı´ konecˇne´ho automatu podle regula´rnı´ho vy´razu .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

17 17 19 21 23 24 26 27 29 32 34 34 36 39 42 44

Regula´rnı´ gramatiky 3.1 Vytva´rˇ´ıme regula´rnı´ gramatiku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Konecˇny´ automat podle regula´rnı´ gramatiky . . . . . . . . . . . . . . . . . . . . . . . 3.3 Regula´rnı´ gramatika podle konecˇne´ho automatu . . . . . . . . . . . . . . . . . . . . .

46 46 50 52

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

iii

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

iv

4

5

Bezkontextove´ gramatiky 4.1 Vytva´rˇ´ıme bezkontextovou gramatiku . . . . . . . . . . . . 4.2 Derivacˇnı´ strom . . . . . . . . . . . . . . . . . . . . . . . . . ´ pravy bezkontextovyćh gramatik . . . . . . . . . . . . . . 4.3 U 4.3.1 Prˇevod na nezkracujıćı´ bezkontextovou gramatiku 4.3.2 Redukce gramatiky . . . . . . . . . . . . . . . . . . . 4.3.3 Odstraneˇnı´ jednoduchyćh pravidel . . . . . . . . . . 4.3.4 Gramatika bez cyklu a vlastnı´ gramatika . . . . . . 4.3.5 Leva´ a prava´ rekurze . . . . . . . . . . . . . . . . . . Za´sobnı´kovy´ automat 5.1 Co je to za´sobnı´kovy´ automat . . . . . . . . . . . . . . . 5.1.1 Definice . . . . . . . . . . . . . . . . . . . . . . . 5.1.2 Typy za´sobnı´kovyćh automatu˚ . . . . . . . . . . 5.2 Vytva´rˇ´ıme za´sobnı´kovy´ automat . . . . . . . . . . . . . 5.3 Nedeterminismus . . . . . . . . . . . . . . . . . . . . . . 5.4 Za´sobnı´kovy´ automat podle bezkontextove´ gramatiky

. . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

. . . . . .

. . . . . . . .

56 56 57 59 59 63 64 66 66

. . . . . .

73 73 73 74 77 79 81

Kapitola

1

Jazyky a regula´rnı´ vy´razy 1.1

ˇ eteˇzec, mnozˇina, jazyk R

U konecˇnyćh automatu˚ je nejmensˇ´ı (atomickou, da´le nedeˇlitelnou) jednotkou, se kterou pracujeme, signa´l (znak). Mnozˇinu signa´lu˚, se ktery´mi doka´zˇe konkre´tnı´ automat pracovat, nazy´va´me abeceda a znacˇ´ıme symbolem Σ (velke´ rˇecke´ pı´smeno sigma). Abeceda je vzˇdy konecˇna´ mnozˇina. Automaty rozpozna´vajı´ (tj. prˇijı´majı´ na sve´m vstupu) posloupnosti signa´lu˚ (prˇ´ıpadneˇ znaku˚; tyto posloupnosti nazy´va´me slova) – automaty na vstupu postupneˇ cˇtou signa´ly a za´rovenˇ meˇnı´ svu˚j vnitrˇnı´ stav. Jeden automat obvykle doka´zˇe rozpozna´vat vıće takovyćh slov. Mnozˇina vsˇech slov, ktera´ doka´zˇe automat rozpoznat, je jazyk rozpozna´vany´ automatem. Pokud je automat oznacˇen A, pak jazyk jı´m rozpozna´vany´ znacˇ´ıme L(A). Obecneˇ (nejen ve vztahu k automatu˚m) je jazyk mnozˇinou slov nad danou abecedou. Protozˇe jazyky mohou by´t i hodneˇ rozsa´hle´ mnozˇiny, je trˇeba si za´pis jazyka a take´ jeho slov vhodneˇ zkra´tit. Mu˚zˇeme pouzˇ´ıt toto znacˇenı´: • ε – takto znacˇ´ıme pra´zdne´ slovo, tedy rˇeteˇzec o de´lce nula (rˇecke´ pı´smeno epsilon)

• a2 , a3 , a4 , . . . – pocˇet opakovańı´ objektu, ktery´ je takto „umocneˇn“, naprˇ´ıklad a3 znamena´ slovo aaa (symbol zrˇeteˇzenı´ „·“ nemusı´me psa´t), a0 prˇedstavuje ε (pocˇet signa´lu˚ a je nula) • a∗ – opera´tor ∗ (Kleeneho opera´tor, iterace) znamena´, zˇe objekt, za ktery´m na´sleduje (signa´l, prvky mnozˇiny, apod.) mu˚zˇe by´t ve sloveˇ opakovań, a to jaky´koliv pocˇet kra´t (mu˚zˇe by´t i nula opakovańı´), za hveˇzdicˇku mu˚zˇeme dosadit jakoukoliv neza´pornou celocˇ´ıselnou mocninu, tedy a∗ prˇedstavuje mnozˇinu slov {ε, a, aa, aaa, . . .}

• {a, b, c}∗ = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, aab, . . .} (operace hveˇzdicˇka se prova´dı´ prˇes vsˇechny prvky mnozˇiny, ktery´koliv z nich mu˚zˇe by´t pouzˇit na ktere´mkoliv mı´steˇ) • (abc)4 = abcabcabcabc (prvky v posloupnosti narozdı´l od prvku˚ mnozˇiny nejsou oddeˇleny cˇa´rkou, mezi nimi je vztah zrˇeteˇzenı´ • (ab)∗ = {ε, ab, (ab)2 , (ab)3 , . . .} = {ε, ab, abab, ababab, . . .}

• {a, dfg, bb}∗ = {ε, a, dfg, bb, aa, adfg, abb, dfga, dfgdfg, dfgbb, aaa, . . .}

1

P

KAPITOLA 1

JAZYKY A REGULA´RNI´ VY´RAZY

2

• a+ je pozitivnı´ iterace, uvedeny´ objekt mu˚zˇe by´t v jake´mkoliv pocˇtu vy´skytu˚ podobneˇ jako u operace ∗ , ale nejmeńeˇ jednou, takzˇe a+ = {a, a2 , a3 , . . .} • opera´tor pozitivnı´ iterace se z du˚vodu˚ snadne´ zameˇnitelnosti s jiny´m opera´torem cˇasto prˇepisuje do tvaru a∗ a nebo aa∗

• opera´tor + mu˚zˇe by´t pouzˇit take´ jako bina´rnı´: ab + bc naprˇ´ıklad urcˇuje mnozˇinu dvou slov, ab a bc, tedy mnozˇinu {ab, bc}

• tento opera´tor cˇasto uplatnˇujeme na dva vy´razy, naprˇ´ıklad (ab)∗ + (ba)∗ prˇedstavuje mnozˇinu slov, ve kteryćh se strˇ´ıdajı´ znaky a a b s tı´m, zˇe slovo mu˚zˇe zacˇ´ıt ktery´mkoliv z teˇchto znaku˚, de´lka slov je vzˇdy sude´ cˇ´ıslo • (a + b)∗ = {a, b}∗ – oba za´pisy prˇedstavujı´ mnozˇinu vsˇech slov nad abecedou {a, b}

Protozˇe jazyk je vlastneˇ mnozˇina slov, mu˚zˇeme pouzˇ´ıt klasicky´ matematicky´ mnozˇinovy´ za´pis: {ai baj ; i, j ≥ 0} je tote´zˇ jako a∗ ba∗ . Prˇı´klad 1.1 Za´pis vy´razu˚ je cˇasto mozˇne´ minimalizovat (zjednodusˇit). Naprˇ´ıklad: • a2 · ε = a2 (protozˇe ε je neutra´lnı´m prvkem vzhledem k operaci zrˇeteˇzenı´, podobneˇ jako cˇ´ıslo 0 u scˇ´ıtańı´ cˇ´ısel)

M

• a∗ + ε = a∗ (protozˇe vy´raz a∗ uzˇ v sobeˇ zahrnuje slovo ε) • (a + ε)∗ = a∗ (zdu˚vodneˇte)

• (a + aa)∗ = a∗ (zdu˚vodneˇte)

• (ab)+ + ε = (ab)∗ (zdu˚vodneˇte) • (ab)∗ + (a + b)∗ = (a + b)∗

• (a2 )3 = a6

Prˇı´klad 1.2 Jazyk mu˚zˇe by´t specifikovań take´ pomocı´ matematickyćh operacı´. Naprˇ´ıklad: • a2n

; n ≥ 0 je tote´zˇ jako zı´ska´me mnozˇinu {a, b}∗

(aa)∗ ,

tedy mnozˇina

{ε, a2 , a4 , a6 , . . .}

poslednı´ dveˇ mnozˇiny,

; n ≥ 1 je tote´zˇ jako aa(aa)∗ , tedy mnozˇina {a2 , a4 , a6 , . . .} 0 1 2 3 • a ; n ≥ 0 je neˇco jine´ho (!), jedna´ se o mnozˇinu {a2 , a2 , a2 , a2 , . . .} = {a1 , a2 , a4 , a8 , . . .} • {w ∈ {a, b}∗ ; |w| > 5} je mnozˇina vsˇech slov nad abecedou {a, b}, jejichzˇ de´lka je veˇtsˇ´ı nezˇ 5 • {w ∈ {a, b}∗ ; |w| ≤ 5} je mnozˇina vsˇech slov nad abecedou {a, b}, jejichzˇ de´lka je mensˇ´ı nebo

•

2n a 2n

rovna 5, tedy pokud sjednotı´me tuto a prˇedchozı´ mnozˇinu, dostaneme: {w ∈ {a, b}∗ ; |w| > 5} ∪ {w ∈ {a, b}∗ ; |w| ≤ 5} = {a, b}∗

• {w ∈ {a, b}∗ ; |w|a = |w|b } je mnozˇina vsˇech slov nad abecedou {a, b} takovyćh, zˇe pocˇet znaku˚ a je stejny´ jako pocˇet znaku˚ b, tj. {ε, ab, ba, aabb, abab, abba, baab, baba, bbaa, . . .}

• {an bn ; n ≥ 0} oproti prˇedchozı´mu prˇida´va´ podmıńku na porˇadı´ (nejdrˇ´ıv znaky a, azˇ pak b), tedy: {ε, ab, aabb, . . .}, do mnozˇiny nepatrˇ´ı naprˇ´ıklad slovo aab ani slovo ba

M

KAPITOLA 1 •

i j ab

•

i j ab


3

; i, j ≥ 0 pro zmeˇnu stanovuje pouze podmıńku na porˇadı´: {ε, a, b, aa, bb, ab, aab, abb, . . .},

do te´to mnozˇiny nepatrˇ´ı naprˇ´ıklad slovo ba

; i ≥ 2, j ≥ 1 je definovańo podobneˇ jako prˇedchozı´, ale ma´me odlisˇnou spodnı´ hra-

nici pro hodnotu promeˇnnyćh i a j, nejkratsˇ´ı slovo je aab

Prˇı´klad 1.3 Napı´sˇeme vsˇechna slova na´sledujıćıćh jazyku˚ kratsˇ´ı nezˇ 5. Postup: nejdrˇ´ıv mı´sto vsˇech „promeˇnnyćh“ indexu˚ ∗ a + dosadı´me nejnizˇsˇ´ı mozˇnou hodnotu, tj. naprˇ´ıklad ve vy´razu a∗ b∗ vytvorˇ´ıme slovo a0 b0 = ε, pak postupneˇ dosazujeme vysˇsˇ´ı hodnoty v ru˚znyćh mozˇnyćh kombinacıćh.

M

• ab∗ + ba = {a, ab, ba, abb, abbb, . . .}

• 2 · {0, 1}∗ = { 2, 20, 21, 200, 201, 210, 211, 2000, 2001, 2010, 2011, 2100, 2101, 2110, 2111, . . .} i j • {a bb ; i, j ≥ 1} ∪ {(ab)i ; i ≥ 0} = {abb, aabb, abbb, . . .} ∪ {ε, ab, abab, . . .} = = {abb, aabb, abbb, ε, ab, abab, . . .} Zde si vsˇimneˇme odlisˇnyćh spodnıćh mezı´ pro promeˇnne´ i, j v obou sjednocovanyćh jazycıćh – pokud i ≥ 1, pak ai znamena´ a+ neboli aa∗ . • (10)∗ 01 = {01, 1001, . . .}

• (10)∗ (01)∗ = {ε, 10, 01, 1010, 1001, 0101, . . .}

• {bai cbj ; 0 ≤ i < j} = {bcb, bcbb, . . .} (vsˇimneˇte si, zˇe kdyby ve sloveˇ bylo jedno a, musela by na´sledovat nejmeńeˇ dveˇ b, cozˇ by ale znamenalo, zˇe de´lka slova by nebyla kratsˇ´ı nezˇ 5) • {w ∈ {a, b}∗ ; |w|a < |w|b } = {b, bb, abb, bab, bba, bbb, abbb, babb, bbab, bbba, bbbb, . . .} (do jazyka vsˇak nepatrˇ´ı naprˇ´ıklad slovo aabb, protozˇe nenı´ splneˇna podmıńka |w|a < |w|b )

• {w ∈ {a, b}∗ ; |w|a = |w|b + 1} = {a, abb, bab, bba, . . .} (vsˇimneˇte si, zˇe „vedlejsˇ´ım du˚sledkem“ podmıńky je licha´ de´lka slov jazyka)

´ koly U Napisˇte vsˇechna slova na´sledujıćıćh jazyku˚ kratsˇ´ı nezˇ 5. •

(abc)∗

• (a∗ b)∗

• (ab)∗ c

• (a∗ b)∗ c

• {(ab)i bj ; i ≥ 0, j ≥ 1}

• 0∗ (10)∗ 1

• {ai bj ; i, j ≥ 0, i ≤ j}

• {w ∈ {a, b}∗ ; |w|b = |w|a + 1}

C

KAPITOLA 1


• {w ∈ {a, b}∗ ; |w|a < |w|b } •

w · bai ; w ∈ {a, b}∗ , i ≥ 1

4

• {w ∈ {a, b}∗ ; |w| < 3}

1.2

Regula´rnı´ vy´razy

S regula´rnı´mi vy´razy jsme se jizˇ setkali, ted’ se na neˇ zameˇrˇ´ıme forma´lneˇji. Oznacˇme pomocnou mnozˇinu Φ = {∅, ε, +, ·, ∗, (, )}. Mnozˇina RV (Σ) vsˇech regula´rnıćh vy´razu˚ nad abecedou Σ je nejmensˇ´ı mnozˇina slov (rˇeteˇzcu˚) takova´, zˇe • slova se skla´dajı´ ze symbolu˚ abecedy Σ ∪ Φ, Σ a Φ jsou disjunktnı´,

P

• ∅ ∈ RV (Σ), ε ∈ RV (Σ), a ∈ RV (Σ) pro kazˇde´ a ∈ Σ, • jestlizˇe α, β ∈ RV (Σ), pak taky (α + β) ∈ RV (Σ), (α · β) ∈ RV (Σ), (α)∗ ∈ RV (Σ).

Symbol pro zrˇeteˇzenı´ se nemusı´ psa´t. Pro operace pouzˇ´ıvane´ v regula´rnıćh vy´razech platı´ podobna´ pravidla jako pro operace v aritmetickyćh vy´razech. Naprˇ´ıklad opera´tory · a + jsou asociativnı´ a distributivnı´, + take´ komutativnı´. Prvky ∅ a ε plnı´ v regula´rnıćh vy´razech podobnou roli jako v aritmetice nula a jednicˇka. Teˇchto vlastnostı´ lze vyuzˇ´ıt prˇi u´pravaćh slozˇiteˇjsˇ´ıch regula´rnıćh vy´razu˚. Prˇı´klad 1.4 ∅+a=a ε·a=a ε∗ = ε ab + c = c + ab a(b + c) = ab + ac ab∗ + ab = a(b∗ + b) = ab∗ ab∗ + a(c + d) = a(b∗ + c + d)

(a∗ b∗ )∗ = (ab∗ )∗ = {a, b}∗ = (a + b)∗ (a + ε)∗ = a∗ (a + ε) · a∗ = a∗ bb∗ + ε = b∗ a(ba)∗ b = ab(ab)∗ = (ab)∗ ab a + (cb)∗ a = (ε + (cb)∗) a = (cb)∗ a aba + (ab)∗ a = ((ab) + (ab)∗ )a = (ab)∗ a

´ koly U Zjednodusˇte tyto regula´rnı´ vy´razy: • ab∗ + a∗ (a + ε)

• a∗ b(ab)∗ + a∗ b(ab)∗ bb∗

• a + bc(bc)∗ a

M

C • a∗ + b(a + ε) · ∅

• {a, b}∗ ba + (ab)∗ ba

• (ab)∗ abaa∗ + ab(ab)∗ a∗

• 01(01)∗ 0 + 0∗ (10)∗ {0, 1}∗

• a∗ + a{a, b}∗ b∗

• 01(01)∗ 0 + 0∗ (10)∗

KAPITOLA 1

1.3


5

Urcˇenı´ jazyka

Kdyzˇ ma´me sestavit prˇedpis jazyka (tj. mnozˇiny rˇeteˇzcu˚) splnˇujıćı´ho urcˇitou podmıńku, musı´me vzˇdy zapsat maxima´lnı´ mnozˇinu vyhovujıćı´ dane´ podmıńce. Jaky´koliv rˇeteˇzec vyhovujıćı´ zadane´ podmıńce musı´ patrˇit do takove´ho jazyka. Prˇı´klad 1.5 Sestavı´me prˇedpis jazyka L splnˇujıćı´ho na´sledujıćı´ podmıńku: • L obsahuje vsˇechna slova zacˇ´ınajıćı´ rˇeteˇzcem aa a koncˇ´ıcı´ symbolem b, je nad abecedou {a, b}: L = aa(a + b)∗ b = {aa} · {a, b}∗ · {b} = {aa · w · b ; w ∈ {a, b}∗ }

• slova jazyka L obsahujı´ nejmeńeˇ 2 symboly a a maxima´lneˇ 10 symbolu˚ b, nad abecedou {a, b}: L = {w ∈ {a, b}∗ ; |w|a ≥ 2, |w|b ≤ 10}

• v prvnı´ cˇa´sti slova jsou pouze symboly a, v druhe´ cˇa´sti slova jsou pouze symboly b: L = a∗ b∗ = {ai bj ; i, j ≥ 0}

• v kazˇde´m sloveˇ je stejny´ pocˇet symbolu˚ a a b, nad abecedou {a, b}: L = {w ∈ {a, b}∗ ; |w|a = |w|b }

• ve slovech je symbolu˚ a meńeˇ nezˇ symbolu˚ b, nad abecedou {a, b}: L = {w ∈ {a, b}∗ ; |w|a < |w|b }

• vsˇechna slova majı´ sudou de´lku, nad abecedou {a, b}: L = ((a + b)2 )∗ = {w ∈ {a, b}∗ ; |w| = 2n, n ∈ N0 }

(N0 povazˇujme za mnozˇinu vsˇech prˇirozenyćh cˇ´ısel, vcˇetneˇ nuly)

• jazyk nad abecedou {a}, pocˇet symbolu˚ a ve sloveˇ je druhou mocninou neˇktere´ho prˇirozene´ho cˇ´ısla nebo nuly: 2

L = {an ; n ≥ 0} • jazyk nad abecedou {a, b}, pocˇet symbolu˚ a ve sloveˇ je druhou mocninou neˇktere´ho prˇirozene´ho cˇ´ısla nebo nuly: L = {w ∈ {a, b}∗ ; |w|a = n2 , n ≥ 0} • jazyk je nad abecedou {a, b}; slova zacˇ´ınajı´ symbolem a a obsahujı´ sudy´ pocˇet symbolu˚ b, a nebo zacˇ´ınajı´ symbolem b a obsahujı´ lichy´ pocˇet symbolu˚ a: L = {a · w ; |w|b = 2n, n ≥ 0} ∪ {b · w ; |w|a = 2n + 1, n ≥ 0}

M

KAPITOLA 1


6

• slova majı´ meńeˇ symbolu˚ a nezˇ symbolu˚ b, a za´rovenˇ stejny´ pocˇet symbolu˚ c jako symbolu˚ b, jsou nad abecedou {a, b, c}: L = {w ∈ {a, b, c}∗ ; |w|a < |w|b } ∩ {w ∈ {a, b, c}∗ ; |w|c = |w|b } = {w ∈ {a, b, c}∗ ; |w|a < |w|b , |w|c = |w|b }

´ koly U Sestavte prˇedpis jazyka, kde 1. vsˇechna slova zacˇ´ınajı´ pı´smenem a a pocˇet symbolu˚ b je veˇtsˇ´ı nezˇ 5,

C

2. pocˇet symbolu˚ a je dvojna´sobkem pocˇtu symbolu˚ b, 3. de´lka slov je neˇkterou (prˇirozena´ cˇ´ısla) mocninou cˇ´ısla 3, jazyk je nad abecedou {a, b},

4. pocˇet symbolu˚ b ve slovech je neˇkterou (prˇirozena´ cˇ´ısla) mocninou cˇ´ısla 3, jazyk je nad abecedou {a, b}, 5. pocˇet symbolu˚ a je veˇtsˇ´ı nebo roven pocˇtu symbolu˚ b ve sloveˇ, a za´rovenˇ de´lka slov je nejmeńeˇ 8, jazyk je nad abecedou {a, b},

6. pocˇet symbolu˚ a je veˇtsˇ´ı nezˇ pocˇet symbolu˚ b ve sloveˇ, a nebo de´lka slov je nejmeńeˇ 8, jazyk je nad abecedou {a, b},

7. jedna´ se o jazyk prˇirozenyćh bina´rnıćh cˇ´ısel nad abecedou {0, 1}; symbolem 0 mu˚zˇe zacˇ´ınat pouze jednociferne´ cˇ´ıslo (tj. jednoznakovy´ rˇeteˇzec „0“), vsˇechna ostatnı´ slova zacˇ´ınajı´ symbolem 1, jazyk neobsahuje pra´zdne´ slovo, 8. jedna´ se o jazyk rea´lnyćh bina´rnıćh cˇ´ısel s desetinnou tecˇkou nad abecedou {0, 1, .}; pro celou cˇa´st slova (rea´lne´ho cˇ´ısla) platı´ podmıńka z prˇedchozı´ho bodu, je nad abecedou {0, 1}, da´le na´sleduje desetinna´ tecˇka s rea´lnou cˇa´stı´, v rea´lne´ cˇa´sti za desetinnou tecˇkou (take´ nad abecedou {0, 1} musı´ by´t alesponˇ jeden symbol.

1.4

Operace nad jazyky

Protozˇe jazyky jsou mnozˇiny rˇeteˇzcu˚ (slov), lze na nich prova´deˇt mnozˇinove´ a rˇeteˇzcove´ operace. Jazyk reprezentujeme bud’ mnozˇinoveˇ nebo vy´razem (konkre´tneˇji regula´rnı´m vy´razem). Spra´vneˇ bychom meˇli pouzˇ´ıvat znacˇenı´ operacı´ odpovı´dajıćı´ reprezentaci jazyka (tj. mnozˇinove´ operace, jako je naprˇ´ıklad sjednocenı´ cˇi pru˚nik, prova´deˇt za´sadneˇ na mnozˇinovyćh reprezentacıćh jazyku˚), ale pokud by zpu˚sob reprezentace byl prˇ´ılisˇ komplikovany´, mu˚zˇeme od tohoto prˇedpisu upustit. Typicky operaci pru˚niku budeme pouzˇ´ıvat i u reprezentace jazyka regula´rnı´m vy´razem. V na´sledujıćıćh definicıćh budeme vzˇdy prˇedpokla´dat, zˇe jazyky jsou nad abecedou Σ. Nejdrˇ´ıv se budeme zaby´vat regula´rnı´mi operacemi – sjednocenı´, zrˇeteˇzenı´ a iterace, ktere´ majı´ blı´zky´ vztah k regula´rnı´m vy´razu˚m.

R

KAPITOLA 1

1.4.1


7

Regula´rnı´ operace

Sjednocenı´: Slovo patrˇ´ı do sjednocenı´ dvou mnozˇin, jestlizˇe je prvkem alesponˇ jedne´ z teˇchto mnozˇin. Forma´lnı´ za´pis: L1 ∪ L2 = {w ∈ Σ∗ ; w ∈ L1 nebo w ∈ L2 }

P

(1.1)

Jedna´ se o jednu z regula´rnıćh operacı´, cozˇ znamena´, zˇe ma´ svu˚j obraz v reprezentaci jazyka formou regula´rnı´ho vy´razu. Tam mı´sto symbolu ∪ pouzˇ´ıva´me symbol +. Prˇı´klad 1.6

M

• Pokud L1 = {abc, aac, cb} a L2 = {baa, cb}, pak L1 ∪ L2 = {abc, aac, cb, baa} • Pokud L1 = ab∗ a L2 = cb∗ , pak L1 ∪ L2 = ab∗ + cb∗ = (a + c) b∗ n

• Pokud L1 = a∗ a L2 = a2 ; n ≥ 0 , pak L1 ∪ L2 = L1 (protozˇe zde L2 ⊂ L1 )

• L ∪ ∅ = L (pra´zdna´ mnozˇina zde plnı´ roli neutra´lnı´ho prvku) Zrˇeteˇzenı´: Zrˇeteˇzenı´ dvou slov nenı´ trˇeba definovat, zapisujeme je u · v, kde u, v ∈ Σ∗ . Zrˇeteˇzenı´m dvou jazyku˚ je jazyk, jehozˇ slova lze rozdeˇlit na dveˇ cˇa´sti – prvnı´ patrˇ´ı do prvnı´ho stanovene´ho jazyka, druha´ cˇa´st do druhe´ho jazyka. L1 · L2 = {u · v ; u ∈ L1 , v ∈ L2 }

P

(1.2)

Zrˇeteˇzenı´ jazyku˚ provedeme jednodusˇe tak, zˇe po dvojicıćh zrˇeteˇzujeme slova teˇchto jazyku˚ (kazˇde´ slovo prvnı´ho jazyka postupneˇ s kazˇdy´m slovem druhe´ho jazyka). Prˇı´klad 1.7 • Pokud L1 = {abc, aac, cb} a L2 = {baa, cb}, pak L1 · L2 = {abcbaa, abccb, aacbaa, aaccb, cbbaa, cbcb} • Pokud L1 = {ε, ab} a L2 = {bba, cb}, pak L1 · L2 = {ε · baa, ε · cb, abbba, abcb} = {baa, cb, abbba, abcb} • Pokud L1 = {ε, ab} a L2 = {ε, cb}, pak L1 · L2 = {ε · ε, ε · cb, ab · ε, abcb} = {ε, cb, ab, abcb} • Pokud L1 = a∗ a L2 = b∗ , pak L1 · L2 = a∗ b∗ • Pokud L1 = a∗ a L2 = a2 L1 · L2 = a∗ (procˇ?)

n

; n ≥ 0 , pak

M

KAPITOLA 1


8

• L · {ε} = L (pra´zdne´ slovo zde plnı´ u´lohu neutra´lnı´ho prvku) • L · ∅ = ∅ (podobneˇ jako kdyzˇ na´sobı´me nulou) Iterace: Iterace (Kleeneho uza´veˇr) je na´m jizˇ zna´ma´ operace „hveˇzdicˇka“. Definujme postupneˇ: L0 = {ε}

(neutra´lnı´ prvek vzhledem k zrˇeteˇzenı´)

L1 = L n

L L

n+1 ∗

L

n

= L·L , n≥0 0

1

2

= L ∪ L ∪ L ∪ ... =

P

(1.4)

= {w1 · w2 · . . . · wn ; wi ∈ L, 1 ≤ i ≤ n}, n ≥ 1

∞ [

(1.3)

Ln

(1.5) (1.6) (1.7) (1.8)

n=0

Prˇı´klad 1.8

M

• L = {a}, pak L∗ = a∗ • Pokud L = {abc, aac, cb}, pak L∗ = (abc + aac + cb)∗ n

• Pokud L = a2 ; n ≥ 0 , pak L∗ = a∗ (protozˇe do L patrˇ´ı i slovo a, z neˇj lze poskla´dat vsˇechna slova delsˇ´ı nezˇ ε)

• ∅∗ = {ε} (Je to spra´vneˇ? Procˇ ano/ne? Na´poveˇda: dosad’te si do vy´sˇe uvedene´ho vzorce pro iteraci.) • {ε}∗ = {ε}

´ koly U 1. Ktere´ z vy´sˇe uvedenyćh regula´rnıćh operacı´ jsou bina´rnı´ a ktera´ z teˇchto bina´rnıćh je komutativnı´? Jsou asociativnı´? 2. Jsou dańy tyto jazyky: L1 = {ab} L2 = a∗ L3 = (ab)∗ L4 = {ai bi ; i ≥ 0} L5 = {ε, bb}.

Jak vypadajı´ na´sledujıćı´ jazyky?

C

KAPITOLA 1

JAZYKY A REGULA´RNI´ VY´RAZY • L1 · L5 L1 · L2 L1 · L3 L3 · L4

• L1 ∪ L2 L1 ∪ L5 L1 ∪ L3 L1 ∪ L4

9 • L∗1 , L∗2 L∗4 L∗5

L∗3

Jak vı´me z prˇedna´sˇek, regula´rnı´ vy´raz je takove´ vyja´drˇenı´ (za´pis) mnozˇiny rˇeteˇzcu˚, ve ktere´m pouzˇ´ıva´me operace +, zrˇeteˇzenı´ a iterace. Zde jsme probrali trˇi operace nad mnozˇinami rˇeteˇzcu˚ – sjednocenı´, zrˇeteˇzenı´ a iteraci, a nazvali jsme je regula´rnı´mi operacemi. Shrnˇme si nynı´ vztah regula´rnıćh operacı´ k regula´rnı´m vy´razu˚m: Regula´rnı´ vy´raz

Jazyk

∅ ε a, a ∈ Σ

∅, tedy pra´zdny´ jazyk {ε} (jazyk obsahujıćı´ jen slovo s nulovou de´lkou) {a} (jazyk obsahujıćı´ jen slovo a s de´lkou 1) {α} ∪ {β} (sjednocenı´) {α} · {β} (zrˇeteˇzenı´) {α}∗ (iterace)

α+β α·β (α)∗

Tabulka 1.1: Vztah mezi za´pisem regula´rnıćh vy´razu˚ a jazyku˚

1.4.2

Dalsˇı´ potrˇebne´ operace

Pru ˚nik: Do pru˚niku dvou jazyku˚ patrˇ´ı vsˇechna slova, ktera´ jsou jak v prvnı´m, tak (za´rovenˇ) i v druhe´m jazyce. L1 ∩ L2 = {w ∈ Σ∗ ; w ∈ L1 ∧ w ∈ L2 } (1.9)

P

(vsˇimneˇte si vztahu pru˚niku a konjunkce; v podobne´m vztahu pro sjednocenı´ a disjunkce) Prˇı´klad 1.9 • Pokud L1 = {abc, aac, cb} a L2 = {baa, cb}, pak L1 ∩ L2 = {cb} • Pokud L1 = {abc, aac} a L2 = {baa, cb}, pak L1 ∩ L2 = ∅ • Pokud L1 = a∗ a L2 = b∗ , pak L1 ∩ L2 = {ε} n

• Pokud L1 = a∗ a L2 = a2 ; n ≥ 0 , pak L1 ∩ L2 = L2 (protozˇe zde L2 ⊂ L1 )

• L∩∅=∅

M

KAPITOLA 1


10

Rozdı´l: Rozdı´l dvou jazyku˚ je mnozˇina vsˇech slov, ktera´ patrˇ´ı do prvnı´ho z teˇchto jazyku˚ a za´rovenˇ nepatrˇ´ı do druhe´ho jazyka. L1 − L2 = {w ∈ Σ∗ ; w ∈ L1 ∧ w ∈ / L2 } (1.10) Prˇı´klad 1.10

P M

• Pokud L1 = {abc, aac, cb} a L2 = {baa, cb}, pak L1 − L2 = {abc, aac} • Pokud L1 = {abc, aac} a L2 = {abb, abc, aaa, aab, aac}, pak L1 − L2 = ∅ • Pokud L1 = a∗ a L2 = b∗ , pak L1 − L2 = L1 − {ε} = aa∗ • L−∅=L Doplneˇk: Doplneˇk (komplement) jazyka vzhledem k dane´ abecedeˇ Σ je mnozˇina vsˇech slov nad danou abecedou, ktera´ do pu˚vodnı´ho jazyka nepatrˇ´ı. Doplneˇk jazyka L zapisujeme LC nebo L. LC = L = {w ∈ Σ∗ ; w ∈ / L}

P

(1.11)

Prˇı´klad 1.11

M

• Pokud L = {abc, aac, cb}, pak L = Σ∗ − {abc, aac, cb} • Pokud L = {w ∈ Σ∗ ; |w|a > 10}, pak L = {w ∈ Σ∗ ; |w|a ≤ 10} • Pokud L = Σ∗ , pak L = ∅ (a naopak) Take´ zde platı´ DeMorganovy za´kony: L1 ∪ L2 = L1 ∩ L2 L1 ∩ L2 = L1 ∪ L2

nebo nebo

L1 ∪ L2 = L1 ∩ L2 L1 ∩ L2 = L1 ∪ L2

(1.12)

Mnozˇinove´ operace sjednocenı´ a pru˚niku jsou navza´jem dua´lnı´ – navza´jem na sebe prˇeveditelne´ (pokud pouzˇijeme operaci negace) tak, jak vidı´me v DeMorganovyćh za´konech.. Zrcadlovy´ obraz: Zrcadlovy´ obraz (reverze) slova vznikne prˇevraćenı´m tohoto slova. V reverzi jazyka provedeme tote´zˇ s kazˇdy´m slovem tohoto jazyka. LR = L = {wR ; w ∈ L}

(1.13)

L P

KAPITOLA 1


11

Prˇı´klad 1.12

M

• L = {abc, mnp, ε}, pak LR = {cba, pnm, ε} • Pokud L = a∗ , pak LR = a∗ (zmeˇna porˇadı´ symbolu˚ nenı´ poznatelna´, tote´zˇ platı´ pro vsˇechny jazyky nad jednoznakovou abecedou) • L = {an bn ; n ≥ 0}, pak LR = {bn an ; n ≥ 0} • L = {wcwR ; w ∈ {a, b}∗ }, pak LR = {wcwR ; w ∈ {a, b}∗ } Pozitivnı´ iterace: Pozitivnı´ iterace (operace „plus“ je definovańa podobneˇ jako iterace: L+ = L1 ∪ L2 ∪ . . . =

∞ [

Ln

(1.14)

P

(1.15)

n=1

Homomorfismus: Morfismus (homomorfismus – je to tote´zˇ) je zobrazenı´ h zachova´vajıćı´ neutra´lnı´ prvek (zde ε) a operaci na dane´ strukturˇe (u na´s zrˇeteˇzenı´) v dane´ abecedeˇ Σ, tj. splnˇuje homomorfnı´ podmıńky:

P

1. h(ε) = ε 2. h(a · w) = h(a) · h(w),

a ∈ Σ, w ∈ Σ∗

Pokud zobrazenı´ splnˇuje homomorfnı´ podmıńky, lze je definovat jednodusˇeji – pro jednotlive´ symboly jazyka. Platı´ vzorec: [ h(L) = h(w) (1.16) w∈L

Prˇı´klad 1.13 Na jazyk L = {a2 bi (ab)i+1 ; i ≥ 1} uplatnı´me homomorfismy h1 a h2 definovane´ na´sledovneˇ: h1 (a) = cd h1 (b) = c3

h2 (a) = c h2 (b) = c

Potom platı´: h1 (L) = {(cd)2 c3i (cdc3 )i+1 ; i ≥ 1} ∗ h2 (L) = ci+2 (cc)i+1 ; i ≥ 1 = c3i+4 ; i ≥ 1 = c4 c3 c3

M

KAPITOLA 1


12

´ koly U 1. Ktere´ z vy´sˇe uvedenyćh operacı´ jsou bina´rnı´ a ktere´ z teˇchto bina´rnıćh jsou komutativnı´? Jsou asociativnı´?

C

2. Jsou dańy tyto jazyky: L1 = {ab} L2 = a∗ L3 = (ab)∗ L4 = {ai bi ; i ≥ 0} L5 = {ε, bb}.

Jak vypadajı´ na´sledujıćı´ jazyky? • L1 ∩ L3 L1 ∩ L4 L2 ∩ L5

• L2 − L1 L1 − L3 L5 − L3

• L1 L+ 1, L+ 5

L+ 3

• LR 1, LR 2 LR 4

LR 3

3. Je dań homomorfismus h definovany´ na´sledovneˇ: h(a) = 01, h(b) = 10. • Urcˇete h(L1 ), pokud L1 = {ε, aa, ab, aab} • Urcˇete h(L2 ), pokud L2 = (ab)∗ • Urcˇete h(L3 ), pokud L3 = a∗ abb∗

1.4.3

Prefixy a postfixy slov

Na´sledujıćı´ operace na´m umozˇnˇujı´ pracovat s prefixy (predponami) a postfixy (prˇ´ıponami) slov. Levy´ a pravy´ deriva´t urcˇujı´ mnozˇinu slov dane´ho jazyka, jejichzˇ prefixem cˇi postfixem je dane´ slovo, levy´ a pravy´ kvocient pouzˇ´ıvajı´ mı´sto jednoho prefixu cˇi postfixu celou mnozˇinu (tedy jiny´ jazyk).

Levy´ a pravy´ deriva´t: Levy´ deriva´t jazyka L podle slova x je mnozˇina vsˇech slov takovyćh, zˇe pokud je k nim zleva operacı´ zrˇeteˇzenı´ prˇidańo slovo x, patrˇ´ı do jazyka L. δxl (L) = {w ∈ Σ∗ ; x · w ∈ L}

(1.17)

Pravy´ deriva´t jazyka L podle slova x je mnozˇina vsˇech slov takovyćh, zˇe pokud je k nim zprava operacı´ zrˇeteˇzenı´ prˇidańo slovo x, patrˇ´ı do jazyka L. δxr (L) = {w ∈ Σ∗ ; w · x ∈ L}

(1.18)

Prˇı´klad 1.14 Pokud L = {(ab)i (ba)i ; i ≥ 2}, pak l (L) = {(ab)i−1 (ba)i ; i ≥ 2} • δab

r • δbaba (L) = {(ab)i (ba)i−2 ; i ≥ 2} = {(ab)i+2 (ba)i ; i ≥ 0}

r i+4 (ba)i ; i ≥ 0} (vs • δ(ba) ˇ imneˇte si, zˇe neˇktera´ slova jazyka L do vy´sledne´ho 4 (L) = {(ab) jazyka nebyla vu˚bec zarˇazena)

M

KAPITOLA 1


13

Levy´ a pravy´ kvocient: Jedna´ se o zobecneˇnı´ leve´ho a prave´ho deriva´tu. Levy´ kvocient jazyka L1 vzhledem k jazyku L2 je sjednocenı´m levyćh deriva´tu˚ jazyka L1 vzhledem ke vsˇem slovu˚m jazyka L2 . Podobneˇ pravy´ kvocient jazyka L1 vzhledem k jazyku L2 je sjednocenı´m pravyćh deriva´tu˚ jazyka L1 vzhledem ke vsˇem slovu˚m jazyka L2 . ∗ L2 \ L1 = {w ∈ Σ ; existuje x ∈ L2 tak, zˇe x · w ∈ L1 } = {w ∈ δxl (L1 ) ; x ∈ L2 }

L1 \ L

2

= {w ∈ Σ∗ ; existuje x ∈ L2 tak, zˇe w · x ∈ L1 }

= {w ∈ δxr (L1 ) ; x ∈ L2 }

(1.19) (1.20)

Mnemotechnicka´ pomu˚cka: z toho jazyka, ktery´ je „nı´zˇe“, bereme prefix (tj. slovo x z vy´sˇe uvedenyćh vzorcu˚). Ten jazyk, ktery´ je „vy´sˇe“, bude zleva nebo zprava „osekań“. Prˇı´klad 1.15 Jsou dańy tyto jazyky: L1 = {ab, aab, ac} L2 = {ai bci ; i ≥ 0}

L3 = a∗ L4 = a∗ b∗

L5 = (ab)∗ L6 = (ab)+

L7 = {ε, abc, ab}

Stanovı´me tyto leve´ a prave´ kvocienty: • L1 \ L2 = {c, cc} (vsˇimneˇte si, zˇe opravdu jde o konecˇny´ jazyk, trˇebazˇe L2 je nekonecˇny´) • L2 \ L1 = ∅ (protozˇe zˇa´dne´ slovo z jazyka L2 nenı´ prefixem zˇa´dne´ho slova jazyka L1 ; pozor, nejkratsˇ´ı slovo z jazyka L2 je b, nikoliv ε) • L \ L2 = {am bci ; 0 ≤ m ≤ i} (postup: vezmeme slovo z L2 , naprˇ´ıklad a4 bc4 , a pouzˇijeme 3

jako prefixy postupneˇ slova ε, a, a2 , a3 , a4 z jazyka L3 – vsˇechna do de´lky pocˇtu symbolu˚ a ve sloveˇ z jazyka L2 , pak dalsˇ´ı slovo, atd.) • L4 \L2 = L2 ∪ {am bci ; 0 ≤ m ≤ i} ∪ {ci ; i ≥ 0} (prvnı´ cˇa´st: z L4 zvolı´me ε; druha´ cˇa´st: z L4 zvolı´me slova a∗ ; trˇetı´ cˇa´st: z L4 zvolı´me a∗ b) protozˇe L2 ⊂ {am bci ; 0 ≤ m ≤ i}, vy´sledek mu˚zˇeme zjednodusˇit; jak? • L \ L2 = L2 ∪ {c} (pokud x = ε, pak zı´ska´me L2 ; pokud x = {ab}, zı´ska´me {c}; dalsˇ´ı slova z 5

L4 nelze pouzˇ´ıt) • L6 \ L2 = {c} • L \ L2 = L2 ∪ {ε, c} 7

• L1 \ L5 = L1 ∪ {ε, a} (pozor, ted’ uzˇ pocˇ´ıta´me pravy´ kvocient) • L1 \ L = {ε, a} 6

L M

KAPITOLA 1

1.5


14

K vlastnostem jazyku˚

Prˇı´klad 1.16 Jesˇteˇ si trochu procvicˇ´ıme operace nad jazyky.

M

• L1 = {ai bj ; i, j ≥ 0} L2 = {w ∈ {a, b}∗ ; |w|a = |w|b } L1 ∩ L2 = {an bn ; n ≥ 0} j i LR 1 = {b a ; i, j ≥ 0} LR ˇ de´ slovo po reverzi opeˇt patrˇ´ı do pu˚vodnı´ho jazyka a naopak) 2 = L2 (kaz • L1 = (ab)∗ L2 = (ba)∗ L1 ∩ L2 = {ε} L1 ∪ L2 = (ab)∗ + (ba)∗ R LR 1 = L2 , L2 = L1 • L1 = a∗ L2 = b∗ L1 ∩ L2 = {ε} L1 ∪ L2 = a∗ + b∗ (pozor, ne (a + b)∗ , ve slovech budou vzˇdy bud’ jen symboly a nebo jen symboly b) {a, b}∗ − L1 = {w ∈ {a, b}∗ ; |w|b ≥ 1} (procˇ?) R LR 1 = L1 , L2 = L2 n n n • L1 = {a n c b ; n ≥ 0} o L2 = wcwR ; w ∈ {a, b}∗ L1 ∩ L2 = {acb} L1 − L2 = {an cn bn ; n ≥ 2} ∪ {ε} = L1 − {abc} (vsˇimneˇte si minima pro hodnotu n) n n n LR 1 = {b c a ; n ≥ 0} LR 2 = L2

• L1 = a∗ n L2 = {a2 ; n ≥ 0} L1 ∪ L2 = L1 (protozˇe L2 ⊂ L1 ) L1 ∩ L2 = L2 (z te´hozˇ du˚vodu) L2 − L1 = ∅ (ale naopak by to neplatilo, operace − nenı´ komutativnı´) Z prˇ´ıkladu 1.16 je zrˇejme´, zˇe a∗ + b∗ 6= (a + b)∗ Take´ bychom si meˇli da´vat pozor na to, zˇe operace zrˇeteˇzenı´ nenı´ komutativnı´ (nicmeńeˇ asociativnı´ je). Naproti tomu operace + ma´ stejne´ vlastnosti jako operace sjednocenı´ mnozˇin, vcˇetneˇ vlastnosti komutativity a asociativity.

L

KAPITOLA 1


15

Prˇı´klad 1.17 Najdeme jazyk L, ktery´ splnˇuje danou vlastnost:

M

• L=L·L

naprˇ´ıklad: L = {a, b}∗ , protozˇe platı´ {a, b}∗ · {a, b}∗ = {a, b}∗ jine´ mozˇnosti: L = a∗ , L = (ab)∗ , L = {ε}, L = {w ∈ {a, b}∗ ; |w|a = |w|b }, atd. n sˇpatneˇ by bylo naprˇ´ıklad L = {a}, L = {ab, bc}, L = {a2 }, L = {w ∈ {a, b}∗ ; |w|a = |w|b +1}

• L = L∗

naprˇ´ıklad: L = a∗ , protozˇe jak L, tak i L∗ obsahujı´ pra´veˇ vsˇechny rˇeteˇzce nad abecedou {a} jine´ mozˇnosti: L = {a, b}∗ , L = {w ∈ {a, b}∗ ; |w|a = |w|b }, L = {ε}, atd. sˇpatneˇ by bylo naprˇ´ıklad L = {ab, aa}, L = {an bn ; n ≥ 0}, L = a+

• L∗ = L+

naprˇ´ıklad: L = {an bn ; n ≥ 0}, protozˇe L∗ i L+ obsahujı´ tata´zˇ slova vcˇetneˇ ε jine´ mozˇnosti: L = a∗ , L = {a, b}∗ , L = {w ∈ {a, b}∗ ; |w|a = |w|b }, atd. (je trˇeba, aby ε ∈ L) sˇpatneˇ by bylo naprˇ´ıklad L = {an bn ; n ≥ 1}, L = {w ∈ {a, b}∗ ; |w|a < |w|b }

• L ∩ LR = ∅

naprˇ´ıklad: L = {an bn ; n ≥ 1} (v reverzi je opacˇne´ porˇadı´ a a b, v jazycıćh nenı´ slovo ε) jine´ mozˇnosti: L = (ab)∗ ab, L = {abc} sˇpatneˇ by bylo naprˇ´ıklad L = (ab)∗ , L = {a, b}∗ , L = {w ∈ {a, b}∗ ; |w|a = |w|b }

• L∗ = L ∪ {ε}

naprˇ´ıklad: L = {w ∈ {a, b}∗ ; |w|a < |w|b }, zde nevadı´, zˇe v L nenı´ ε jine´ mozˇnosti: L = a∗ , L = {a, b}∗ , L = {an bn ; n ≥ 1}, atd. sˇpatneˇ by bylo naprˇ´ıklad L = {abc}, L = {an bn ; n ≥ 1}

Prˇı´klad 1.18 Najdeme jazyk L, ktery´ nesplnˇuje danou vlastnost: • L = L∗

naprˇ´ıklad: L = {abc, ba}, protozˇe L∗ = {ε, abc, ba, abcabc, abcba, baba, baabc, . . .} sˇpatneˇ: L = a∗ , protozˇe L∗ = (a∗ )∗ = a∗ (pozor, v zadańı´ je „nesplnˇuje“)

• L ∩ LR = ∅

naprˇ´ıklad: L = {an bn ; n ≥ 0}, protozˇe L i L∗ obsahujı´ slovo ε sˇpatneˇ: L = {an bn ; n ≥ 1}, zde opravdu L a R nemajı´ zˇa´dne´ spolecˇne´ slovo, jsou disjunktnı´

M

KAPITOLA 1


16

´ koly U 1. Ke kazˇde´mu vztahu napisˇte jazyk La , ktery´ danou vlastnost splnˇuje, a jazyk Ln , ktery´ danou vlastnost nesplnˇuje:

C

• L = LR • L ∩ L∗ = {ε} • L = {a, b}∗ − L

2. Ke vsˇem vlastnostem z prˇ´ıkladu˚ 1.16 a 1.18 urcˇete, zda je na´sledujıćı´ jazyky splnˇujı´: ∗ • L1 = {a, n b, c} o • L2 = wcwR ; w ∈ {a, b}∗

n

• L3 = wwR ; w ∈ {a, b}∗ n

• L4 = a2

; n≥0

o

3. Je dań jazyk L = (ab)∗ b(ba)∗ a na´sledujıćı´ homomorfismy: h1 (a) = 01 h1 (b) = 10

h2 (a) = 0 h2 (b) = 00

Zjisteˇte jazyky h1 (L) a h2 (L). 4. Prˇipomenˇte si, jak je u algebraickyćh struktur definovańa vlastnost komutativity, asociativity a distributivity. Zjisteˇte, zda je operace zrˇeteˇzenı´ distributivnı´ vzhledem k operaci + a naopak. 5. Je dań jazyk L = {vypsat, vylı´t, vymazat}. Vytvorˇte: l = • {vy} \ L = δvy

• {prˇe} · {vy} \ L =

R

Kapitola

2

Konecˇne´ automaty Konecˇny´ automat je jednoduchy´ matematicky´ model, ktery´ se skla´da´ z rˇ´ıdicı´ jednotky (vcˇetneˇ stavu), vstupnı´ pa´sky (vstupnı´ soubor cˇi jina´ datova´ struktura) a cˇtecı´ hlavy. V kazˇde´m kroku tento automat nacˇte jeden symbol ze vstupu a cˇinnost v tomto kroku je urcˇena podle tohoto nacˇtene´ho symbolu a momenta´lnı´ho stavu, spocˇ´ıva´ ve zmeˇneˇ stavu.

2.1

Vytva´rˇı´me konecˇny´ automat

P

Konecˇny´ automat lze zapsat celkem trˇemi zpu˚soby: 1. pouzˇitı´m plne´ specifikace s δ-funkcı´ 2. stavovy´m diagramem 3. tabulkou prˇechodu˚ Uka´zˇeme si vsˇechny trˇi zpu˚soby. Exaktnı´ postup vytvorˇenı´ konecˇne´ho automatu si uka´zˇeme pozdeˇji (kapitola 2.8 na straneˇ 44), ale abychom mohli sestrojovat uzˇ ted’ alesponˇ mensˇ´ı konecˇne´ automaty, podı´va´me se na zjednodusˇeny´ postup. Prˇı´klad 2.1 Vytvorˇ´ıme konecˇny´ automat pro jazyk L = a (a (a + b) a)∗ bb∗ = a · (a · (a + b) · a)∗ · b · b∗ ve vsˇech trˇech reprezentacıćh. U mensˇ´ıch automatu˚ je nejjednodusˇsˇ´ı vytvorˇit stavovy´ diagram: a q0 a a, b q4

δ-funkce vcˇetneˇ plne´ specifikace: A = ({q0 , q1 , q2 , q3 , q4 }, {a, b}, δ, q0 , {q3 })

b q3 q1 a b q2

δ(q0 , a) = q1 δ(q1 , a) = q2 δ(q1 , b) = q3 δ(q2 , a) = q4

17

δ(q2 , b) = q4 δ(q4 , a) = q1 δ(q3 , b) = q3

M

KAPITOLA 2

KONECˇNE´ AUTOMATY

18 a

Tabulka prˇechodu˚:

→ q0 q1 q2 ← q3 q4

q1 q2 q4

b q3 q4 q3

q1

Zatı´mco u stavove´ho diagramu a tabulky prˇechodu˚ nemusı´me uva´deˇt plnou specifikaci – rˇeteˇzec A = ({q0 , q1 , q2 , q3 }, {a, b}, δ, q0 , {q3 }), prˇi pouzˇitı´ δ-funkce je plna´ specifikace nutna´. Bez nı´ bychom nepoznali, ktery´ stav je pocˇa´tecˇnı´ a ktere´ stavy jsou koncove´.

Prˇı´klad 2.2 Sestrojı´me konecˇny´ automat rozpozna´vajıćı´ cela´ cˇ´ısla. Pouzˇ´ıva´me cˇ´ıslice 0 . . . 9, cˇ´ıslo se musı´ skla´dat z alesponˇ jedne´ cˇ´ıslice. Vıćeciferna´ cˇ´ısla nesmı´ zacˇ´ınat nulou. Vytvorˇ´ıme automat se trˇemi stavy. Oddeˇlı´me zpracovańı´ jednociferne´ho cˇ´ısla „0“ od ostatnıćh, ktera´ nulou nesmı´ zacˇ´ınat.

q0 1, . . . , 9 q1 0, . . . , 9 0 q2

´ koly U 1. Pro na´sledujıćh sˇest jazyku˚ sestrojte konecˇny´ automat ve vsˇech trˇech reprezentacıćh: (d) (ab)∗ ba (a) a∗ b (e) {abi ; i ≥ 1} ∪ {bai ; i ≥ 0} (b) {0, 1}∗ 11 ∗ (f) a∗ · {a, bc} (c) 11{0, 1} 2. Podle zadańı´ vytvorˇte zbyle´ dveˇ reprezentace dane´ho konecˇne´ho automatu. (a) Podle δ-funkce vytvorˇte stavovy´ diagram a tabulku prˇechodu˚: A1 = ({q0 , q1 , q2 }, {a, b, c}, δ, q0 , {q1 , q2 }) δ(q0 , a) = q1 δ(q1 , c) = q1 δ(q0 , b) = q2 δ(q2 , c) = q1

M C

(b) Podle kazˇde´ tabulky prˇechodu˚ vytvorˇte stavovy´ diagram a δ-funkci s plnou reprezentacı´ automatu: 0 1 a b →A B ←C ←D

B B D

C C D

↔ q0 q1 ← q2 ← q3

q1 q1 q3

q0 q2

KAPITOLA 2


19

Vsˇimneˇte si, zˇe podle druhe´ tabulky je pocˇa´tecˇnı´ stav za´rovenˇ koncovy´ (sˇipka vede obeˇma smeˇry). (c) Podle kazˇde´ho stavove´ho diagramu vytvorˇte tabulku prˇechodu˚ a δ-funkci s plnou reprezentacı´ automatu: 0,1 1 0 0 q2 q1 q0

a q0 b

q1 c c b q2 a

q3

3. Sestrojte konecˇny´ automat (stavovy´ diagram) rozpozna´vajıćı´ rea´lna´ cˇ´ısla. Cela´ cˇa´st je podle zadańı´ v prˇedchozı´m prˇ´ıkladu, na´sleduje desetinna´ cˇa´rka a pak opeˇt sekvence cˇ´ıslic (alesponˇ jedna, mu˚zˇe to by´t i cˇ´ıslice 0). 4. Podle stavove´ho diagramu pro rea´lna´ cˇ´ısla vytvorˇte tabulku prˇechodu˚.

2.2

Nedeterministicky´ konecˇny´ automat

Nedeterministicky´ konecˇny´ automat je takovy´ automat, kde v alesponˇ jednom stavu lze na neˇktery´ signa´l reagovat vıće ru˚zny´mi zpu˚soby. Protozˇe se tento typ automatu sˇpatneˇ programuje (je teˇzˇke´ vlozˇit do instrukcı´ na´hodnost – zvolit jednu z nabı´zenyćh cest, a to pokud mozˇno tak, aby vedla „spra´vny´m smeˇrem“, do koncove´ho stavu), mu˚zˇe se hodit postup, jak nedeterministicky´ automat prˇeve´st na deterministicky´ se zachovańı´m rozpozna´vane´ho jazyka. Prˇı´klad 2.3 Zadany´ nedeterministicky´ automat prˇevedeme na deterministicky´ (je dań stavovy´ diagram a tabulka prˇechodu˚). 0 q0 0, 1

0 q1

q2

↔ q0 q1 ← q2

0

1

q1 q0 , q2

q0

Tento prˇevod je nejjednodusˇsˇ´ı na tabulce prˇechodu˚. V neˇkteryćh bunˇkaćh je vıće nezˇ jedna polozˇka, proto obsah buneˇk budeme cha´pat jako mnozˇiny. Vytva´rˇ´ıme tedy novy´ konecˇny´ (deterministicky´) automat takovy´, zˇe jeho stavy jsou mnozˇinami stavu˚ pu˚vodnı´ho automatu. Novou tabulku prˇechodu˚ tedy vytvorˇ´ıme z pu˚vodnı´ tabulky tak, zˇe nejdrˇ´ıv jak obsah buneˇk, tak i stavy v oznacˇenı´ rˇa´dku˚ uzavrˇeme do mnozˇinovyćh za´vorek. Tı´m ale v neˇkteryćh bunˇkaćh (zde v jedne´) dostaneme stav, ktery´ nenı´ v oznacˇenı´ zˇa´dne´ho rˇa´dku. To napravı´me jednodusˇe tak, zˇe prˇida´me novy´ rˇa´dek tabulky s tı´mto oznacˇenı´m a obsah buneˇk zjistı´me sjednocenı´m rˇa´dku˚ pu˚vodnı´ tabulky oznacˇenyćh prvky mnozˇiny, se kterou pra´veˇ pracujeme:

P M

KAPITOLA 2 ... {A} ... {B} {C} ...


20

...

{B, C}

...

{D, E} {F }

... ...

{G} {H, I}

⇒

{B, C} ...

... {A} ... {B} {C} ... {B, C}

...

{D, E, F } ... {G, H, I}

{D, E} {F }

{G, H} {H, I}

... ...

Mu˚zˇe se sta´t, zˇe sjednocenı´m mnozˇin v bunˇkaćh opeˇt vznikne mnozˇina, ktera´ se nenacha´zı´ v oznacˇenı´ zˇa´dne´ho rˇa´dku. Pak opeˇt vytvorˇ´ıme novy´ rˇa´dek a pro bunˇky pouzˇijeme operaci sjednocenı´ mnozˇin. Postup je tedy rekurzivnı´. Takzˇe k prˇ´ıkladu: 0 ↔ {q0 } {q1 } ← {q2 }

{q1 } {q0 , q2 }

1 {q0 }

⇒

↔ {q0 } {q1 } ← {q2 } ← {q0 , q2 }

0

1

{q1 } {q0 , q2 } ∅ {q1 } ∪ ∅ = {q1 }

∅ {q0 } ∅ ∅∪∅=∅

Vlastnost „by´t koncovy´m stavem“ se take´ deˇdı´ v ra´mci sjednocenı´ – pokud alesponˇ jeden z prvku˚ mnozˇiny stavu˚ je v pu˚vodnı´m automatu koncovy´m stavem, sta´va´ se koncovy´m stavem i cela´ tato mnozˇina. Uvedeny´ postup je vlastneˇ zkraćeny´. Ve skutecˇnosti bychom meˇli postupovat tak, zˇe bychom jako stavy pouzˇili vsˇechny mozˇne´ kombinace stavu˚ a opeˇt operaci sjednocenı´ mnozˇin:

↔ {q0 } {q1 } ← {q2 }

← {q0 , q1 } ← {q0 , q2 } ← {q1 , q2 } ← {q0 , q1 , q2 }

0

1

{q1 } {q0 , q2 } ∅

∅ {q0 } ∅

{q0 , q1 , q2 } {q1 } {q0 , q2 } {q0 , q1 , q2 }

{q0 } ∅ {q0 } {q0 }

0

1 q0

0 q0 , q1 0

0

q1 , q2 1 0

q2

q1

q0 , q2

0

1

q0 , q1 , q2

0

Ve stavove´m diagramu mu˚zˇeme videˇt, zˇe stavy, ktere´ jsou oproti prˇedchozı´mu postupu navıć, jsou nedosazˇitelne´ z pocˇa´tecˇnı´ho stavu a tedy se nenacha´zejı´ na zˇa´dne´ cesteˇ prˇi zpracovańı´ slov jazyka. Proto je vlastneˇ mu˚zˇeme bez u´jmy na obecnosti z automatu odstranit.

KAPITOLA 2


21

´ koly U Uvedene´ nedeterministicke´ konecˇne´ automaty reprezentovane´ tabulkami prˇeved’te na ekvivalentnı´ deterministicke´. Ke kazˇde´mu vytvorˇte stavovy´ diagram pu˚vodnı´ho nedeterministicke´ho automatu i vytvorˇene´ho deterministicke´ho a porovnejte. a ↔ X Y Z

2.3

Y Z X

b → q0 ← q1 ← q2

X, Z

0

1

q0 , q1

q0 , q1 q1 , q2

→ q0 q1 ← q2

a

b

q1 , q2 q2 q0

q1 q1 , q2

C

c

q2

Tota´lnı´ automat

V tota´lnı´m (u´plne´m) automatu lze v kazˇde´m stavu reagovat na jaky´koliv symbol. Prˇi prˇevodu (netota´lnı´ho) automatu na tota´lnı´ vytvorˇ´ıme novy´ stav („odpadkovy´ kosˇ“, chybovy´ stav), do ktere´ho prˇesmeˇrujeme vsˇechny chybeˇjıćı´ prˇechody. Nesmı´me zapomenout, zˇe pozˇadavek mozˇnosti reakce na ktery´koliv symbol se vztahuje take´ na tento noveˇ prˇidany´ stav. Postup prˇevodu na tota´lnı´ automat lze pouzˇ´ıt pouze na deterministicky´ konecˇny´ automat, proto u nedeterministicke´ho automatu je prvnı´m krokem vzˇdy prˇevod na deterministicky´. Prˇı´klad 2.4 K zadane´mu deterministicke´mu konecˇne´mu automatu vytvorˇ´ıme ekvivalentnı´ tota´lnı´ automat:

↔ q0 q1 ← q2

a

b

q1 q2

q1

c

q2

a q0

b a q1

c q2

Tento automat urcˇiteˇ nenı´ tota´lnı´ – naprˇ´ıklad ve stavu q0 nelze reagovat hned na dva signa´ly. Vytvorˇ´ıme novy´ stav, oznacˇ´ıme jej symbolem ∅ a prˇesmeˇrujeme do tohoto stavu vsˇechny chybeˇjıćı´ prˇechody:

↔ q0 q1 ← q2 ∅

a

b

c

q1 q2 ∅ ∅

∅ q1 ∅ ∅

∅ ∅ q2 ∅

a q0 b, c

c b a q2 q1 c a, b ∅ a, b, c

P M

KAPITOLA 2


22

Prˇı´klad 2.5 V prˇ´ıkladu 2.3 jsme k nedeterministicke´mu automatu vytvorˇili ekvivalentnı´ deterministicky´. Tento deterministicky´ automat nynı´ zu´plnı´me (prˇevedeme na tota´lnı´). Stav {q2 } nenı´ dosazˇitelny´ z pocˇa´tecˇnı´ho stavu, proto jej take´ vypustı´me. Abychom trochu zjednodusˇili znacˇenı´, budeme mı´sto mnozˇin {. . .} pouzˇ´ıvat velka´ pı´smena, provedeme prˇeznacˇenı´: Pu˚vodnı´: Prˇeznacˇeny´: Tota´lnı´: 0 1 0 1 0 1 ↔ {q0 } {q1 } ← {q0 , q2 }

{q1 } {q0 , q2 } {q1 }

∅ {q0 } ∅

⇒

↔ A B ← C

B C B

∅ A ∅

Stavove´ diagramy prˇeznacˇene´ho a zu´plneˇne´ho automatu: 0

1 A

0 B 0

C

↔ A B ← C ∅

⇒

0

1 A

1

0 B 0

1 ∅ 0,1

B C B ∅

∅ A ∅ ∅

C

´ koly U 1. Vsˇechny konecˇne´ automaty, ktere´ jste v u´kolu cˇ. 2.2.2 na straneˇ 21 prˇevedli na deterministicke´, zu´plnˇte (prˇeved’te na tota´lnı´). 2. Na´sledujıćı´ konecˇny´ automat prˇeved’te na tota´lnı´ a nakreslete jeho stavovy´ diagram (signa´l v za´hlavı´ poslednı´ho sloupce je desetinna´ cˇa´rka):

→A ←B ←C D ←E

0

1, . . . , 9

C B

B B

E E

E E

, D D

1, . . . , 9 0, . . . , 9 B A 0, . . . , 9 0 , , 0, . . . , 9 C E D

3. Na´sledujıćı´ (nedeterministicky´!) konecˇny´ automat zu´plnˇte. 0 →A B ←C

B B, C

1 A A, C

0 A 1

0 0 B

M

1 C

1

C

KAPITOLA 2

2.4


23

Konecˇne´ jazyky

Vsˇechny konecˇne´ jazyky jsou regula´rnı´, proto pro neˇ doka´zˇeme sestrojit konecˇny´ automat. U konecˇne´ho automatu pro konecˇny´ jazyk by´va´ obvykly´ pozˇadavek na rozlisˇitelnost nacˇ´ıtanyćh slov podle koncove´ho stavu, tedy pro kazˇde´ slovo jazyka by meˇl existovat samostatny´ koncovy´ stav. Pak bez nutnosti porovna´vańı´ vstupu s jednotlivy´mi slovy jazyka snadno zjistı´me, ktere´ slovo bylo nacˇteno – podle koncove´ho stavu, ve ktere´m skoncˇil vy´pocˇet. Postup je jednoduchy´ – pro kazˇde´ slovo jazyka vytvorˇ´ıme „veˇtev“ ve stavove´m diagramu. Jestlizˇe chceme automat deterministicky´ (opeˇt jde o obvykly´ pozˇadavek, pokud tento postup pouzˇ´ıva´me prˇi programovańı´), stacˇ´ı sloucˇit pocˇa´tky teˇch veˇtvı´, ktere´ stejneˇ zacˇ´ınajı´ (konce veˇtvı´ nesmı´me sloucˇit, nebylo by mozˇne´ rozpoznat slova jazyka podle koncovyćh stavu˚!). Prˇı´klad 2.6 Podle zadane´ho konecˇne´ho jazyka vytvorˇ´ıme konecˇny´ automat. L = {hrad, hrom, polom, ohrada} d q3 m q7 q11 o q16 a

a d r q2 q3 q1 h o m q7 q0 p o q11 o q10 l q9 o q16 a q15 r q14 h

r q1 h r h q5 q0 p o q9 o q14 h

a q2 o q6 q10 l q15 r

q4

q12 m q13 q19 q18 a q17 d q8

Da´le chceme, aby automat byl deterministicky´ se zachovańı´m mozˇnosti rozlisˇit rozpozna´vana´ slova podle koncove´ho stavu. Prvnı´ dveˇ slova jazyka zacˇ´ınajı´ stejny´m podrˇeteˇzcem, tedy zacˇa´tky prvnıćh dvou veˇtvı´ sloucˇ´ıme: q4

q12 m q13 q19 q18 a q17 d q8

Kdybychom netrvali na podmıńce odlisˇenı´ slov koncovy´mi stavy, bylo by mozˇne´ sloucˇit vsˇechny koncove´ stavy v jeden, a take´ stavy q7 a q12 .

V konecˇne´m automatu pro konecˇny´ jazyk nesmı´ (a ani nemu˚zˇe) by´t zˇa´dna´ smycˇka (cyklus) – kdyby byla, pak by bylo mozˇne´ tuto smycˇku jaky´kolivpocˇetkra´t zopakovat a rozpozna´vany´ jazyk by byl nekonecˇny´.

M

KAPITOLA 2


24

´ koly U 1. Vytvorˇte konecˇny´ automat pro na´sledujıćı´ jazyky (deterministicky´, a to tak, aby pro kazˇde´ slovo jazyka existoval jeden konecˇny´ stav): (a) (b) (c) (d)

La = {strom, stroj, vy´stroj} Lb = {if, else, elif} Lc = {read, write, writeall, matrix} Ld = {delfıń, ryba, velryba}

Pozna´mka: V prˇ´ıpadeˇ (c) bude koncovy´ stav veˇtve pro druhe´ slovo soucˇa´stı´ veˇtve pro trˇetı´ slovo (pokud vytvorˇ´ıme deterministicky´ automat). To je v porˇa´dku, vlastnost rozpozna´vańı´ podle koncove´ho stavu zu˚sta´va´ zachovańa. 2. Vytvorˇte konecˇny´ automat (stavovy´ diagram), ktery´ bude rozpozna´vat vsˇechna slova nad abecedou Σ = {a, b, c}, jejichzˇ de´lka je (a) pra´veˇ 3 znaky, (b) nejvy´sˇe 3 znaky (tj. 0, 1, 2 nebo 3 znaky). Na´poveˇda: Jde o konecˇne´ jazyky. Vı´me, zˇe v automatu pro konecˇny´ jazyk nesmı´ by´t cyklus, a take´ vı´me, zˇe prˇechody ve stavove´m diagramu mohou by´t oznacˇeny vıće nezˇ jednı´m znakem.

2.5

Odstraneˇnı´ nepotrˇebnyćh stavu˚ (redukce)

Nepotrˇebne´ stavy jsou stavy, ktere´ nejsou pouzˇity prˇi zˇa´dne´m u´speˇsˇne´m vy´pocˇtu (tj. koncˇ´ıcı´m v koncove´m stavu). Jedna´ se o stavy • nedosazˇitelne´ – neexistuje k nim cesta z pocˇa´tecˇnı´ho stavu, • nadbytecˇne´ – neexistuje cesta z tohoto stavu do jake´hokoliv koncove´ho stavu. S odstranˇovańı´m (le´pe rˇecˇeno ignorovańı´m, neuvedenı´m cˇi vypusˇteˇnı´m) prvnı´ho typu nepotrˇebnyćh stavu˚ – nedosazˇitelnyćh – jsme se setkali uzˇ u zkraćene´ho postupu pro prˇevod nedeterministicke´ho automatu na deterministicky´. Pokud nove´ rˇa´dky tabulky prˇechodu˚ tvorˇ´ıme jen pro takove´ mnozˇiny pu˚vodnıćh stavu˚, ktere´ se jizˇ vyskytly v neˇktere´ bunˇce, veˇtsˇinu nedosazˇitelnyćh stavu˚ (ale ne vzˇdy vsˇechny) automaticky odstranˇujeme. Kdyzˇ chceme odstranit nepotrˇebne´ stavy, vzˇdy zacˇ´ına´me nedosazˇitelny´mi stavy a azˇ potom odstranı´me nadbytecˇne´. V obou prˇ´ıpadech postupujeme rekurzı´vneˇ, a to bud’ podle stavove´ho diagramu nebo podle tabulky prˇechodu˚. • nedosazˇitelne´ stavy: jako ba´zi (za´kladnı´ mnozˇinu) zvolı´me S0 = {q0 } (obsahuje pouze pocˇa´tecˇnı´ stav), dalsˇ´ı prvky prˇida´va´me „ve smeˇru sˇipek“ v stavove´m diagramu, resp. v tabulce prˇechodu˚ ve smeˇru oznacˇenı´ rˇa´dku → obsah buneˇk na rˇa´dku, postupneˇ vytva´rˇ´ıme mnozˇinu vsˇech stavu˚, do kteryćh vede cesta z pocˇa´tecˇnı´ho stavu o de´lce max. 0, 1, . . . , n kroku˚ (toto cˇ´ıslo je dolnı´ index u oznacˇenı´ vytva´rˇene´ mnozˇiny Si );

C

KAPITOLA 2


25

• nadbytecˇne´ stavy: jako ba´zi naopak zvolı´me mnozˇinu koncovyćh stavu˚ – E0 = F , dalsˇ´ı prvky prˇida´va´me „proti smeˇru sˇipek“ v stavove´m diagramu, resp. ve smeˇru obsah neˇktere´ bunˇky tabulky prˇechodu˚ → oznacˇenı´ rˇa´dku, vytva´rˇ´ıme mnozˇinu vsˇech stavu˚, ze kteryćh vede cesta do neˇktere´ho koncove´ho stavu o de´lce max. 0, 1, . . . , n kroku˚. Prˇı´klad 2.7 V zadane´m konecˇne´m automatu odstranı´me nedosazˇitelne´ a nadbytecˇne´ stavy.

→ q0 ← q1 q2 q3 ← q4 ← q5

a

b

q1 q1 q3 q3 q5 q5

q3 q2

q2

c q5 q0 q3

a q0 c b a q3 a

M

a c q1 b b q2 c

a

a q5

q4

Odstranı´me nedosazˇitelne´ stavy (do kteryćh neexistuje cesta z pocˇa´tecˇnı´ho stavu): = {q0 } = {q0 } ∪ {q1 , q3 } = {q0 , q1 , q3 } (ze stavu q0 vede prˇechod do q1 a q3 ) = {q0 , q1 , q3 } ∪ {q5 , q2 } = {q0 , q1 , q3 , q5 , q2 } = {q0 , q1 , q3 , q5 , q2 } = S2 (konec, v poslednı´m kroku zˇa´dny´ stav do mnozˇiny neprˇibyl) V mnozˇineˇ S3 nenı´ stav q4 , je tedy nedosazˇitelny´ z pocˇa´tecˇnı´ho stavu a mu˚zˇeme ho z automatu odstranit. V kazˇde´ z mnozˇin Si , ktere´ jsme postupneˇ vytvorˇili, najdeme vsˇechny stavy, ktere´ jsou z pocˇa´tecˇnı´ho stavu dosazˇitelne´ po nejvy´sˇe i krocıćh. Da´le zjistı´me, ze kteryćh stavu˚ nevede cesta do koncovyćh stavu˚. Budeme pracovat jizˇ s automatem po odstraneˇnı´ stavu q4 .

S0 S1 S2 S3

E0 E1 E2 E3

= F = {q1 , q5 } = {q1 , q5 } ∪ {q0 } = {q1 , q5 , q0 } (do stavu˚ z E0 vede prˇechod pouze ze stavu q0 ) = {q1 , q5 , q0 , q2 } = {q1 , q5 , q0 , q2 } = E2

V mnozˇineˇ E3 nenı´ stav q3 , to znamena´, zˇe z tohoto stavu neexistuje zˇa´dna´ cesta do koncove´ho a tedy kdyzˇ tento stav odstranı´me, neovlivnı´me vy´pocˇet zˇa´dne´ho slova, ktere´ automat rozpozna´va´. Odstranı´me tento stav a take´ vsˇechny prˇechody s nı´m prˇ´ımo souvisejıćı´. Po odstraneˇnı´ stavu˚ nepatrˇ´ıcıćh do mnozˇin Si a Ei dosta´va´me tento konecˇny´ automat:

→ q0 ← q1 q2 ← q5

a

b

c

q1 q1

q2

q5 q0

q5

a q0 c

a c q1 b q2

a q5

KAPITOLA 2


26

´ koly U 1. Podle zadańı´ na´sledujıćı´ho automatu vytvorˇte tabulku prˇechodu˚ a stavovy´ diagram. Potom odstranˇte nepotrˇebne´ stavy. Takto upraveny´ automat pak zu´plnˇte (prˇeved’te na tota´lnı´ automat).

C

A = ({A, B, C, D, E, F }, {0, 1, 2}, δ, A, {A, C}) s funkcı´ δ: δ(A, 0) = E δ(A, 1) = B δ(A, 2) = E

δ(B, 0) = C δ(B, 1) = D δ(B, 2) = E

δ(C, 0) = C δ(C, 1) = C δ(D, 2) = C

δ(E, 1) = E δ(E, 2) = E δ(F, 0) = C

δ(F, 1) = E δ(F, 2) = F

2. K na´sledujıćı´mu konecˇne´mu automatu vytvorˇte zby´vajıćı´ dveˇ reprezentace – δ-funkci a tabulku prˇechodu˚. Potom odstranˇte vsˇechny nepotrˇebne´ stavy.

a

b A a c b D

B a a C b a a F

b E a G

3. Podle na´sledujıćıćh konecˇnyćh automatu˚ urcˇenyćh tabulkami prˇechodu˚ sestrojte stavove´ diagramy a pak odstranˇte vsˇechny nepotrˇebne´ stavy.

↔A B C D ←E

a

b

c

A C C A B

A

B

B E C

B C

→ q0 ← q1 ← q2 q3 q4

a

b

q4 q4 q3

q1 q1 q4 q3

c q0 q2 q3

4. Zamyslete se nad teˇmito prˇ´ıpady: jak by vypadal jazyk upravene´ho automatu (bez nepotrˇebnyćh stavu˚), kdyby do mnozˇin Si nebyly zarˇazeny zˇa´dne´ koncove´ stavy? Jak by vypadal tento jazyk, kdyby do mnozˇin Ei nebyl zarˇazen pocˇa´tecˇnı´ stav?

2.6

Uza´veˇrove´ vlastnosti – regula´rnı´ operace

Trˇ´ıda jazyku˚ je mnozˇina vsˇech jazyku˚ s danou spolecˇnou vlastnostı´. Take´ regula´rnı´ jazyky tvorˇ´ı trˇ´ıdu – trˇ´ıda regula´rnıćh jazyku˚ je mnozˇina vsˇech jazyku˚, pro ktere´ lze sestrojit konecˇny´ automat.

P

KAPITOLA 2


27

Vı´me, zˇe na rˇeteˇzce lze pouzˇ´ıt operaci zrˇeteˇzenı´. Jazyk je mnozˇina rˇeteˇzcu˚, a tedy na jazyk mu˚zˇeme pouzˇ´ıt ru˚zne´ mnozˇinove´ operace (sjednocenı´, pru˚nik, doplneˇk – zrcadlenı´, substituci), a take´ operace odvozene´ z praće s rˇeteˇzci a znaky (signa´ly) – zrˇeteˇzenı´, da´le iteraci (operace „hveˇzdicˇka“) a dalsˇ´ı. Trˇ´ıda jazyku˚ je uzavrˇena vzhledem k neˇjake´ operaci, pokud po uplatneˇnı´ operace na jazyky z te´to trˇ´ıdy vzˇdy vznikne jazyk patrˇ´ıcı´ do stejne´ trˇ´ıdy. Postupneˇ si uka´zˇeme vsˇechny za´kladnı´ operace, a to na konecˇnyćh automatech. Pokud jde o bina´rnı´ operaci (uplatnˇuje se na dva jazyky), je obvykou podmıńkou disjunktnost pru˚niku mnozˇin stavu˚ automatu˚ (zˇa´dny´ stav existuje v obou automatech za´rovenˇ).

2.6.1

Sjednocenı´

V prˇ´ıpadeˇ sjednocenı´ vyuzˇijeme celou definici pu˚vodnıćh automatu˚. Prˇida´me novy´ stav a z tohoto stavu povedeme prˇechody do vsˇech stavu˚, do kteryćh vede prˇechod z pocˇa´tecˇnı´ho stavu. Novy´ stav na´m tedy simuluje pouzˇitı´ pocˇa´tecˇnıćh stavu˚ v pu˚vodnıćh automatech. Postup si mu˚zˇeme prˇedstavit trˇeba tak, zˇe vezmeme vsˇechny prˇechody, ktere´ vedou z pu˚vodnıćh pocˇa´tecˇnıćh stavu˚, a zkopı´rujeme (ne prˇeneseme, ty pu˚vodnı´ musejı´ zu˚stat) jejich zacˇa´tky (tj. u stavu˚, ze kteryćh vycha´zejı´) k nove´mu stavu. Pokud neˇktery´ z pu˚vodnıćh pocˇa´tecˇnıćh stavu˚ patrˇ´ı i do mnozˇiny koncovyćh stavu˚, pak take´ tuto vlastnost prˇida´me nove´mu pocˇa´tecˇnı´mu stavu. Oznacˇme • A1 = (Q1 , Σ1 , δ1 , q1 , F1 ) je prvnı´ automat,

P P

• A2 = (Q2 , Σ2 , δ2 , q2 , F2 ) je druhy´ automat, pak automat rozpozna´vajıćı´ jazyk, ktery´ je sjednocenı´m jazyku˚ obou automatu˚, je A = (Q1 ∪ Q2 ∪ {s0 }, Σ1 ∪ Σ2 , δ, s0 , F1 ∪ F2 ), platı´, zˇe s0 ∈ / Q1 ∪ Q2 , prˇechodova´ funkce: δ(s0 , x) =(δ1 (q1 , x) ∪ δ2 (q2 , x), x ∈ Σ1 ∪ Σ2 δ1 (r, x) ; r ∈ Q1 , x ∈ Σ1 , δ(r, x) = δ2 (r, x) ; r ∈ Q2 , x ∈ Σ2 To znamena´, zˇe prˇechodovou funkci prakticky prˇejmeme z pu˚vodnıćh automatu˚, zmeˇna bude jen na zacˇa´tku. Prˇı´klad 2.8 Uka´zˇeme si operaci sjednocenı´ na na´sledujıćıćh jazycıćh a automatech: L1 = {(ba)i (a ∪ bb) : i ≥ 0} L2 = {ai baaj ; i, j ≥ 0} Konecˇne´ automaty pro tyto jazyky jsou na´sledujıćı´: a q1 q0 ↔ q0 b b ← q1 a q2 q2

a

b

q1

q2

q0

q1

b A a

M

B

→A

a B

←C

C a

a

b

A C C

B

KAPITOLA 2


28

A1 = ({q0 , q1 , q2 }, {a, b}, δ1 , q0 , {q0 , q1 }) δ1 (q0 , a) = q1 δ1 (q0 , b) = q2 δ1 (q2 , a) = q0 δ1 (q2 , b) = q1

A2 = ({A, B, C}, {a, b}, δ2 , A, {C}) δ2 (A, a) = A δ2 (A, b) = B δ2 (B, a) = C δ2 (C, a) = C

Prˇida´me novy´ stav s0 a vsˇechny prˇechody z tohoto stavu nasmeˇrujeme a oznacˇ´ıme stejneˇ jako prˇechody z pocˇa´tecˇnıćh stavu˚ pu˚vodnıćh automatu˚. Postup je nejna´zorneˇjsˇ´ı na stavove´m diagramu, ale je jednoduchy´ take´ v tabulce prˇechodu˚ – stacˇ´ı obeˇ tabulky shrnout do jedne´ a prˇidat novy´ rˇa´dek, jehozˇ bunˇky budou sjednocenı´m buneˇk na rˇa´dcıćh pu˚vodnıćh pocˇa´tecˇnıćh stavu˚ a na prˇ´ıslusˇnyćh sloupcıćh. Protozˇe jeden z pu˚vodnıćh pocˇa´tecˇnıćh stavu˚ (q0 ) patrˇ´ı do mnozˇiny koncovyćh stavu˚, take´ novy´ pocˇa´tecˇnı´ stav s0 bude za´rovenˇ koncovy´m. a q1 q0 b b a a b q2 s0 a a a b b a C A B

a

↔ s0 ← q0 ← q1 q2 A B ←C

q1 , A q1

q0 A C C

b q2 , B q2 q1 B

A = ({s0 , q0 , q1 , q2 , A, B, C}, {a, b}, δ, s0 , {q0 , q1 , C}) δ(s0 , a) = δ1 (q0 , a) ∪ δ2 (A, a) = {q1 , A} δ(s0 , b) = δ1 (q0 , b) ∪ δ2 (A, b) = {q2 , B} δ(q0 , a) = {q1 } δ(q0 , b) = {q2 } δ(q2 , a) = {q0 }

δ(q2 , b) = {q1 } δ(A, a) = {A} δ(A, b) = {B} δ(B, a) = {C} δ(C, a) = {C}

Je zrˇejme´, zˇe L(A) = L(A1 ) ∪ L(A2 ). Pokud by zˇa´dny´ z pu˚vodnıćh pocˇa´tecˇnıćh stavu˚ nepatrˇil do mnozˇiny koncovyćh stavu˚, pak ani stav s0 nesmı´me zarˇadit do mnozˇiny koncovyćh stavu˚! Znamenalo by to, zˇe do vy´sledne´ho jazyka nema´ patrˇit pra´zdne´ slovo. ´ koly U 1. Pouzˇijte operaci sjednocenı´ na na´sledujıćı´ konecˇne´ automaty: 0 A 1

0 1 C B

0 1 1 E D

L C

KAPITOLA 2


29

2. Pouzˇijte operaci sjednocenı´ na na´sledujıćı´ konecˇne´ automaty (q3 za´rovenˇ koncovy´!):

→ q0 ← q1 ← q2

a

b

q0 , q2

q1 q2

q2

↔ q3 q4 q5 ← q6

a

b

q4

q6 q5

c

q3

3. Pro oba konecˇne´ automaty ze zadańı´ prˇedchozı´ho prˇ´ıkladu a take´ pro vy´sledny´ automat vytvorˇte zbyle´ dva typy reprezentacı´ – stavovy´ diagram a δ-funkci vcˇetneˇ plne´ specifikace automatu. 4. Zamyslete se nad tı´m, jak by vypadalo sjednocenı´ vıće nezˇ dvou konecˇnyćh automatu˚.

2.6.2

Zrˇeteˇzenı´

Zrˇeteˇzenı´ dvou jazyku˚ vytvorˇ´ıme tak, zˇe ve vy´sledne´m jazyce jsou vsˇechny mozˇne´ rˇeteˇzce, jejichzˇ prvnı´ cˇa´st je ktere´koliv slovo z prvnı´ho jazyka a druha´ cˇa´st zase ktere´koliv slovo z druhe´ho jazyka. Za´lezˇ´ı na porˇadı´, cˇa´sti slova nemu˚zˇeme prˇehodit, rˇ´ıdı´ se porˇadı´m zrˇeteˇzovanyćh jazyku˚. Prˇı´klad 2.9 Princip zrˇeteˇzenı´ jazyku˚ si uka´zˇeme na teˇchto konecˇnyćh jazycıćh: L1 = {ε, abc, ba} L2 = {ddb, dc} Zrˇeteˇzenı´m teˇchto dvou jazyku˚ zı´ska´me jazyk L = L1 · L2 : L = {ε · ddb, ε · dc, abc · ddb, abc · dc, ba · ddb, ba · dc} = {ddb, dc, abcccb, abcdc, baddb, badc} Prˇi zrˇeteˇzenı´ nenı´ trˇeba ve vy´sledne´m automatu vytva´rˇet novy´ stav. Opeˇt vyuzˇijeme vsˇechny stavy a prˇechody z pu˚vodnıćh automatu˚ a budeme prˇida´vat nove´ prˇechody, ktere´ je propojı´. Prˇi ukoncˇenı´ vy´pocˇtu prvnı´ cˇa´sti slova (tj. v prvnı´m pu˚vodnı´m automatu) je trˇeba „plynule“ nava´zat na vy´pocˇet druhe´ho pu˚vodnı´ho automatu. Proto noveˇ prˇida´vane´ prˇechody budou ve´st z koncovyćh stavu˚ prvnı´ho automatu, jejich cı´lovy´ stav (stav, do ktere´ho bude smeˇrˇovat sˇipka prˇechodu) a oznacˇenı´ prˇejmeme (zkopı´rujeme) od prˇechodu˚ z pocˇa´tecˇnı´ho stavu druhe´ho pu˚vodnı´ho automatu. Pocˇa´tecˇnı´m stavem vy´sledne´ho automatu bude samozrˇejmeˇ pocˇa´tecˇnı´ stav prvnı´ho pu˚vodnı´ho automatu. Do mnozˇiny koncovyćh stavu˚ zarˇadı´me • koncove´ stavy druhe´ho pu˚vodnı´ho automatu,

• pokud pocˇa´tecˇnı´ stav druhe´ho automatu byl za´rovenˇ koncovy´m (to znamena´, zˇe do druhe´ho jazyka patrˇilo slovo ε), pak do mnozˇiny koncovyćh stavu˚ vy´sledne´ho automatu zarˇadı´me take´ koncove´ stavy prvnı´ho pu˚vodnı´ho automatu.

P M

KAPITOLA 2


30

P

Oznacˇme • A1 = (Q1 , Σ1 , δ1 , q1 , F1 ) je prvnı´ automat,

• A2 = (Q2 , Σ2 , δ2 , q2 , F2 ) je druhy´ automat, zde je jizˇ du˚lezˇite´ jejich porˇadı´,

pak automat rozpozna´vajıćı´ jazyk, ktery´ je zrˇeteˇzenı´m jazyku˚ obou automatu˚, je A = (Q1 ∪ Q2 , Σ1 ∪ Σ2 , δ, q1 , F ), koncove´ stavy: • F = F2 , pokud ε ∈ / L(A2 )

• F = F1 ∪ F2 , pokud ε ∈ L(A2 )

(tj. jestlizˇe v jazyce druhe´ho automatu bylo pra´zdne´ slovo, tedy pocˇa´tecˇnı´ stav patrˇil do mnozˇiny koncovyćh stavu˚, znamena´ to, zˇe do vy´sledne´ho jazyka budou patrˇit i vsˇechna slova rozpozna´vana´ prvnı´m automatem – zrˇeteˇzena´ s ε, lze skoncˇit take´ ve stavech z F1 ) Prˇechodova´ funkce:    δ1 (r, x) ; r ∈ Q1 − F1 , x ∈ Σ1 , δ(r, x) = δ1 (r, x) ∪ δ2 (q2 , x) ; r ∈ F1 , x ∈ Σ1 ∪ Σ2 ,   δ2 (r, x) ; r ∈ Q2 , x ∈ Σ2 Znamena´ to, zˇe v koncovyćh stavech prvnı´ho pu˚vodnı´ho automatu budeme (kromeˇ existujıćıćh pu˚vodnıćh reakcı´) reagovat stejneˇ, jako v pocˇa´tecˇnı´m stavu druhe´ho pu˚vodnı´ho automatu (cozˇ je podle nasˇeho znacˇenı´ q2 ). Prˇı´klad 2.10 Zrˇeteˇzı´me jazyky teˇchto konecˇnyćh automatu˚: a A1 q1 q0 ↔ q0 b b ← q1 a q2 q2

a

b

q1

q2

q0

q1

A1 = ({q0 , q1 , q2 }, {a, b}, δ1 , q0 , {q0 , q1 }) δ1 (q0 , a) = q1 δ1 (q0 , b) = q2 δ1 (q2 , a) = q0 δ1 (q2 , b) = q1

b A a

B A2

→A

a B

←C

C a

M a

b

A C C

B

A2 = ({A, B, C}, {a, b}, δ2 , A, {C}) δ2 (A, a) = A δ2 (A, b) = B δ2 (B, a) = C δ2 (C, a) = C

V automatu A1 (prvnı´m) jsou dva koncove´ stavy. Z nich budou ve´st nove´ prˇechody ke stavu˚m automatu A2 – ke vsˇem stavu˚m, do kteryćh vede prˇechod z pocˇa´tecˇnı´ho stavu A. b a a q0 b

a q1 b b a q2

b A a

B

a

C a

→ q0 q1 q2 A B ←C

a

b

q1 , A A q0 A C C

q2 , B B q1 B

KAPITOLA 2


31

A = ({q0 , q1 , q2 , A, B, C}, {a, b}, δ, {C}) δ(q0 , a) = {q1 , A} δ(q0 , b) = {q2 , B} δ(q1 , a) = {A}

δ(q1 , b) = {B} δ(q2 , a) = {q0 } δ(q2 , b) = {q1 }

δ(A, a) = {A} δ(A, b) = {B} δ(B, a) = {C}

δ(C, a) = {C}

Platı´ L(A) = L(A1 ) · L(A2 ).

Prˇı´klad 2.11 Nynı´ pouzˇijeme stejne´ zadańı´ jako v prˇedchozı´m prˇ´ıkladu, jen obra´tı´me porˇadı´ zrˇeteˇzovanyćh automatu˚. Musı´me bra´t v u´vahu to, zˇe pocˇa´tecˇnı´ stav automatu, ktery´ je ted’ druhy´ v porˇadı´, je za´rovenˇ koncovy´m stavem, cozˇ bude mı´t vliv take´ na mnozˇinu koncovyćh stavu˚: b A a

B

a a

C a b

a q1 q0 b b a q2

→A B ←C q0 q1 q2

a

b

A C C, q1 q1

B

q0

q2 q2 q1

M

A0 = ({q0 , q1 , q2 , A, B, C}, {a, b}, δ, {C, q0 , q1 }) δ(A, a) = {A} δ(A, b) = {B} δ(B, a) = {C}

δ(C, a) = {C, q1 } δ(C, b) = {q2 } δ(q0 , a) = {q1 }

δ(q0 , b) = {q2 } δ(q2 , a) = {q0 } δ(q2 , b) = {q1 }

Platı´ L(A0 ) = L(A2 ) · L(A1 ).

´ koly U 1. Proved’te operaci zrˇeteˇzenı´ jazyku˚ na´sledujıćıćh konecˇnyćh automatu˚: 0 A 1

0 1 C B

0 1 1 E D

2. Proved’te operaci zrˇeteˇzenı´ jazyku˚ na´sledujıćıćh konecˇnyćh automatu˚ – nejdrˇ´ıv v porˇadı´ podle zadańı´ (L(A1 ) · L(A2 )) a potom v opacˇne´m porˇadı´ (L(A2 ) · L(A1 )). Sestrojte take´ stavove´ diagramy.

C

KAPITOLA 2 A1

→ q0 ← q1 ← q2

2.6.3

KONECˇNE´ AUTOMATY a

b

q0 , q2

q1 q2

32 A2

↔ q3 q4 q5 ← q6

q2

a

b

q4

q6 q5

c

q3

Iterace (Kleeneho uza´veˇr)

Prˇi iteraci zrˇeteˇzujeme jazyk sa´m se sebou, a to 0×, 1×, 2×, . . . , a pak vsˇechny vy´sledne´ jazyky po zrˇeteˇzenı´ sjednotı´me. Forma´lneˇ to mu˚zˇeme zapsat na´sledovneˇ: L∗ =

∞ [

P

Li

i=0

kde Li je i-na´sobne´ zrˇeteˇzenı´ jazyka L sama se sebou (naprˇ´ıklad pro i = 3 bylo L3 = L · L · L). Zrˇeteˇzenı´ jsme jizˇ probı´rali. Prˇı´klad 2.12 Princip iterace jazyka si uka´zˇeme na tomto konecˇne´m jazyce: L1 = {abc, ba, cd} Iteracı´ zı´ska´me jazyk L = L∗1 : L = { ε, ....................................................................... abc, ba, cd, . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . abcabc, abcba, abccd, baabc, baba, bacd, cdabc, cdba, cdcd, ................... abcabcabc, abcabcba, abcabccd, abcbaabc, abcbaba, abcbacd, . . .} .............

M 0× 1× 2× 3×, . . .

Vy´sledkem iterace je vzˇdy nekonecˇny´ jazyk obsahujıćı´ pra´zdne´ slovo ε, i kdyby pu˚vodnı´ jazyk L1 byl konecˇny´ a i kdyby pra´zdne´ slovo neobsahoval.

´ prava konecˇne´ho automatu prˇi iteraci spocˇ´ıva´ v teˇchto dvou krocıćh: U 1. vytvorˇ´ıme novy´ pocˇa´tecˇnı´ stav, prˇechody z neˇj vedoucı´ urcˇ´ıme stejne´ jako ty, ktere´ vedou z pu˚vodnı´ho pocˇa´tecˇnı´ho stavu, 2. vytvorˇ´ıme nove´ prˇechody umozˇnˇujıćı´ „na´vrat“ z koncovyćh stavu˚ na pocˇa´tek vy´pocˇtu (dalsˇ´ı slovo z jazyka), 3. novy´ pocˇa´tecˇnı´ stav zarˇadı´me do mnozˇiny koncovyćh stavu˚ (tı´m zarˇadı´me do jazyka slovo ε). Prvnı´ bod je nevyhnutelny´ prˇedevsˇ´ım tehdy, pokud v pu˚vodnı´m automatu vede neˇktery´ prˇechod do pocˇa´tecˇnı´ho stavu a za´rovenˇ tento stav nebyl v mnozˇineˇ koncovyćh stavu˚; je trˇeba zabrańit tomu, aby zarˇazenı´ pocˇa´tecˇnı´ho stavu do mnozˇiny koncovyćh stavu˚ meˇlo za na´sledek rozpozna´vańı´ takovyćh slov, ktera´ do jazyka spra´vneˇ patrˇit nemajı´.

L P

KAPITOLA 2


33

Oznacˇme A1 = (Q1 , Σ, δ1 , q0 , F1 ) pu˚vodnı´ automat, pak automat rozpozna´vajıćı´ jazyk, ktery´ je iteracı´ pu˚vodnı´ho jazyka, je A = (Q1 ∪ {s0 }, Σ, δ, s0 , F1 ∪ {s0 }), prˇechodova´ funkce: δ(r, x) =

P

   δ1 (r, x)

; r ∈ Q1 − F1 , x ∈ Σ, δ1 (r, x) ∪ δ1 (q0 , x) ; r ∈ F1 , x ∈ Σ,   δ1 (q0 , x) ; r = s0 , x ∈ Σ

Nove´ prˇechody povedou z pu˚vodnıćh koncovyćh stavu˚, a to do vsˇech stavu˚, do kteryćh vede prˇechod z pocˇa´tecˇnı´ho stavu. Princip je prakticky stejny´ jako u drˇ´ıve probı´ranyćh operacı´, kopı´rujeme pocˇa´tky prˇechodu˚ od pocˇa´tecˇnı´ho stavu se zachovańı´m jejich cı´le i oznacˇenı´ (signa´lu). Prˇı´klad 2.13 Vytvorˇ´ıme iteraci jazyka na´sledujıćı´ho automatu: A1 = ({A, B, C, D}, {0, 1, 2}, δ1 , A, {B, D}) 0 1 A 2 0 C

Postup:

2

→A ←B C ←D

1 B

D

M

0

1

2

A

B D

C B

δ1 (A, 0) = A δ1 (A, 1) = B δ1 (A, 2) = C δ1 (B, 1) = D δ1 (B, 2) = B δ1 (C, 0) = D

D

• Koncove´ stavy jsou dva. Z kazˇde´ho prˇida´me prˇechody do vsˇech stavu˚, do kteryćh smeˇrˇujı´ prˇechody z pocˇa´tecˇnı´ho stavu. • Vytvorˇ´ıme novy´ pocˇa´tecˇnı´ stav a prˇechody z neˇj vedoucı´ „zkopı´rujeme“ z pu˚vodnı´ho pocˇa´tecˇnı´ho stavu (tj. v nove´m pocˇa´tecˇnı´m stavu se automat bude chovat stejneˇ jako v pu˚vodnı´m). Tento krok je sice u veˇtsˇiny automatu˚ zbytecˇny´, ale u neˇkteryćh nutny´ – zamezı´me vzniku smycˇek prˇes pocˇa´tecˇnı´ stav generujıćıćh slova nepatrˇ´ıcı´ do jazyka (takove´ smycˇky jsme mohli vytvorˇit prˇedchozı´m krokem). • Potom (novy´) pocˇa´tecˇnı´ stav oznacˇ´ıme jako koncovy´, aby automat prˇijı´mal pra´zdne´ slovo ε. 1 0 s0 2

0 0 1 A 2 2 0 C 2

1, 2 1 1 B

D

0

0

↔ s0 A ←B C ←D

A A A D A

1

2

B B D, B

C C B, C

B

C

KAPITOLA 2


34

A = ({s0 , A, B, C, D}, {0, 1, 2}, δ, s0 , {s0 , B, D}) δ(s0 , 0) = A δ(s0 , 1) = B δ(s0 , 2) = C

δ(A, 0) = A δ(A, 1) = B δ(A, 2) = C

δ(B, 1) = D δ(B, 2) = B δ(C, 0) = D

δ(B, 0) = A δ(B, 1) = B δ(B, 2) = C

δ(D, 0) = A δ(D, 1) = B δ(D, 2) = C

Kdyby stav A v pu˚vodnı´m automatu patrˇil do mnozˇiny koncovyćh stavu˚, tak by samozrˇejmeˇ koncovy´m stavem zu˚stal.

´ koly U 1. Zkonstruujte konecˇny´ automat jazyka, ktery´ je iteracı´ jazyka na´sledujıćı´ho automatu: a q1 q0 b b a q2

A1

↔ q0 ← q1 q2

a

b

q1

q2

q0

q1

C

2. Zkonstruujte konecˇny´ automat jazyka, ktery´ je iteracı´ jazyka na´sledujıćı´ho automatu: 0 1 1 E D

→D ←E

0

1

D

E E

Pro vy´sledny´ automat take´ vytvorˇte trˇetı´ typ reprezentace – δ-funkci s plnou specifikacı´.

2.7 2.7.1

Uza´veˇrove´ vlastnosti – dalsˇı´ operace Pozitivnı´ iterace

Pozitivnı´ iterace je podobna´ operace jako prˇedchozı´, ale zatı´mco iterace znamena´ rˇeteˇzenı´ 0×, 1×, 2×, . . ., prˇi pozitivnı´ iteraci zacˇ´ına´me prˇi rˇeteˇzenı´ azˇ 1×, 2×, . . .. Matematicky´ za´pis obojı´ho: L∗ =

∞ [ i=0

Li

L+ =

∞ [

P

Li

i=1

Postup je stejny´ jako u iterace, ale pokud pocˇa´tecˇnı´ stav pu˚vodnı´ho automatu nepatrˇil do mnozˇiny koncovyćh stavu˚ (tj. slovo ε nepatrˇilo do jazyka), nebude koncovy´m stavem ani po u´praveˇ automatu. Oznacˇme A1 = (Q1 , Σ, δ1 , q0 , F1 ) pu˚vodnı´ automat, pak automat rozpozna´vajıćı´ jazyk, ktery´ je

P

KAPITOLA 2


35

pozitivnı´ iteracı´ pu˚vodnı´ho jazyka, je A = (Q1 ∪ {s0 }, Σ, δ, s0 , F ), kde F = F1 ∪ {s0 }, pokud q0 ∈ F1 , jinak F = F1 . Prˇechodova´ funkce:    δ1 (r, x) ; r ∈ Q1 − F1 , x ∈ Σ, δ(r, x) = δ1 (r, x) ∪ δ1 (q0 , x) ; r ∈ F1 , x ∈ Σ,   δ1 (q0 , x) ; r = s0 , x ∈ Σ Prˇı´klad 2.14 Vytvorˇ´ıme pozitivnı´ iteraci jazyka na´sledujıćı´ho automatu: A1 = ({A, B, C, D}, {0, 1, 2}, δ1 , A, {B, D}) 0 1 A 2 0 C

2

→A ←B C ←D

1 B

D

0

1

2

A

B D

C B

M δ1 (A, 0) = A δ1 (A, 1) = B δ1 (A, 2) = C δ1 (B, 1) = D δ1 (B, 2) = B δ1 (C, 0) = D

D

Prˇida´va´me pouze nove´ prˇechody, pocˇa´tecˇnı´ stav nebudeme zarˇazovat do mnozˇiny koncovyćh stavu˚, protozˇe v pu˚vodnı´m automatu take´ nebylo rozpozna´vańo slovo ε: 1 0 s0 2

0 0 1 A 2 2 0 C 2

1, 2 1 1 B

D

0

0

→ s0 A ←B C ←D

A A A D A

1

2

B B D, B

C C B, C

B

C

A = ({s0 , A, B, C, D}, {0, 1, 2}, δ, s0 , {B, D}) δ(s0 , 0) = A δ(s0 , 1) = B δ(s0 , 2) = C

δ(A, 0) = A δ(A, 1) = B δ(A, 2) = C

δ(B, 1) = D δ(B, 2) = B δ(C, 0) = D

δ(B, 0) = A δ(B, 1) = B δ(B, 2) = C

δ(D, 0) = A δ(D, 1) = B δ(D, 2) = C

Pokud pu˚vodnı´ jazyk L obsahuje slovo ε, pak platı´ L∗ = L+ , v opacˇne´m prˇ´ıpadeˇ se tyto jazyky nerovnajı´ a platı´ L∗ = L+ ∪ {ε}. ´ koly U 1. Zkonstruujte konecˇny´ automat jazyka, ktery´ je pozitivnı´ iteracı´ jazyka na´sledujıćı´ho automatu:

L C

KAPITOLA 2

KONECˇNE´ AUTOMATY a q1 q0 b b a q2

36

A1

↔ q0 ← q1 q2

a

b

q1

q2

q0

q1

2. Zkonstruujte konecˇny´ automat jazyka, ktery´ je pozitivnı´ iteracı´ jazyka na´sledujıćı´ho automatu: 0 1 0 1 1 E D

2.7.2

→D ←E

D

E E

Zrcadlovy´ obraz (reverze)

Reverze je prˇevraćenı´. Zrcadlovy´ obraz slova sestrojı´me tak, zˇe je zrcadloveˇ „prˇevra´tı´me“, tj. naprˇ´ıklad ze slova abcd zı´ska´me slovo (abcd)R = dcba. Zrcadlovy´ obraz jazyka je jazyk obsahujıćı´ vsˇechna slova pu˚vodnı´ho jazyka, ale prˇevraćena´. Operace zrcadlenı´ je sama k sobeˇ inverznı´ – kdyzˇ slovo (nebo jazyk) revertujeme dvakra´t, dosta´va´me pu˚vodnı´ slovo (jazyk). Zrcadlenı´ mu˚zˇeme zapsat takto: LR = {w ; wR ∈ L} Pokud budeme prˇi reverzi pracovat s konecˇny´m automatem, prˇedevsˇ´ım prˇevra´tı´me vsˇechny cesty, ktere´ v automatu existujı´ (tj. prˇevra´tı´me vsˇechny prˇechody) a zameˇnı´me pocˇa´tecˇnı´ a koncove´ stavy. Da´le musı´me vyrˇesˇit jeden proble´m – pocˇa´tecˇnı´ stav musı´ by´t vzˇdy jen jeden, ale koncovyćh stavu˚ mu˚zˇe by´t obecneˇ jaky´koliv pocˇet. Proto rozlisˇ´ıme dva prˇ´ıpady – pokud pu˚vodnı´ automat ma´ jen jediny´ koncovy´ stav, stacˇ´ı postup naznacˇeny´ v prˇedchozı´m odstavci. Jestlizˇe vsˇak ma´ vıće koncovyćh stavu˚, musı´me zajistit, aby po reverzi existoval jen jediny´ pocˇa´tecˇnı´ stav. Proto vytvorˇ´ıme novy´ stav, ktery´ v sobeˇ bude shrnovat vlastnosti pu˚vodnıćh koncovyćh stavu˚ (resp. novyćh „pocˇa´tecˇnıćh“ stavu˚) ty´kajıćı´ se prˇechodu˚, ktere´ z nich po reverzi vycha´zejı´. Pokud pocˇa´tecˇnı´ stav pu˚vodnı´ho automatu patrˇil do mnozˇiny koncovyćh stavu˚, bude koncovy´m stavem take´ pocˇa´tecˇnı´ stav po reverzi. Oznacˇme A1 = (Q1 , Σ, δ1 , q0 , F1 ) pu˚vodnı´ automat, pak automat rozpozna´vajıćı´ jazyk, ktery´ je reverzı´ pu˚vodnı´ho jazyka, je A = (Q1 ∪ {s0 }, Σ, δ, s0 , F ), mnozˇina koncovyćh stavu˚ je F = {q0 , s0 }, pokud q0 ∈ F1 , jinak F = {q0 } (za´lezˇ´ı na tom, zda do pu˚vodnı´ho jazyka patrˇilo ε). Prˇechodova´ funkce: (

δ(r, x) =

p ; δ1 (p, x) = r, x ∈ Σ, t ; r = s0 , δ1 (t, x) ∈ F1 , x ∈ Σ

Na prˇechodove´ funkci vidı´me, zˇe podle prvnı´ho rˇa´dku prˇedpisu se vsˇechny prˇechody obra´tı´ (tj. zameˇnı´ se zdroj a cı´l prˇechodu), podle druhe´ho rˇa´dku vytvorˇ´ıme prˇechody vedoucı´ z nove´ho (pocˇa´tecˇnı´ho) stavu s0 .

P

P


KAPITOLA 2

37

Prˇı´klad 2.15 Provedeme operaci zrcadlenı´ jazyka tohoto konecˇne´ho automatu: A1 = ({q0 , q1 , q2 , q3 }, {a, b, c}, δ1 , q0 , {q1 }) a q0 b

q1 c c b q2 a

→ q0 ← q1 q2 q3

q3

a

b

q1

q2

M

c

δ1 (q0 , a) = q1 δ1 (q0 , b) = q2 δ1 (q1 , c) = q1 δ1 (q2 , a) = q3 δ1 (q2 , c) = q1 δ1 (q3 , b) = q2

q1 q1

q3 q2

Obra´tı´me vsˇechny prˇechody. Protozˇe ma´me jen jediny´ koncovy´ stav, stacˇ´ı pak jen zameˇnit pocˇa´tecˇnı´ a koncovy´ stav (nebudeme vytva´rˇet novy´ stav s0 ). U tabulky se zameˇnˇujı´ oznacˇenı´ rˇa´dku˚ s obsahem buneˇk na tomto rˇa´dku. AR = ({q0 , q1 , q2 , q3 }, {a, b, c}, δ, q1 , {q0 }) q1 c

a q0 c b b q2 a

a

q3

← q0 → q1 q2 q3

b

c

q0

δ1 (q1 , a) = q0 δ1 (q2 , b) = q0 δ1 (q1 , c) = q1 δ1 (q3 , a) = q2 δ1 (q1 , c) = q2 δ1 (q2 , b) = q3

q1 , q2 q0 , q3

q2

Prˇı´klad 2.16 Podı´va´me se na slozˇiteˇjsˇ´ı prˇ´ıpad – konecˇny´ automat s vıće koncovy´mi stavy. Postup bude podobny´, ale navıć rˇesˇ´ıme nutnost existence jedine´ho pocˇa´tecˇnı´ho stavu. Je dań tento konecˇny´ automat: b A

b a C b

B

→A ←B C ←D

c D a

a

b

C

B

c D

A, D D

Jsou zde dva koncove´ stavy. Nejdrˇ´ıv prˇesmeˇrujeme vsˇechny prˇechody a oznacˇ´ıme novy´ koncovy´ stav, a azˇ v druhe´m kroku vytvorˇ´ıme novy´ pocˇa´tecˇnı´ stav podobneˇ, jak jsme pouzˇili naprˇ´ıklad u sjednocenı´ (tam sˇlo take´ o „simulaci“ – nahrazenı´ dvou pocˇa´tecˇnıćh stavu˚ jediny´m). b A

b a C b

B c D a

⇒

b A

b a C b

b c s0 B c a D a

b

→ s0 ←A B C D

a

b

c

D

A, C C A

B

C

B

A D

M

KAPITOLA 2


38

Poslednı´ prˇ´ıpad, na ktery´ se podı´va´me, je konecˇny´ automat s vıće koncovy´mi stavy, kde take´ pocˇa´tecˇnı´ stav patrˇ´ı do mnozˇiny koncovyćh stavu˚. Prˇı´klad 2.17 Pro operaci zrcadlenı´ je dań konecˇny´ automat A1 = ({q0 , q1 , q2 }, {a, b}, δ1 , q0 , {q0 , q1 }) a q1 q0 b b a q2

↔ q0 ← q1 q2

a

b

q1

q2

q0

q1

M

δ1 (q0 , a) = q1 δ1 (q0 , b) = q2 δ1 (q2 , a) = q0 δ1 (q2 , b) = q1

Narozdı´l od prˇedchozıćh prˇ´ıkladu˚ budou ve vy´sledne´m automatu dva koncove´ stavy. Stav q0 bude koncovy´, protozˇe v pu˚vodnı´m automatu je pocˇa´tecˇnı´m stavem, a stav s0 bude koncovy´, protozˇe do jazyka pu˚vodnı´ho automatu patrˇ´ı slovo ε, jehozˇ prˇevraćenı´m je opeˇt slovo ε pro jeho rozpoznańı´ musı´ by´t pocˇa´tecˇnı´ stav (tj. s0 ) v mnozˇineˇ koncovyćh stavu˚. AR = ({s0 , q0 , q1 , q2 }, {a, b}, δ, s0 , {q0 , s0 })

a

a q0 b

q1

b a q2 s0 a, b

↔ s0 ← q0 q1 q2

a

b

q0 , q2 q2 q0

q2

δ(s0 , a) = {q0 , q2 } δ(s0 , b) = {q2 } δ(q1 , a) = {q0 } δ(q2 , b) = {q0 } δ(q0 , a) = {q2 } δ(q1 , b) = {q2 }

q2 q0

´ koly U 1. Zkonstruujte konecˇny´ automat jazyka, ktery´ je reverzı´ (zrcadlovy´m obrazem) jazyka na´sledujıćı´ho automatu: 0 1 1 E D

→D ←E

0

1

D

E E

2. Vytvorˇte konecˇny´ automat jazyka, ktery´ je reverzı´ jazyka na´sledujıćı´ho automatu. Pro oba automaty (uvedeny´ i ten, ktery´ vytvorˇ´ıte) sestrojte tabulku prˇechodu˚. b a b q1 q0

C

KAPITOLA 2


39

3. Vytvorˇte konecˇny´ automat rozpozna´vajıćı´ jazyk L = {ε, tisk, tis, sı´to} tak, aby jednotliva´ slova jazyka byla rozpozna´vana´ koncovy´m stavem (tj. pro kazˇde´ slovo vlastnı´ koncovy´ stav). Potom proved’te reverzi tohoto automatu. 4. Vytvorˇte zrcadlovy´ obraz jazyka tohoto konecˇne´ho automatu (ma´ jediny´ koncovy´ stav, ktery´ je za´rovenˇ pocˇa´tecˇnı´m stavem): ↔ q0 q1 q2

2.7.3

a

b

q1

q2 q2 q0

q2

Pru˚nik

Kdyzˇ vytva´rˇ´ıme konecˇny´ automat pro pru˚nik dvou jazyku˚ pomocı´ automatu˚, ktere´ je rozpozna´vajı´, tak vlastneˇ simulujeme (paralelneˇ) cˇinnost obou teˇchto automatu˚. Po prˇecˇtenı´ kazˇde´ho signa´lu ze vstupu provedeme jeden krok v obou automatech za´rovenˇ. Ve vy´sledne´m automatu jsou proto stavy usporˇa´dany´mi dvojicemi stavu˚ z prvnı´ho a druhe´ho pu˚vodnı´ho automatu (za´lezˇ´ı na porˇadı´!). Oznacˇme • A1 = (Q1 , Σ1 , δ1 , q1 , F1 ) je prvnı´ automat, • A2 = (Q2 , Σ2 , δ2 , q2 , F2 ) je druhy´ automat,

P P

pak automat rozpozna´vajıćı´ jazyk, ktery´ je pru˚nikem jazyku˚ obou automatu˚, je AP = (Q1 × Q2 , Σ1 ∩ Σ2 , δ, [q1 , q2 ], F1 × F2 ), kde operace × je karte´zsky´m soucˇinem uvedenyćh mnozˇin. Prˇechodova´ funkce: δ([p, r], x) = [δ1 (p, x), δ2 (r, x)], kde p ∈ Q1 , r ∈ Q2 , x ∈ Σ2 , x ∈ Σ1 ∩ Σ2 Prˇı´klad 2.18 Sestrojı´me konecˇny´ automat rozpozna´vajıćı´ pru˚nik jazyku˚ na´sledujıćıćh dvou automatu˚: a b q0

b b q1

a b q2

q3

A1 = ({q0 , . . . , q3 }, {a, b}, δ1 , q0 , {q2 }) δ1 (q0 , a) = {q0 } δ1 (q0 , b) = {q1 } δ1 (q1 , b) = {q1 , q2 }

δ1 (q2 , a) = {q3 } δ1 (q3 , b) = {q2 }

a p0 a

b a p1 b b p3

p2

p4

A2 = ({p0 , . . . , p4 }, {a, b}, δ2 , p0 , {p4 }) δ2 (p0 , a) = {p1 , p3 } δ2 (p1 , a) = {p2 } δ2 (p1 , b) = {p1 }

δ2 (p2 , b) = {p0 } δ2 (p3 , b) = {p4 }

M

KAPITOLA 2


40

Nejdrˇ´ıv si vyznacˇ´ıme pru˚beˇh „simulace“. Nenı´ to nutne´ b a a b b (a u slozˇiteˇjsˇ´ıho automatu je to prakticky neproveditelne´), q2 q3 q1 q0 b ale na diagramu le´pe pochopı´me paralelnost obou zpracovańı´ te´hozˇ slova (cˇerveneˇ jsou spojeny stavy, ve kteryćh b jsou automaty ve stejne´m kroku zpracovańı´ slova) – obra´zek a a p2 p1 p0 vpravo. Naprˇ´ıklad pro slovo abbabab paralelneˇ procha´zı´me b dvojicemi stavu˚ [q0 , p0 ], pak [q0 , p1 ], [q1 , p1 ], [q2 , p1 ], [q3 , p2 ], a [q2 , p0 ], da´le [q3 , p3 ] a [q2 , p4 ]. b p4 p3 Protozˇe by bylo hodneˇ na´rocˇne´ (a take´ nedeterministicke´ a teˇzˇko naprogramovatelne´) takto vyhleda´vat vsˇechny dvojice stavu˚, ve kteryćh se nacha´zı´ vy´pocˇet v obou automatech ve stejne´m kroku, pouzˇijeme jinou (trochu „otrockou“) metodu: • jako mnozˇinu stavu˚ pouzˇijeme mnozˇinu vsˇech usporˇa´danyćh dvojic, kde prvnı´ prvek je stav prvnı´ho automatu a druhy´ prvek je stav druhe´ho automatu, • vytvorˇ´ıme δ-funkci nebo tabulku prˇechodu˚, ve ktere´ zachytı´me spolecˇne´ prˇechody na stejny´ signa´l v obou automatech, • odstranı´me nepotrˇebne´ stavy. Pocˇa´tecˇnı´m stavem bude usporˇa´dana´ dvojice obsahujıćı´ pocˇa´tecˇnı´ stavy obou pu˚vodnıćh automatu˚, koncove´ stavy budou vsˇechny usporˇa´dane´ dvojice, ve kteryćh jsou oba pu˚vodnı´ stavy koncovy´mi. Jednodusˇsˇ´ı je vyuzˇitı´ tabulky prˇechodu˚. Podle tabulek pu˚vodnıćh automatu˚ vytvorˇ´ıme tabulku pro vy´sledny´ automat (kombinace rˇa´dku˚ ve stejne´m sloupci).

→ q0 q1 ← q2 q3

a

b

q0

q1 q1 , q2

a → p0 p1 p2 p3 ← p4

q3 q2

p1 , p3 p2

b p1 p0 p4

Tabulka prˇechodu˚ vy´sledne´ho konecˇne´ho automatu ma´ 4 · 5 = 20 rˇa´dku˚: a → [q0 , p0 ] [q0 , p1 ] [q0 , p2 ] [q0 , p3 ] [q0 , p4 ] [q1 , p0 ] [q1 , p1 ] [q1 , p2 ] [q1 , p3 ] [q1 , p4 ]

[q0 , p1 ], [q0 , p3 ] [q0 , p2 ]

b [q1 , p1 ] [q1 , p0 ] [q1 , p4 ]

[q1 , p1 ], [q2 , p1 ] [q1 , p0 ], [q2 , p0 ] [q1 , p4 ], [q2 , p4 ]

(pokracˇovańı´)

[q2 , p0 ] [q2 , p1 ] [q2 , p2 ] [q2 , p3 ] ← [q2 , p4 ] [q3 , p0 ] [q3 , p1 ] [q3 , p2 ] [q3 , p3 ] [q3 , p4 ]

a

b

[q3 , p1 ], [q3 , p3 ] [q3 , p2 ]

[q2 , p1 ] [q2 , p0 ] [q2 , p4 ]

KAPITOLA 2


41

Nynı´ odstranı´me nepotrˇebne´ (tj. nedosazˇitelne´ a nadbytecˇne´) stavy tak, jak jsme se ucˇili v prˇedchozıćh kapitolaćh, obsah mnozˇin je pru˚beˇzˇneˇ trˇ´ıdeˇn pro usnadneˇnı´ porovna´vańı´. S0 = {[q0 , p0 ]} S1 = {[q0 , p0 ], [q0 , p1 ], [q0 , p3 ]} S2 = {[q0 , p0 ], [q0 , p1 ], [q0 , p3 ], [q0 , p2 ], [q1 , p1 ], [q1 , p4 ]} S3 = {[q0 , p0 ], [q0 , p1 ], [q0 , p2 ], [q0 , p3 ], [q1 , p1 ], [q1 , p4 ], [q1 , p0 ], [q2 , p1 ]} S4 = {[q0 , p0 ], [q0 , p1 ], [q0 , p2 ], [q0 , p3 ], [q1 , p0 ], [q1 , p1 ], [q1 , p4 ], [q2 , p1 ], [q3 , p2 ]} S5 = {[q0 , p0 ], [q0 , p1 ], [q0 , p2 ], [q0 , p3 ], [q1 , p0 ], [q1 , p1 ], [q1 , p4 ], [q2 , p1 ], [q3 , p2 ], [q2 , p0 ]} S6 = {[q0 , p0 ], [q0 , p1 ], [q0 , p2 ], [q0 , p3 ], [q1 , p0 ], [q1 , p1 ], [q1 , p4 ], [q2 , p0 ], [q2 , p1 ], [q3 , p2 ], [q3 , p1 ], [q3 , p3 ]} S7 = {[q0 , p0 ], [q0 , p1 ], [q0 , p2 ], [q0 , p3 ], [q1 , p0 ], [q1 , p1 ], [q1 , p4 ], [q2 , p0 ], [q2 , p1 ], [q3 , p1 ], [q3 , p2 ], [q3 , p3 ], [q2 , p4 ]} S8 = {[q0 , p0 ], [q0 , p1 ], [q0 , p2 ], [q0 , p3 ], [q1 , p0 ], [q1 , p1 ], [q1 , p4 ], [q2 , p0 ], [q2 , p1 ], [q2 , p4 ], [q3 , p1 ], [q3 , p2 ], [q3 , p3 ]} = S7 Odstranili jsme stavy [q0 , p4 ], [q1 , p2 ], [q1 , p3 ], [q2 , p2 ], [q2 , p3 ], [q3 , p0 ], [q3 , p4 ], ktere´ jsou nedosazˇitelne´ z pocˇa´tecˇnı´ho stavu. Da´le pracujeme s touto tabulkou prˇechodu˚: a → [q0 , p0 ] [q0 , p1 ] [q0 , p2 ] [q0 , p3 ] [q1 , p0 ] [q1 , p1 ] [q1 , p4 ] [q2 , p0 ] [q2 , p1 ] ← [q2 , p4 ] [q3 , p1 ] [q3 , p2 ] [q3 , p3 ] E0 E1 E2 E3 E4 E5 E6 E7 E8

[q0 , p1 ], [q0 , p3 ] [q0 , p2 ]

b [q1 , p1 ] [q1 , p0 ] [q1 , p4 ] [q1 , p1 ], [q2 , p1 ]

[q3 , p1 ], [q3 , p3 ] [q3 , p2 ] [q2 , p1 ] [q2 , p0 ] [q2 , p4 ]

Odstranı´me nadbytecˇne´ symboly (ze kteryćh neexistuje cesta do koncove´ho stavu): = {[q2 , p4 ]} = {[q2 , p4 ], [q3 , p3 ]} = {[q2 , p4 ], [q3 , p3 ], [q2 , p0 ]} = {[q2 , p0 ], [q2 , p4 ], [q3 , p3 ], [q3 , p2 ]} = {[q2 , p0 ], [q2 , p1 ], [q2 , p4 ], [q3 , p2 ], [q3 , p3 ]} = {[q2 , p0 ], [q2 , p1 ], [q2 , p4 ], [q3 , p2 ], [q3 , p3 ], [q1 , p1 ], [q3 , p1 ]} = {[q1 , p1 ], [q2 , p0 ], [q2 , p1 ], [q2 , p4 ], [q3 , p1 ], [q3 , p2 ], [q3 , p3 ], [q0 , p1 ]} = {[q0 , p1 ], [q1 , p1 ], [q2 , p0 ], [q2 , p1 ], [q2 , p4 ], [q3 , p1 ], [q3 , p2 ], [q3 , p3 ], [q0 , p0 ]} = {[q0 , p0 ], [q0 , p1 ], [q1 , p1 ], [q2 , p0 ], [q2 , p1 ], [q2 , p4 ], [q3 , p1 ], [q3 , p2 ], [q3 , p3 ]} = E7

Po odstraneˇnı´ stavu˚ [q0 , p2 ], [q0 , p3 ], [q1 , p0 ], [q1 , p4 ] dosta´va´me tuto tabulku prˇechodu˚ (s pu˚vodnı´m oznacˇenı´m stavu˚ a po prˇeznacˇenı´ na pı´smena):

KAPITOLA 2

KONECˇNE´ AUTOMATY a

→ [q0 , p0 ] [q0 , p1 ] [q1 , p1 ] [q2 , p0 ] [q2 , p1 ] ← [q2 , p4 ] [q3 , p1 ] [q3 , p2 ] [q3 , p3 ]

42 b

a →A B C D E ←F G H K

[q0 , p1 ] [q1 , p1 ] [q1 , p1 ], [q2 , p1 ] [q3 , p1 ], [q3 , p3 ] [q3 , p2 ] [q2 , p1 ] [q2 , p0 ] [q2 , p4 ]

Stavovy´ diagram (stavy jsou prˇeznacˇene´): a A

b B

b C b

a E

b a G

H

b a D

b

B C C, E G, K H E D F

b K F

´ koly U 1. Vytvorˇte deterministicke´ konecˇne´ automaty pro jazyky L1 = {if, then, else} a L2 = {if, iff, elif}, v kazˇde´m z automatu˚ stacˇ´ı jediny´ koncovy´ stav pro vsˇechna slova dane´ho jazyka. Potom pomocı´ automatu˚ vytvorˇte pru˚nik teˇchto jazyku˚.

C

2. Sestrojte konecˇny´ automat, ktery´ je pru˚nikem jazyku˚ na´sledujıćıćh automatu˚ (pracujte s tabulkami prˇechodu˚). Odstranˇte vsˇechny nedosazˇitelne´ a nadbytecˇne´ stavy a sestrojte stavovy´ diagram. 0 1 0 1 →A ←B C D

B C

A D

B

→E F ←H

F H

F H H

Pro kontrolu: po odstraneˇnı´ nepotrˇebnyćh stavu˚ by meˇl automat mı´t osm stavu˚, z toho jeden koncovy´, jeden cyklus prˇes jeden stav a jeden cyklus prˇes trˇi stavy.

2.7.4

Homomorfismus

Homomorfismus je takove´ zobrazenı´, ktere´ • zachova´va´ neutra´lnı´ prvek (tj. u rˇeteˇzcu˚ pra´zdny´ rˇeteˇzec ε zobrazı´ opeˇt na ε)

• zachova´va´ zobrazenı´ operace, pro kterou je definovań (u rˇeteˇzcu˚ jde o zrˇeteˇzenı´, tj. h(a · b) = h(a) · h(b))

• vy´sledkem zobrazenı´ prvku (signa´lu, znaku) je vzˇdy rˇeteˇzec (u substituce, cozˇ je zobecneˇnı´ homomorfismu, je vy´sledkem zobrazenı´ mnozˇina rˇeteˇzcu˚).

KAPITOLA 2


43

Kdyzˇ konstruujeme konecˇny´ automat homomorfismu pro neˇktery´ jazyk, vyuzˇ´ıva´me plneˇ zpu˚sobu definice dane´ho homomorfismu – pokud je v prˇedpisu tohoto zobrazenı´ naprˇ´ıklad h(a) = xyz, tj. znak a ma´ by´t zobrazen na rˇeteˇzec xyz, vezmeme postupneˇ vsˇechny prˇechody oznacˇene´ znakem a a nahradı´me je cestami rozpozna´vajıćı´mi slovo xyz. Kazˇda´ z teˇch cest musı´ by´t samozrˇejmeˇ samostatna´, vzˇdy jeden konkre´tnı´ prˇechod oznacˇeny´ signa´lem a nahradı´me jednou samostatnou cestou pro xyz. Prˇı´klad 2.19 Je dań automat A rozpozna´vajıćı´ jazyk L(A) = {ε} ∪ {abi acj ; i, j ≥ 0}. Sestrojı´me konecˇny´ automat Ah rozpozna´vajıćı´ jazyk vznikly´ uplatneˇnı´m homomorfismu h na jazyk automatu A. A

↔ q0 q1 ← q2

a

b

q1 q2

q1

c

Homomorfismus: h(a) = df, h(b) = f f d, h(c) = d

q2

Po u´praveˇ vypada´ konecˇny´ automat na´sledovneˇ: Ah

↔ q0 q1 ← q2 q3 q4 q5 q6

d

f

q5 q6 q2

q3 q4

Pu˚vodnı´ abeceda: Σ1 = {a, b, c} Nova´ abeceda: Σ2 = {d, f }

a q0

b a q1

q1 q2

c

q2

f q4 q3 f d d q0 q2 q1 d f d f q5

q1

M

q6

Po u´praveˇ dosta´va´me automat rozpozna´vajıćı´ jazyk {ε} ∪ {df (ff d)i df dj ; i, j ≥ 0}. ´ koly U Je dań konecˇny´ automat A s jazykem L = L(A) a homomorfismy h1 a h2 . h1 (a) = 01 h1 (b) = 110 h1 (c) = 1 h2 (a) = dd h2 (b) = g h3 (c) = dg

→ q0 ← q1 q2 q3

a

b

q1

q2

c q1 q1

q3 q2

a q0 b

q1 c c b q2 a

C q3

Zjisteˇte jazyky h1 (L) a h2 (L) a vytvorˇte take´ konecˇne´ automaty pro tyto jazyky (u´pravou automatu A). Jazyk automatu A je L(A) = {aci ; i ≥ 0} ∪ {b(ab)i ccj ; i, j ≥ 0}. Da´le pro vy´sledne´ automaty sestrojte jejich δ-funkci vcˇetneˇ plne´ specifikace, nezapomenˇte na zmeˇnu abecedy.

KAPITOLA 2

2.8


44

Sestrojenı´ konecˇne´ho automatu podle regula´rnı´ho vy´razu

Prˇi sestrojenı´ konecˇne´ho automatu podle zadane´ho regula´rnı´ho vy´razu vyuzˇ´ıva´me vztahu mezi prvky regula´rnı´ho vy´razu (+, ·, ∗ ) a operacemi nad mnozˇinami rˇeteˇzcu˚ ∪, ·, ∗ ). V prˇedchozıćh prˇ´ıkladech jsme se naucˇili pracovat s regula´rnı´mi operacemi (cozˇ, jak vı´me, jsou sjednocenı´, zrˇeteˇzenı´ a iterace) a tyto postupy pouzˇijeme take´ zde. Prˇı´klad 2.20 Sestrojı´me konecˇny´ automat pro regula´rnı´ vy´raz a∗ b + (b∗ a + bbc)∗ . REG1 = a

a 0

REG2 = b

b 2

1

REG3 = (REG1 )∗ = a∗

a b 1

REG5 = ((REG2 )∗ · REG1 ) = b∗ a

3

4

REG6 = bbc

b 6

5

b 7

c 9 8

b a 5 3

REG7 = (REG5 + REG6 ) = b∗ a + bbc

b a 10 b b @ @6 @

REG8 = (REG7 )∗ = (b∗ a + bbc)∗

REG4 = (REG3 · REG2 ) = a∗ b

a a 1 0

b a 3

M

b 7

b b a a 5 3 b b a b b 7

c 9 8

10

b a c 9 8 b


KAPITOLA 2

45

Vy´sledny´ automat: REG9 = (REG4 + REG8 ) = a∗ b + (b∗ a + bbc)∗ a b 4 1

a b 11 b b

a

b b a a 5 3 b b a @ @ 10 @ b b a b c 9 7 8 b

→ 11 1 3 ←4 ←5 7 8 ←9

a

b

1, 5 1 5

3, 4, 7 4 3

5

3, 7 8

c

9 5

3, 7

Stav 10 je nedosazˇitelny´ z pocˇa´tecˇnı´ho stavu, proto mu˚zˇe by´t odstraneˇn (v tabulce vpravo se jizˇ nenacha´zı´).

´ koly U Sestrojte konecˇne´ automaty podle teˇchto regula´rnıćh vy´razu˚: • (a +

b∗ )

·

b∗

• a · (b + (ab)∗ ) + b

• (01 + 10)∗ 10∗

• (abc)∗ · a · (ba + c)

C

Kapitola

3

Regula´rnı´ gramatiky 3.1

Vytva´rˇı´me regula´rnı´ gramatiku

Nejdrˇ´ıv si ujasnı´me, co to vlastneˇ je (regula´rnı´) gramatika. Obecneˇ a neforma´lneˇ mu˚zˇeme rˇ´ıci, zˇe gramatika je konstrukce, ktera´ popisuje strukturu dane´ho ˇ ´ıka´ na´m, co ma´ by´t drˇ´ıv, co pozdeˇji, co za cˇ´ım ma´ jazyka a jednotlivyćh slov tohoto jazyka. R na´sledovat, prˇ´ıpadneˇ jaky´m zpu˚sobem ma´ by´t co v cˇem vnorˇeno, za´lezˇ´ı na slozˇitosti samotne´ gramatiky. Cˇ´ım je slozˇiteˇjsˇ´ı jazyk, ktery´ ma´ gramatika popisovat, tı´m slozˇiteˇjsˇ´ı bude samozrˇejmeˇ i samotna´ gramatika. Podle definice je regula´rnı´ gramatika usporˇa´dana´ cˇtverˇice G = (N, T, P, S), kde jednotlive´ prvky te´to posloupnosti (opravdu posloupnosti, za´lezˇ´ı na porˇadı´) znamenajı´: • N je konecˇna´ nepra´zdna´ mnozˇina netermina´lnıćh symbolu˚, pro na´s prˇedstavuje obdobu promeˇnnyćh, • T je konecˇna´ nepra´zdna´ mnozˇina termina´lnıćh symbolu˚, pro na´s je to vlastneˇ abeceda, z jejıćhzˇ prvku˚ (znaku˚) jsou tvorˇena slova jazyka generovane´ho nasˇ´ı gramatikou, • P je konecˇna´ nepra´zdna´ mnozˇina pravidel, jejichzˇ formu probereme da´le,

• S ∈ N je startovacı´ symbol gramatiky (je to jeden z netermina´lnıćh symbolu˚, tak je jasne´, procˇ je ta mnozˇina nepra´zdna´). Vsˇimneˇte si slov „konecˇna´“ a „nepra´zdna´“, ktera´ se v definici cˇasto vyskytujı´. Tato slova jsou velmi du˚lezˇita´ a bez nich by definice byla neu´plna´. Pravidla v mnozˇineˇ P mohou by´t v jednom z teˇchto tvaru˚: A → aB A → a

(3.1) (3.2)

kde A, b ∈ N (jsou to netermina´ly) a a ∈ T (termina´l). Zˇa´dny´ jiny´ tvar pravidel nenı´ prˇ´ıpustny´, uzˇ by se nejednalo o regula´rnı´ gramatiku. Da´le je prˇ´ıpustne´ pravidlo S → ε, ale jen tehdy, kdyzˇ je S startovacı´ symbol gramatiky a nevyskytuje se na prave´ straneˇ zˇa´dne´ho pravidla. Je zrˇejme´, zˇe toto pravidlo bude pouze v takove´ gramatice, ktera´ generuje jazyk obsahujıćı´ pra´zdne´ slovo. 46

P

KAPITOLA 3

REGULA´RNI´ GRAMATIKY

47

Prˇı´klad 3.1 Vytvorˇ´ıme regula´rnı´ gramatiku, ktera´ generuje tento konecˇny´ jazyk: L = {vlak, drak, vlek} Postupujeme vzˇdy zleva doprava (tak jak cˇteme beˇzˇny´ text), budeme generovat jedno pı´smeno za druhy´m. Musı´me se drzˇet tvaru pravidel podle prˇedpisu˚ 3.1 a 3.2. Epsilonove´ pravidlo nepotrˇebujeme, protozˇe jazyk neobsahuje pra´zdne´ slovo. Nejdrˇ´ıv se veˇnujme prvnı´mu slovu: S → vA A → lB B → aC C→k Druhe´ slovo (musı´me zacˇ´ınat zase startovacı´m symbolem, ten je na zacˇa´tku generovańı´ kazˇde´ho slova gramatiky): S → dD D → rE E → aF F →k Trˇetı´ slovo: S → vG G → lH H → eK K→k

M

Cela´ gramatika: G = ({S, A, B, C, D, E, F, G, H, K}, {v, l, a, k, d, r, e}, P, S), kde P obsahuje tato pravidla: S → vA | dD | vG A → lB D → rE G → lH B → aC E → aF H → eK C→k F →k K→k

Vsˇechna pravidla prˇepisujıćı´ symbol S jsme shrnuli na jediny´ rˇa´dek, oddeˇlili jsme je svislicı´ |. Nejde o lomı´tko ani zpeˇtne´ lomı´tko, je to svisla´ cˇa´ra (na kla´vesnici ji obvykle najdeme vpravo nad zpeˇtny´m lomı´tkem na anglicke´ kla´vesnici). Tento symbol se v logice pouzˇ´ıva´ ve smyslu „nebo“, tenty´zˇ vy´znam ma´ i zde – symbol S mu˚zˇeme prˇepsat podle prvnı´ho nebo druhe´ho nebo trˇetı´ho pravidla. Jesˇteˇ si oveˇrˇ´ıme, zda v gramatice lze vygenerovat vsˇechna trˇi slova: S ⇒ vA ⇒ vlB ⇒ vlaC ⇒ vlak S ⇒ dD ⇒ drE ⇒ draF ⇒ drak S ⇒ vG ⇒ vlH ⇒ vleK ⇒ vlek Vsˇimneˇte si – jednoduchou sˇipku pouzˇ´ıva´me u pravidel, kdezˇto v odvozenı´ slov pouzˇ´ıva´me dvojitou sˇipku. Toto pravidlo budeme bezvy´hradneˇ dodrzˇovat, v kazˇde´m z teˇchto prˇ´ıpadu˚ jde o neˇco jine´ho. Prˇı´klad 3.2 Gramatika v prˇedchozı´m prˇ´ıkladu byla zbytecˇneˇ slozˇita´. Pokusı´me se ji zjednodusˇit tak, aby generovala i nada´le tenty´zˇ jazyk, ale aby obsahovala mensˇ´ı pocˇet pravidel. Dveˇ ze slov jazyka stejneˇ zacˇ´ınajı´. Proto bychom mohli stejneˇ zacˇ´ınat i prˇi jejich generovańı´. G0 = ({S, A, B, C, D, E, F, K}, {v, l, a, k, d, r, e}, P 0 , S), kde P 0 obsahuje tato pravidla: S → vA | dD A → lB D → rE K→k B → aC | eK E → aF C→k F →k

L M

KAPITOLA 3


48

Slovo „vlek“ odvodı´me takto: S ⇒ vA ⇒ vlB ⇒ vleK ⇒ vlek

Dala by se mnozˇina pravidel jesˇteˇ vıć zredukovat? Trˇeba takto: G00 = ({S, A, B, C, D, E}, {v, l, a, k, d, r, e}, P 00 , S), kde P 00 obsahuje tato pravidla: S → vA | dD A → lB D → rE C→k B → aC | eC E → aC Oveˇrˇ´ıme, zda se na´m nezmeˇnil generovany´ jazyk: S ⇒ vA ⇒ vlB ⇒ vlaC ⇒ vlak S ⇒ dD ⇒ drE ⇒ draC ⇒ drak S ⇒ vA ⇒ vlB ⇒ vleC ⇒ vlek

Je zrˇejme´, zˇe v gramatice lze vygenerovat opravdu jen tato trˇi slova, zˇa´dne´ dalsˇ´ı.

Vzˇdy bychom se meˇli prˇesveˇdcˇit, jak gramatika „funguje“, vyzkousˇet vygenerovat pa´r typickyćh slov jazyka (alesponˇ neˇkolik nejkratsˇ´ıch). Nejde jen o to, aby gramatika generovala vsˇechna slova prˇ´ıslusˇne´ho jazyka, ale i o to, aby gramatika negenerovala slova do jazyka nepatrˇ´ıcı´. Prˇı´klad 3.3 Sestrojı´me regula´rnı´ gramatiku generujıćı´ jazyk L = ab∗ + cd∗ . Slova jazyka zacˇ´ınajı´ bud’ pı´smenem a nebo pı´smenem c. Tyto dveˇ „kategorie“ oddeˇlı´me hned v pravidlech prˇepisujıćıćh startovacı´ symbol. S → aA | cB Ted’ prˇedevsˇ´ım musı´me da´t pozor, aby se na´m pı´smena ve slovech „nepomıćhala“ – za pı´smenem a mohou na´sledovat jen pı´smena b (jaky´koliv pocˇet) a za pı´smenem c mohou na´sledovat jen pı´smena d (taky jaky´koliv pocˇet). A → bA | b B → dB | d Ale jesˇteˇ jsme neskoncˇili. Do jazyka generovane´ho touto gramatikou totizˇ patrˇ´ı i slova o de´lce jedna: S→a|c

L M

Cela´ gramatika: G = ({S, A, B}, {a, b, c, d}, P, S) S → aA | a | cB | c A → bA | b B → cB | c

Otestujeme gramatiku vygenerovańı´m neˇkolika slov: S ⇒ aA ⇒ abA ⇒ abbA ⇒ abbb S⇒a S ⇒ cB ⇒ cb Pravidlo A → bA je rekurzvnı´, protozˇe se typicky pouzˇ´ıva´ v cyklu (je to obdoba cyklu v automatu, ale cyklus probı´ha´ mezi netermina´ly, ne mezi stavy). Kazˇda´ rekurze musı´ nutneˇ skoncˇit, k ukoncˇenı´ rekurze u na´s slouzˇ´ı pravidlo A → b. Tato rekurze je prˇ´ıma´ (prˇes jediny´ netermina´l), ale mu˚zˇe by´t i neprˇ´ıma´, jak uvidı´me na na´sledujıćı´m prˇ´ıkladu.

P

KAPITOLA 3


49

Prˇı´klad 3.4 Vytvorˇ´ıme regula´rnı´ gramatiku generujıćı´ jazyk L = (ab)∗ Vidı´me, zˇe do jazyka patrˇ´ı i pra´zdne´ slovo. Proto pouzˇijeme pravidlo S→ε Jazyk L je nekonecˇny´, proto zde urcˇiteˇ bude rekurze. Ale ne prˇ´ıma´, budeme potrˇebovat jesˇteˇ dalsˇ´ı netermina´l. Musı´me strˇ´ıdaveˇ generovat pı´smena a a b: A → aB B → bA Kazˇda´ rekurze se neˇkdy musı´ zastavit: B→b Jesˇteˇ tento cyklus napojı´me na startovacı´ symbol: S → aB Cela´ gramatika: G = ({S, A, B}, {a, b}, P, S), mnozˇina P : S → aB | ε A → aB B → bA | b Oveˇrˇ´ıme, jaka´ slova jsou gramatikou generovańa: S⇒ε S ⇒ aB ⇒ ab S ⇒ aB ⇒ abA ⇒ abaB ⇒ ababA ⇒ ababaB ⇒ ababab, atd.

M

Mohlo by se zda´t, zˇe bychom mohli gramatiku sestavit takto: = ({S, B}, {a, b}, P 0 , S), mnozˇina P 0 : S → aB | ε B → bS | b Sice bychom meˇli o dveˇ pravidla meńeˇ, ale pozor – prˇi pouzˇitı´ ε-pravidla se startovacı´ symbol nesmı´ vyskytovat na prave´ straneˇ zˇa´dne´ho pravidla, tato gramatika jizˇ nenı´ regula´rnı´! G0

Je trˇeba si uveˇdomit, zˇe gramatika generuje slova jazyka, kdezˇto automat dostane slovo na svu˚j vstup a oveˇrˇuje, zda toto slovo patrˇ´ı do jazyka, ktery´ rozpozna´va´. Prˇesto je mezi gramatikami a automaty velmi u´zky´ vztah – pro dany´ jazyk mu˚zˇeme sestrojit gramatiku, ktera´ ho generuje (tj. popisuje strukturu vsˇech slov patrˇ´ıcıćh do jazyka) a taky automat, ktery´ jeho slova rozpozna´va´ (tj. doka´zˇe urcˇit, zda dane´ slovo patrˇ´ı cˇi nepatrˇ´ı do dane´ho jazyka). V prˇ´ıpadeˇ regula´rnıćh gramatik a konecˇnyćh automatu˚ je celkem jednoduche´ prova´deˇt prˇevody mezi nimi, tedy podle gramatiky sestrojit ekvivalentnı´ automat a podle automatu sestrojit ekvivalentnı´ gramatiku. ´ koly U Sestrojte regula´rnı´ gramatiky generujıćı´ tyto jazyky: • L1 = {0100, 1011, 1110}

• L2 = {ε, 0100, 1011, 1110} • L3 = a∗

L C

KAPITOLA 3


50

• L4 = (abc)∗

• L5 = {am bn ; m ≥ 1, n ≥ 0} • L6 = (ab)∗ + ba∗ • L7 = (ab + cb)∗

3.2

Konecˇny´ automat podle regula´rnı´ gramatiky

Pokud podle regula´rnı´ gramatiky vytva´rˇ´ıme konecˇny´ automat, tak vlastneˇ tento konecˇny´ automat simuluje generovańı´ sve´ho vstupu v pu˚vodnı´ gramatice. Jeden krok automatu skla´dajıćı´ se z nacˇtenı´ signa´lu ze vstupu a prˇechodu do na´sledujıćı´ho stavu odpovı´da´ pouzˇitı´ jednoho pravidla v gramatice, a to takove´ho, ktere´ generuje stejny´ termina´l (signa´l). Postupujeme takto: • mnozˇinu termina´lu˚ gramatiky pouzˇijeme pro abecedu automatu, • mnozˇinu netermina´lu˚ pouzˇijeme pro stavy,

• stav vytvorˇeny´ ze startovacı´ho symbolu gramatiky bude pocˇa´tecˇnı´m stavem,

• do mnozˇiny stavu˚ take´ prˇida´me novy´ stav (obvykle znacˇeny´ X), ktery´ se stane koncovy´m,

• pokud je v jazyce generovane´m gramatikou slovo ε, pak pocˇa´tecˇnı´ stav automatu bude take´ patrˇit do mnozˇiny koncovyćh stavu˚, aby automat rozpozna´val slovo ε, • δ-funkci vytvorˇ´ıme podle pravidel gramatiky. Prˇı´klad 3.5 Vytvorˇ´ıme konecˇny´ automat rozpozna´vajıćı´ jazyk generovany´ touto gramatikou: G = ({S, A, B}, {a, b}, P, S) s teˇmito pravidly: S → aS | bA A → aA | aB | a B → bB | b V gramatice nenı´ zˇa´dne´ ε-pravidlo (tj. pravidlo, na jehozˇ prave´ straneˇ je rˇeteˇzec ε), proto pocˇa´tecˇnı´ stav nebude patrˇit do mnozˇiny koncovyćh stavu˚ (tato mnozˇina bude jednoprvkova´). Jako abecedu pouzˇijeme mnozˇinu termina´lu˚, stavy vytvorˇ´ıme z netermina´lu˚ a prˇida´me jeden koncovy´ stav X. Prˇechody tvorˇ´ıme podle pravidel gramatiky – naprˇ´ıklad podle pravidla A → aB prˇida´me do δ-funkce δ(A, a) 3 B. Postup je dobrˇe videˇt na δ-funkci: A = ({S, A, B, X}, {a, b}, δ, S, {X}) δ(S, a) = {S} podle S → aS δ(S, b) = {A} podle S → bA δ(A, a) = {A, B, X} podle A → aA | aB | a δ(B, b) = {B, X} podle B → bB | b

M

KAPITOLA 3


51

Podobneˇ sestrojı´me stavovy´ diagram a tabulku prˇechodu˚: a b S

a b a A B a b

→ S A B ← X

X

a

b

S A, B, X

A B, X

Jazyk generovany´ gramatikou a rozpozna´vany´ automatem je L(G) = L(A) = a∗ ba∗ a(ε + b∗ b)

Prˇı´klad 3.6 Narozdı´l od prˇedchozı´ho prˇ´ıkladu zde ma´me gramatiku s ε-pravidlem: G = ({S, A, B}, {a, b}, P, S), v mnozˇineˇ P jsou pravidla S → bA | ε A → aB | a B → bA | b V jazyce generovane´m gramatikou je take´ pra´zdne´ slovo ε a toto slovo musı´ prˇijı´mat i konecˇny´ automat, ktery´ vytvorˇ´ıme. To lze zajistit pouze tak, zˇe pocˇa´tecˇnı´ stav automatu prˇida´me do mnozˇiny koncovyćh stavu˚. A = ({S, A, B, X}, {a, b}, δ, S, {S, X}) δ(S, b) = {A} δ(A, a) = {B, X} δ(B, b) = {A, X}

a b S A B b a b X

a ↔ S A B ← X

M

b A

B, X A, X

Jazyk generovany´ gramatikou a rozpozna´vany´ automatem je L(G) = L(A) = ε + b(ab)∗ a + b(ab)∗ ab = ε + b(ab)∗ a(ε + b)

´ koly U Podle na´sledujıćıćh gramatik sestrojte ekvivalentnı´ konecˇny´ automat (tj. rozpozna´vajıćı´ jazyk generovany´ touto gramatikou). G1 = ({S, A, B}, {a, b, c}, P, S) S → aS | bS | cA A → aA | cB | a B → bB | cA | b

G2 = ({A, B, C}, {0, 1}, P, A)

A → 0B | 1C | ε B → 0C | 1C C → 1B | 0

C

KAPITOLA 3


G3 = ({R, Y, Z, W }, {a, b, c}, P, R) R → aR | bR | cZ Y → cR | aY | b Z → aY | aW W → bR | b

3.3

52 G4 = ({S, A, B, C}, {0, 1, 2}, P, S)

S → 0A | 1B | 2C | ε A → 0B | 0 B → 1C | 1 C → 2A

Regula´rnı´ gramatika podle konecˇne´ho automatu

Prˇi vytvorˇenı´ gramatiky generujıćı´ jazyk, ktery´ je rozpozna´vań dany´m konecˇny´m automatem, je nejjednodusˇsˇ´ı obra´tit postup, ktery´ jsme pouzˇili pro vytvorˇenı´ automatu podle gramatiky. Kdyzˇ jsme sestrojili konecˇny´ automat podle regula´rnı´ gramatiky, automat meˇl vzˇdy tyto vlastnosti: • pokud v jazyce generovane´m gramatikou nenı´ slovo ε, pak

– existuje jediny´ koncovy´ stav (noveˇ prˇidany´), obvykle pojmenovany´ X, – ze stavu X nevede zˇa´dny´ prˇechod (tj. kdyzˇ se vy´pocˇet dostane do koncove´ho stavu, nelze da´le pokracˇovat). • pokud v jazyce generovane´m gramatikou je slovo ε, pak

– kromeˇ noveˇ prˇidane´ho koncove´ho stavu X je v mnozˇineˇ koncovyćh stavu˚ i pocˇa´tecˇnı´ stav, – ze stavu X nevede zˇa´dny´ prˇechod, – do pocˇa´tecˇnı´ho stavu nevede zˇa´dny´ prˇechod (ekvivalent k faktu, zˇe pokud v gramatice ma´me pravidlo S → ε, pak se symbol S nesmı´ vyskytovat na prave´ straneˇ zˇa´dne´ho pravidla). Abychom tedy mohli pouzˇ´ıt opacˇny´ postup k postupu prˇedchozı´mu, musı´me zadany´ automat ´ prava spocˇ´ıva´ v teˇchto nejdrˇ´ıv upravit do tvaru odpovı´dajıćı´ho vy´sˇe uvedeny´m pozˇadavku˚m. U krocıćh (jejich porˇadı´ je du˚lezˇite´): 1. Jestlizˇe pocˇa´tecˇnı´ stav patrˇ´ı do mnozˇiny koncovyćh stavu˚ a za´rovenˇ do tohoto stavu vede neˇktery´ prˇechod: • vytvorˇ´ıme novy´ pocˇa´tecˇnı´ stav (take´ zarˇadı´me do mnozˇiny koncovyćh stavu˚), do ktere´ho nebudou ve´st zˇa´dne´ prˇechody, ale z neˇho budou ve´st tyte´zˇ prˇechody jako z pu˚vodnı´ho pocˇa´tecˇnı´ho stavu, • pu˚vodnı´ pocˇa´tecˇnı´ stav zu˚stane v mnozˇineˇ koncovyćh stavu˚. 2. Pokud je v mnozˇineˇ koncovyćh stavu˚ vıće nezˇ jeden stav (prˇ´ıpadneˇ kromeˇ pocˇa´tecˇnı´ho stavu, toho se tento bod nety´ka´): • vytvorˇ´ıme novy´ koncovy´ stav X (nebo jinak oznacˇeny´), • ze stavu X nepovede zˇa´dny´ prˇechod, ale do tohoto stavu povedou tyte´zˇ prˇechody, ktere´ vedou do pu˚vodnıćh koncovyćh stavu˚, • pu˚vodnı´ koncove´ stavy sice v automatu necha´me, ale vyrˇadı´me je z mnozˇiny koncovyćh stavu˚ (nety´ka´ se pocˇa´tecˇnı´ho stavu). 3. Jestlizˇe z koncove´ho stavu vedou prˇechody, proble´m vyrˇesˇ´ıme stejneˇ jako v prˇedchozı´m bodeˇ.

KAPITOLA 3


53

Prˇı´klad 3.7 Nejdrˇ´ıv si uka´zˇeme jednodusˇsˇ´ı prˇ´ıpad – konecˇny´ automat odpovı´dajıćı´ uvedeny´m pozˇadavku˚m. Jak vidı´me, stav q2 zde vlastneˇ zastupuje stav X podle prˇedchozı´ho postupu. To znamena´, zˇe v gramatice bude mnozˇina netermina´lu˚ dvouprvkova´ – {q0 , q1 }, ze stavu q2 zˇa´dny´ netermina´l nevytvorˇ´ıme a pravidla, ktera´ s nı´m souvisejı´, budou slouzˇit k ukoncˇenı´ generovańı´ slova. Mu˚zˇeme take´ prˇejmenovat netermina´ly.

→ q0 q1 ← q2

a

b

q1 q2

q2 q1

Podle automatu: G = ({q0 , q1 }, {a, b}, P, q0 ) q0 → aq1 | b q1 → a | bq1

a q0 b

b a q1

M

q2

Prˇejmenovane´ stavy: G = ({A, B}, {a, b}, P, A) A → aB | b B → a | bB

Gramatika, kterou jsme vytvorˇili, generuje jazyk L(G) = ab∗ a + b, cozˇ je take´ jazyk rozpozna´vany´ zadany´m automatem.

Prˇı´klad 3.8 Vytvorˇ´ıme regula´rnı´ gramatiku generujıćı´ jazyk tohoto automatu: b a S

cˇa´tecˇnı´, proto musı´me redukovat pocˇet koncovyćh stavu˚. Navıć a B A z obou koncovyćh stavu˚ vycha´zejı´ prˇechody, to je dalsˇ´ı du˚vod pro transformaci. c b Vytvorˇ´ıme stav X, do ktere´ho nasmeˇrujeme vsˇechny prˇeC chody mı´rˇ´ıcı´ do pu˚vodnıćh koncovyćh stavu˚. Stav X pak bude

Tento automat ma´ dva koncove´ stavy, z nichzˇ zˇa´dny´ nenı´ po-

M

jediny´m koncovy´m stavem. Po u´praveˇ sestrojı´me regula´rnı´ gramatiku stejneˇ jako u prˇedchozı´ho prˇ´ıkladu. b a S a

a A a c c X

B b C

→ S A B C ← X

a

b

A, X B, X

S

c

C A, X

G = ( {S, A, B, C}, {a, b, c}, P, S) S → aA | a | bS A → aB | a B → bC C → cA | c

Jazyk generovany´ gramatikou je L(G) = b∗ a(abc)∗ (ε + a).

Prˇı´klad 3.9 Na´sledujıćı´ automat nemusı´me upravovat, mu˚zˇeme prˇ´ımo napsat regula´rnı´ gramatiku – startovacı´ symbol patrˇ´ı do mnozˇiny koncovyćh stavu˚, ale do neˇho nevede zˇa´dny´ prˇechod.

M

KAPITOLA 3


0 1 1 S A

B

54

↔ S A ← B

0

1

A

A B

G = ({S, A}, {0, 1}, P, S) S → 1A | ε A → 0A | 1

Generovany´ (rozpozna´vany´) jazyk je L(G) = 10∗ 1.

Prˇı´klad 3.10

0 V poslednı´m prˇ´ıkladu si uka´zˇeme prˇevod automatu, jehozˇ 0 S B A pocˇa´tecˇnı´ stav je za´rovenˇ stavem koncovy´m a vedou do neˇho 1 prˇechody. Nejdrˇ´ıv automat upravı´me. Prˇida´me novy´ (pocˇa´tecˇnı´) stav C, ktery´ take´ bude patrˇit do mnozˇiny koncovyćh stavu˚ (aby automat mohl rozpoznat pra´zdne´ slovo ε) – tento stav bude vyuzˇit pouze na zacˇa´tku vy´pocˇtu. Potom prˇida´me novy´ koncovy´ stav X, ktery´ vyuzˇijeme na konci kazˇde´ho vy´pocˇtu. Pu˚vodnı´ koncove´ stavy (kromeˇ pocˇa´tecˇnı´ho stavu C vyrˇadı´me z mnozˇiny koncovyćh stavu˚. 0 C

0 0 S A 1

B

0 C 0 S 1

0 A

@ @ B @

0, 1

↔ C S A ← X

0

1

A A B, X

X

X

Ze stavu B nevede cesta do koncove´ho stavu, proto mu˚zˇe by´t odstraneˇn. Vy´sledna´ gramatika je na´sledujıćı´: G = ({C, S, A}, {0, 1}, P, C) C → 0A S → 0A A → 0B | 0 | 1 Jazyk generovany´ gramatikou G vyja´drˇeny´ regula´rnı´m vy´razem je L(G) = 0(10)∗ (0 + 1).

M


KAPITOLA 3

55

´ koly U K na´sledujıćı´m konecˇny´m automatu˚m vytvorˇte ekvivalentnı´ regula´rnı´ gramatiky: a b 1 2 a a

b 1 a a

(c)

(d)

a b 1 2 a a a 3

(b)

(e)

a b 1 a

b 2

(f)

a b 3 2

a

4

3

(a)

C

b 3

1, . . . , 9 0, . . . , 9 B A 0, . . . , 9 0 , , 0, . . . , 9 C E D

(g)

(h)

b

a 2 1 b a a

3

b b q1 q0 b a b q1 q0 0

1 A

(i)

0 B 0

C

Kapitola

4

Bezkontextove´ gramatiky 4.1

Vytva´rˇı´me bezkontextovou gramatiku

Bezkontextove´ gramatiky majı´ obecneˇjsˇ´ı tvar pravidel nezˇ regula´rnı´ – na leve´ straneˇ pravidla je vzˇdy jeden netermina´l (jako u regula´rnıćh), ale na prave´ straneˇ je jaky´koliv rˇeteˇzec skla´dajıćı´ se z termina´lu˚ a netermina´lu˚ (vcˇetneˇ pra´zdne´ho rˇeteˇzce). Kdyzˇ chceme sestrojit bezkontextovou gramatiku pro zadany´ jazyk, pokusı´me se popsat strukturu tohoto jazyka s vyuzˇitı´m rekurze. Prˇı´klad 4.1 Sestrojı´me bezkontextovou gramatiku pro jazyk L = {an ban b | n ≥ 0} a vytvorˇ´ıme derivaci (odvozenı´) slova aabaab. G = ({S, A}, {a, b}, P, S) S → Ab A → aAa | b Netermina´l A generuje te´meˇrˇ cele´ slovo, azˇ na poslednı´ symbol b. Cˇa´st slova generovana´

M

tı´mto netermina´lem je symetricka´, proto pravidla jsou vlastneˇ linea´rnı´ (kazˇda´ linea´rnı´ gramatika je za´rovenˇ bezkontextova´, tedy zadańı´ je v tomto smeˇru splneˇno). Na´sleduje derivace slova aabaab: S ⇒ Ab ⇒ aAab ⇒ aaAaab ⇒ aabaab

Prˇı´klad 4.2 Sestrojı´me bezkontextovou gramatiku generujıćı´ jazyk L = {wcwR ; w ∈ {a, b}∗ }

Vidı´me, zˇe uprostrˇed slova je symbol c. Da´le poloviny slova jsou navza´jem symetricke´, zrcadlı´ se. Gramatika tedy bude vypadat takto: G = ({S}, {a, b}, P, S) S → aSa | bSb | c 56

M

KAPITOLA 4

BEZKONTEXTOVE´ GRAMATIKY

57

Podle gramatiky vygenerujeme neˇkolik slov: S⇒c S ⇒ aSa ⇒ abSba ⇒ abbSbba ⇒ abbcbba S ⇒ bSb ⇒ bbSbb ⇒ bbcbb I zde platı´ – v jednoduchosti je sı´la. Zde navıć je jednoduchost nezbytna´. Kdybychom pouzˇili dalsˇ´ı netermina´ly a naprˇ´ıklad bychom prˇidali pravidlo S → AcA a pak A → aA | bA a pak neˇco na ukoncˇenı´ rekurze, gramatika by generovala u´plneˇ jiny´ jazyk. Vzˇdy, pokud potrˇebujeme synchronizovat dveˇ cˇa´sti slova (naprˇ´ıklad zde pouzˇitı´ symbolu a nebo symbolu b), musı´me to prove´st v jedine´m pravidle! Jinak by synchronizace nefungovala. ´ koly U Sestrojte bezkontextove´ gramatiky generujıćı´ tyto jazyky: {an bn

; n ≥ 1} • L2 = {wwR ; w ∈ {a, b}∗ } (pozn.: v bezkontextovyćh gramatikaćh mu˚zˇeme pouzˇ´ıt ε-pravidlo

• L1 =

L C

kdekoliv – u ktere´hokoliv netermina´lu, a taky tento netermina´l klidneˇ mu˚zˇe by´t na prave´ straneˇ jake´hokoliv pravidla)

• L3 = {an bn ck ; n, k ≥ 0}

• L4 = {(01)n 12n ; n ≥ 1}

4.2

Derivacˇnı´ strom

Derivace je odvozenı´ slova v gramatice. Kazˇde´ slovo jazyka generovane´ho gramatikou ma´ tedy (nejmeńeˇ jednu) svou derivaci. Derivacˇnı´ strom je vlastneˇ graf, ktery´ je stromem (ma´ jediny´ korˇen, kazˇdy´ uzel kromeˇ korˇene ma´ pra´veˇ jednoho prˇedka a hrany jsou orientovane´, i kdyzˇ orientaci neznacˇ´ıme), tvorˇeny´ podle pravidel gramatiky pouzˇityćh v derivaci, podle ktere´ je derivacˇnı´ strom vytvorˇen. Pozor – ke kazˇde´ derivaci lze sestrojit pra´veˇ jeden derivacˇnı´ strom, je to vlastneˇ graficke´ zna´zorneˇnı´ derivace dane´ho slova. Pokud pro toto slovo existuje vıć ru˚znyćh derivacı´ (tj. slovo lze v gramatice odvodit neˇkolika ru˚zny´mi zpu˚soby), mu˚zˇe existovat pro jedno slovo vıće derivacˇnıćh stromu˚. Prˇı´klad 4.3 Sestrojı´me bezkontextovou gramatiku pro jazyk L = {0n 102n 1i ; i, n ≥ 1}, vytvorˇ´ıme derivaci slova 0010000111 a derivacˇnı´ strom k te´to derivaci. G = ({S, A, B}, {0, 1}, P, S) S → AB A → 0A00 | 0100 B → 1B | 1

P M


KAPITOLA 4

58

Derivace slova 0010000111 je na´sledujıćı´: S ⇒ AB ⇒ 0A00B ⇒ 0010000B ⇒ 00100001B ⇒ 001000011B ⇒ 0010000111 Modrˇe je vyznacˇena prava´ cˇa´st pravidla, ktere´ bylo v dane´m kroku odvozenı´ pouzˇito (naprˇ´ıklad v druhe´m kroku jsme pouzˇili pravidlo A → 0A00). Derivacˇnı´ strom se vzˇdy vztahuje ke konkre´tnı´ derivaci. Podle vy´sˇe uvedene´ derivace postupneˇ sestrojı´me derivacˇnı´ strom takto (jsou uvedeny i mezikroky): S ⇒ AB

S ⇒ AB ⇒ 0A00B S → AB

S A

A → 0A00 B

A A

0

S ⇒ AB ⇒ 0A00B ⇒ 0010000B A → 0100

B

0

0

S ⇒ . . . ⇒ 0010000B ⇒ 00100001B B → 1B

S A

S

S A

B

B

0

A

0

0

0

A

0

0

0

1

0

0

0

1

0

0

S ⇒ . . . ⇒ 00100001B ⇒ 001000011B B → 1B

S ⇒ . . . ⇒ 001000011B ⇒ 0010000111 B→1

S A

S A

B

0

A

0

0

0

1

0

0

1

B 1

B

1

B

B

0

A

0

0

0

1

0

0

1

B 1

B 1

V jednotlivyćh krocıćh je kromeˇ samotne´ho stromu uvedeno pouzˇite´ pravidlo a take´ momenta´lnı´ stav derivace. Modrˇe je vyznacˇena veˇtna´ forma, kterou jsme v dane´m kroku vytvorˇili. Mu˚zˇeme si vsˇimnout, zˇe v derivacˇnı´m stromeˇ vzˇdy jde o obsah listu˚ stromu v dane´m kroku. Derivacˇnı´ strom dane´ derivace je poslednı´ v porˇadı´.

KAPITOLA 4


59

´ koly U 1. Podle gramatiky a uvedene´ derivace z prˇ´ıkladu 4.1 sestrojte derivacˇnı´ strom.

C

2. Podle zadane´ gramatiky vytvorˇte derivaci slova ababa a k nı´ derivacˇnı´ strom. G = ({S, A, B}, {a, b}, P, S) S → bAB | aBA | ε A → abAab | ε B → baBba | ε

3. Podle gramatiky z prˇedchozı´ho prˇ´ıkladu vytvorˇte derivaci jake´hokoliv slova o de´lce alesponˇ 6 zacˇ´ınajıćı´ho symbolem b a k te´to derivaci sestrojte derivacˇnı´ strom. 4. Sestrojte gramatiky generujıćı´ na´sledujıćı´ jazyky. V kazˇde´m jazyce vyberte jake´koliv slovo o de´lce alesponˇ 3 symboly, vytvorˇte jeho derivaci a sestrojte k nı´ derivacˇnı´ strom. (a) L1 = (ab)i cj (ba)i ; i, j ≥ 0

(b) L2 = {0n 11n ; n ≥ 3} ∪ {ε}

(c) L3 = 0i 10i ; i ≥ 1 ∪ 1i 01i ; i ≥ 1

(d) L4 = {abc, bad, f aa, diff } koliv rˇeteˇzec)

4.3 4.3.1

(nezapomenˇte, zˇe na prave´ straneˇ pravidla mu˚zˇe by´t jaky´-

´ pravy bezkontextovyćh gramatik U Prˇevod na nezkracujıćı´ bezkontextovou gramatiku

Nezkracujıćı´ bezkontextova´ gramatika bud’ vu˚bec neobsahuje ε-pravidla (pokud v jazyce generovane´m gramatikou nenı´ pra´zdne´ slovo), a nebo existuje jedine´ takove´ pravidlo, a to pro startovacı´ symbol gramatiky, pak ale se startovacı´ symbol nesmı´ vyskytovat na prave´ straneˇ zˇa´dne´ho pravidla (to znamena´, zˇe v kazˇde´ derivaci se vyskytuje pouze na jejı´m zacˇa´tku, pak uzˇ ne). Prˇi prˇevodu na nezkracujıćı´ gramatiku odstranˇujeme ε-pravidla tak, zˇe „simulujeme“ jejich pouzˇitı´. Prˇı´klad 4.4 K na´sledujıćı´ gramatice vytvorˇ´ıme ekvivalentnı´ gramatiku s nezkracujıćı´mi pravidly. G = ({S, A, B}, {a, b}, P, S) S → aaB | bAb A → aBa | ε B → AbAa | a Te´meˇrˇ vsˇechna pravidla jsou nezkracujıćı´, je zde pouze jedine´ ε-pravidlo – A → ε. Prˇepisovany´ symbol A se nacha´zı´ na prave´ straneˇ dvou pravidel – druhe´ho a pa´te´ho. Obeˇ tato pravidla necha´me a prˇida´me jejich varianty se „simulovany´m“ pouzˇitı´m ε-pravidla:

M

KAPITOLA 4


60

G0 = ({S, A, B}, {a, b}, P 0 , S) S → aaB | bAb | bb A → aBa B → AbAa | bAa | Aba | ba | a U prvnı´ho ze zpracova´vanyćh pravidel ma´me jen jeden vy´skyt netermina´lu A, tedy existuje pouze jedina´ dalsˇ´ı varianta (toto jedine´ A odstranı´me – prˇepı´sˇeme na ε). U druhe´ho zpracova´vane´ho pravidla jsou dva vy´skyty netermina´lu A, proto musı´me vytvorˇit variant vıće – odstranı´me jen prvnı´ A, odstranı´me jen druhe´, a nebo odstranı´me obeˇ. Derivace v gramatice G0 bude te´meˇrˇ stejna´ jako v gramatice G, ale kroky s pouzˇitı´m ε-pravidel jsou „prˇeskocˇeny“, naprˇ´ıklad v gramatice G: S ⇒ aaB ⇒ aaAbAa ⇒ aabAa ⇒ aabaBaa ⇒ aabaaaa v gramatice G0 : S ⇒ aaB ⇒ aabAa ⇒ aabaBaa ⇒ aabaaaa

Prˇı´klad 4.5 K zadane´ gramatice vytvorˇ´ıme ekvivalentnı´ nezkracujıćı´ gramatiku (tj. generujıćı´ tenty´zˇ jazyk). G = ({S, A}, {a, b, c}, P, S) S → aaS | bbA | ε A → cSbSc | ε Gramatika generuje take´ pra´zdne´ slovo. Proto nejdrˇ´ıv pouzˇijeme stejny´ postup jako v prˇedchozı´m prˇ´ıkladu, ale pak jesˇteˇ musı´me zajistit, aby vy´sledna´ gramatika take´ generovala pra´zdne´ slovo a prˇitom zu˚stala nezkracujıćı´. Nejdrˇ´ıv vytvorˇ´ıme pomocnou gramatiku G0 , ktera´ nema´ zˇa´dna´ ε-pravidla, jejı´ jazyk je L(G0 ) = L(G) − {ε}. G0 = ({S, A}, {a, b, c}, P 0 , S) S → aaS | aa | bbA | bb A → cSbSc | cbSc | cSbc | cbc Prˇida´me novy´ startovacı´ symbol a vytvorˇ´ıme gramatiku ekvivalentnı´ pu˚vodnı´ gramatice. G00 = ({S 0 , S, A}, {a, b, c}, P 00 , S 0 ) S0 → S | ε S → aaS| aa | bbA| bb A → cSbSc | cbSc | cSbc | cbc Derivace v gramatice G: S ⇒ aaS ⇒ aaaaS ⇒ aaaa 00 Derivace v gramatice G : S 0 ⇒ S ⇒ aaS ⇒ aaaa

Prˇı´klad 4.6 Neˇkdy se mu˚zˇe sta´t, zˇe „simulacı´“ ε-pravidla vytvorˇ´ıme dalsˇ´ı ε-pravidlo. Pak je trˇeba postup prova´deˇt rekurzı´vneˇ tak dlouho, dokud nejsou vsˇechna ε-pravidla odstraneˇna. G = ({S, A, B}, {a, b}, P, S) S → bA | aS | bB | a A → baB | ε B → AA | b

M

M

KAPITOLA 4


61

Po odstraneˇnı´ pravidla A → ε dostaneme tuto gramatiku: G0 = ({S, A, B}, {a, b}, P 0 , S) S → bA | b | aS | bB | a A → baB B → AA | A | ε | b Odstraneˇnı´m obou symbolu˚ A v pravidle B → AA vzniklo dalsˇ´ı ε-pravidlo, ktere´ je take´ trˇeba odstranit: G00 = ({S, A, B}, {a, b}, P 00 , S) S → bA | b | aS | bB | b | a A → baB | ba B → AA | A | b Rekurze prˇi rˇesˇenı´ pravidel se zbavı´me tak, zˇe ji prˇeneseme jinam. Mu˚zˇeme pouzˇ´ıt rˇesˇenı´ podobne´ tomu z redukce gramatiky – vytvorˇ´ıme (rekurzı´vneˇ) mnozˇinu Nε vsˇech netermina´lu˚, ktere´ lze (trˇeba i po vıće nezˇ jednom kroku) prˇepsat na pra´zdne´ slovo ε. V mnozˇineˇ Nε,0 bude pouze pra´zdny´ rˇeteˇzec, tj. Nε,0 = {ε}. V dalsˇ´ıch krocıćh do te´to mnozˇiny prˇida´va´me netermina´ly, ktere´ lze prˇepsat na rˇeteˇzec skla´dajıćı´ se pouze ze symbolu˚, ktere´ byly do te´to mnozˇiny prˇidańy v prˇedchozıćh krocıćh, tj. Nε,i = Nε,i−1 ∪ {X ∈ N | X → α, α ∈ Nε,i−1 }. Prˇı´klad 4.7 Podle pravidel gramatiky G = ({S, A, B, C, D}, {a, b, c, d}, P, S) S → aAa | aa A → BC | b B → aC | cD | ε C → AAa | ε D → AAB | d vytvorˇ´ıme tyto mnozˇiny: Nε,0 = {ε} Nε,1 = {B, C} podle B → ε, C → ε, pra´zdne´ slovo uzˇ nezarˇazujeme Nε,2 = {B, C, A} podle A → BC Nε,3 = {B, C, A, D} podle D → AAB V dalsˇ´ım kroku jizˇ nelze dalsˇ´ı netermina´l prˇidat (ostatneˇ vsˇechny uzˇ v mnozˇineˇ jsou), proto Nε = Nε,3 = {B, C, A, D}. Mnozˇiny pouzˇijeme takto: pokud je na prave´ straneˇ pravidla neˇktery´ z netermina´lu˚ obsazˇenyćh v mnozˇineˇ Nε , pak vytvorˇ´ıme dalsˇ´ı pravidla se „simulovany´m“ pouzˇitı´m ε-pravidel na tento netermina´l, ε-pravidla odstranı´me. Postup je prakticky stejny´ jako prˇedchozı´, ale zpracovańı´ gramatiky jizˇ nenı´ trˇeba prova´deˇt rekurzı´vneˇ (rekurze byla pouzˇita prˇi generovańı´ mnozˇiny Nε ). Fialovou barvou jsou zvy´razneˇny netermina´ly obsazˇene´ v mnozˇineˇ Nε (a tedy vytvorˇ´ıme pravidlo, ve ktere´m je odstranı´me), modrou barvou pak nova´ pravidla.

L M

KAPITOLA 4


62

S → aAa | aa | aa (vlastneˇ ma´me dveˇ stejna´ pravidla, jedno mu˚zˇe by´t odstraneˇno) A → BC | C | B | b B → aC | a | cD | c C → AAa | Aa | a D → AAB | AB | B | d

Prˇı´klad 4.8 Postup prˇedvedeny´ v prˇedchozı´m prˇ´ıkladu pouzˇijeme na gramatiku z prˇ´ıkladu 4.6. G = ({S, A, B}, {a, b}, P, S) S → bA | aS | bB | a A → baB | ε B → AA | b Opeˇt rekurzı´vneˇ vytvorˇ´ıme mnozˇinu Nε : Nε,0 = {ε} Nε,1 = {A} Nε,2 = {A, B} = Nε,3 = Nε Vycha´zı´ na´m tato gramatika: 0 G = ({S, A, B}, {a, b}, P 0 , S) S → bA | b | aS | bB | b | a A → baB | ba B → AA | A | b Oproti pu˚vodnı´mu rˇesˇenı´ nenı´ trˇeba neˇkolikra´t prˇepisovat pravidla gramatiky.

´ koly U K na´sledujıćı´m gramatika´m vytvorˇte ekvivalentnı´ nezkracujıćı´ gramatiky. G1 = ({S, A, B}, {a, b}, P, S) S → aSbA | ab A → aAbA | ε B → bAbB | b

G3 = ({S, A, B}, {a, b}, P, S) S → BAa | aS | ε A → aA | ε B → bBA | ε

G2 = ({S, A}, {0, 1}, P, S) S → S1S1 | A | ε A → 0A0 | 1

G4 = {S, A, B}, {a, b}, P, S) S → AB | BA | b A → aaA | ε B → AA | bS | a

M

C

KAPITOLA 4

4.3.2


63

Redukce gramatiky

´ cˇelem redukce gramatiky je snı´zˇenı´ pocˇtu netermina´lu˚ prˇi zachovańı´ generovane´ho jazyka. OdU stranˇujeme • nadbytecˇne´ netermina´ly (tj. netermina´ly, ze kteryćh nelze vygenerovat zˇa´dne´ termina´lnı´ slovo),

• nedostupne´ symboly (termina´lnı´ i netermina´lnı´ – nelze je vygenerovat ze startovacı´ho symbolu).

Zachova´va´me toto porˇadı´ – nejdrˇ´ıv nadbytecˇne´ a pak teprve nedostupne´. Pouzˇ´ıva´me podobny´ postup jako prˇi redukci mnozˇiny stavu˚ konecˇne´ho automatu. Prˇı´klad 4.9 Redukujeme na´sledujıćı´ gramatiku: G = ({S, A, B, C, D}, {a, b, c, d}, P, S) S → bS | bD | ε A → aCB | bAD B → dB | d C → bCC | aAbB D → bA | cDb | aS | ε Nejdrˇ´ıv odstranı´me nadbytecˇne´ netermina´ly. Rekurzı´vneˇ vytvorˇ´ıme mnozˇinu vsˇech symbolu˚, ktere´ jsou bud’ termina´lnı´ a nebo z nich lze vygenerovat termina´lnı´ rˇeteˇzec (v prˇ´ıpadeˇ, zˇe jde o netermina´l). Ba´zı´ rekurze je mnozˇina vsˇech termina´lu˚. V dalsˇ´ıch krocıćh prˇida´va´me netermina´ly z levyćh stran pravidel, na jejichzˇ prave´ straneˇ jsou pouze symboly, ktere´ jsme do nasˇ´ı mnozˇiny prˇidali v prˇedchozıćh krocıćh (a nebo pro neˇ existuje ε-pravidlo). N0 = {a, b, c, d} N1 = {a, b, c, d, S, B, D} (podle pravidel S → ε, B → d, D → ε) N2 = {a, b, c, d, S, B, D} (podle pravidel S → bS | bD, B → dB, D → cDb | aS) Protozˇe jsme do mnozˇiny N2 oproti mnozˇineˇ N1 nic dalsˇ´ıho neprˇidali, rekurze koncˇ´ı. Mnozˇina netermina´lu˚ bude N ∩ N2 = {S, B, D}, vyrˇadı´me netermina´ly A a C vcˇetneˇ vsˇech pravidel, ktera´ je obsahujı´ na leve´ nebo prave´ straneˇ. Gramatika po odstraneˇnı´ nadbytecˇnyćh symbolu˚ je na´sledujıćı´: G0 = ({S, B, D}, {a, b, c, d}, P 0 , S) S → bS | bD | ε B → dB | d D → cDb | aS | ε Zby´va´ odstranit nedostupne´ symboly. Postupujeme opeˇt rekurzı´vneˇ. Vytvorˇ´ıme mnozˇinu symbolu˚, ktere´ se nacha´zejı´ v neˇjake´ veˇtne´ formeˇ v derivaci ze startovacı´ho symbolu. Zacˇneme mnozˇinou obsahujıćı´ pouze startovacı´ symbol, v kazˇde´m kroku prˇida´va´me symboly, ktere´ se nacha´zejı´ na pravyćh stranaćh pravidel prˇepisujıćıćh symboly zarˇazene´ v prˇedchozıćh krocıćh. V0 = {S} V1 = {S, b, D} (podle pravidel S → bS | bD) V2 = {S, b, D, c, a} (podle pravidel D → cDb | aS) V3 = V2 Z postupu vyply´va´, zˇe pokud v neˇktere´m kroku prˇida´me pouze termina´lnı´ symboly, v na´sledujıćı´m kroku jizˇ nelze nic prˇidat (protozˇe termina´ly se neprˇepisujı´ zˇa´dny´m pravidlem) a rekurze

M

KAPITOLA 4


64

koncˇ´ı. Je zrˇejme´, zˇe nedostupny´ netermina´l je jeden (B) a termina´l takte´zˇ jeden (d). Redukovana´ gramatika (tj. jizˇ bez nadbytecˇnyćh i nedostupnyćh symbolu˚) je na´sledujıćı´: G00 = ({S, D}, {a, b, c}, P 00 , S) S → bS | bD | ε D → cDb | aS | ε

´ koly U Redukujte tyto gramatiky: G1 = ({S, A, B, C, D}, {a, b, c, d}, P, S) S → aBa | bA | c | ABc A → aA | dD | bDa B → aB | bA | bS C → aSc | cC | c D → dD | aAb

4.3.3

G2 = ({S, A, B, C, D, E}, {0, 1, 2, 3}, P, S) S → AB0 | 2E | A1 | ε A → 0A0 | 1B | 1S B → 01B | 1D | EB C → 2A | 1S | 0 D → D1 | 3B E → 0E1 | 1B

C

Odstraneˇnı´ jednoduchyćh pravidel

Jednoducha´ pravidla jsou takova´ pravidla, na jejichzˇ prave´ straneˇ ma´me jen jediny´ symbol, a to netermina´l, naprˇ´ıklad A → B. Jednoducha´ pravidla zbytecˇneˇ prodluzˇujı´ vy´pocˇet a v neˇkteryćh algoritmech mohou by´t prˇeka´zˇkou prˇi programovańı´. Pokud tento typ pravidel chceme odstranit, mu˚zˇeme jednodusˇe nahradit symbol na prave´ straneˇ jednoduche´ho pravidla celou mnozˇinou pravidel, na ktera´ se tento symbol prˇepisuje. Naprˇ´ıklad pokud existujı´ pravidla B → α | β | γ, pak jednoduche´ pravidlo A → B nahradı´me pravidly A → α | β | γ (v derivaci to bude znamenat zkraćenı´ odvozenı´ o jeden krok – zpracovańı´ jednoduche´ho pravidla). Protozˇe touto na´hradou mu˚zˇeme opeˇt pro dany´ netermina´l dostat jednoduche´ pravidlo, postup je rekurzivnı´ a lze ho zjednodusˇit prˇenesenı´m rekurze na mnozˇiny netermina´lu˚ podobneˇ jako v prˇedchozıćh postupech. Vytva´rˇ´ıme mnozˇiny NA postupneˇ pro vsˇechny netermina´ly A ∈ N , ktere´ inicializujeme jednoprvkovou mnozˇinou obsahujıćı´ netermina´l v oznacˇenı´ mnozˇiny (tj. v tomto prˇ´ıpadeˇ A). Jde o mnozˇiny netermina´lu˚, jejichzˇ pravidla se pomocı´ jednoduchyćh pravidel majı´ postupneˇ prˇipsat do mnozˇiny pravidel pro dany´ netermina´l A. Prˇı´klad 4.10 Odstranı´me jednoducha´ pravidla v na´sledujıćı´ gramatice: G = ({S, A, B, C}, {a, b}, P, S) S → aBa | A A → aA | B B → bB | AB | C | ε C → bA | b

M

KAPITOLA 4


65

Rekurzı´vneˇ vytvorˇ´ıme mnozˇiny NS , NA , NB , NC . Na zacˇa´tku rekurze, v ba´zi, bude v dane´ mnozˇineˇ pouze ten symbol, pro ktery´ mnozˇinu tvorˇ´ıme, tj. naprˇ´ıklad NS,0 = {S}. NS,0 = {S} NS,1 = {S, A} (podle S → A) NS,2 = {S, A, B} (podle A → B) NS,3 = {S, A, B, C} = NS,4 = NS (podle B → C)

NA,0 = {A} NA,1 = {A, B} (podle A → B NA,2 = {A, B, C} = NA,3 = NA

NB,0 = {B} NB,1 = {B, C} = NB,2 = NA

(podle B → C)

(podle B → C)

NC,0 = {C} = NC,1 = NC Z gramatiky odstranı´me vsˇechna jednoducha´ pravidla. Po jejich odstraneˇnı´ pak pouzˇijeme vytvorˇene´ mnozˇiny – pokud naprˇ´ıklad pro netermina´l A je NA = {A, B, C}, pak v gramatice pro netermina´l A pouzˇijeme vsˇechna pravidla, ktera´ v pu˚vodnı´ gramatice byla pro netermina´ly A, B, C. G0 = ({S, A, B, C}, {a, b}, P 0 , S) S → aBa | aA | bB | AB | ε | bA | b A → aA | bB | AB | ε | bA | b B → bB | AB | ε | bA | b C → bA | b Pokud na´m vadı´ pouze jednoducha´ pravidla jako takova´, prˇedchozı´ postup je dostacˇujıćı´. Jestlizˇe vsˇak je prˇeka´zˇkou samotne´ chovańı´ jednoduchyćh pravidel (naprˇ´ıklad prodluzˇovańı´ derivace), je trˇeba prˇedem odstranit ε-pravidla. Naprˇ´ıklad v gramatice z prˇ´ıkladu 4.11 po odstraneˇnı´ jednoduchyćh pravidel existuje derivace S ⇒ AB ⇒ A ⇒ . . ., kde nacha´zı´me ekvivalent pouzˇitı´ jednoduche´ho pravidla S → A z pu˚vodnı´ gramatiky. Prˇı´klad 4.11 Gramatiku z prˇ´ıkladu 4.11 prˇedem upravı´me – prˇevedeme na nezkracujıćı´. Pak teprve odstranı´me jednoducha´ pravidla. G = ({S, A, B, C}, {a, b}, P, S) S → aBa | A A → aA | B B → bB | AB | C | ε C → bA | b Po prˇevodu na nezkracujıćı´ gramatiku: Nε = {B, A, S} G0 = ({S, A, B, C}, {a, b}, P 0 , S) S → aBa | aa | A | ε A → aA | a | B B → bB | b | AB | A | B | C

M

KAPITOLA 4


66

C → bA | b Pravidlo S → ε mu˚zˇeme nechat, protozˇe se S nevyskytuje na prave´ straneˇ zˇa´dne´ho pravidla (nenı´ nutne´ vytva´rˇet novy´ startovacı´ symbol). Odstranı´me jednoducha´ pravidla: NS = {S, A, B, C} NA = {A, B, C} NB = {B, A, C} (vsˇimneˇte si rozdı´lu oproti podobne´ mnozˇineˇ v prˇ´ıkladu 4.11) NC = {C} G00 = ({S, A, B, C}, {a, b}, P 00 , S) S → aBa | aa | aA | a | ε | aA | a | bB | b | AB | bA | b A → aA | a | bB | b | AB | bA | b B → bB | b | AB | aA | a | bA | b C → bA | b

´ koly U Odstranˇte jednoducha´ pravidla z na´sledujıćıćh gramatik: G1 = ({S, A, B}, {0, 1}, P, S) S → 0A1 | B | ε A → 1S | S | B B → 1A | S | 0

4.3.4

G2 = ({S, A, B}, {a, b}, P, S) S → aA | bB | A A → bAb | S | ε B → aBa | A | a

Gramatika bez cyklu a vlastnı´ gramatika

Gramatika bez cyklu je takova´ gramatika, kde neexistuje zˇa´dna´ derivace A ⇒+ A pro jaky´koliv netermina´l A. Uzˇ z definice je zrˇejme´, jak gramatiku upravit, aby splnˇovala tuto vlastnost – stacˇ´ı ji prˇeve´st na nezkracujıćı´ gramatiku (bez ε-pravidel) a odstranit jednoducha´ pravidla. Vlastnı´ gramatika je gramatika bez cyklu, nezkracujıćı´ a bez nadbytecˇnyćh symbolu˚. Postup je tedy na´sledujıćı´: • prˇevedeme gramatiku na nezkracujıćı´, • odstranı´me jednoducha´ pravidla,

• odstranı´me nadbytecˇne´ symboly postupem, ktery´ jizˇ zna´me z redukce gramatiky.

4.3.5

Leva´ a prava´ rekurze

Gramatika je rekurzivnı´ zleva, pokud v nı´ existuje derivace A ⇒+ Aα, gramatika je rekurzı´vnı´ zprava, pokud v nı´ existuje derivace A ⇒+ αA, A je neˇktery´ netermina´l gramatiky, α je jaky´koliv rˇeteˇzec z termina´lu˚ a netermina´lu˚. Leva´ nebo prava´ rekurze na´m mu˚zˇe brańit v neˇkteryćh dalsˇ´ıch u´pravaćh a nebo v naprogramovańı´ postupu popsane´ho gramatikou. Obvykle na´m vadı´ jen leva´ a nebo jen prava´ rekurze, proto jejich odstraneˇnı´ rˇesˇ´ıme jednodusˇe prˇevodem na tu, ktera´ na´m nevadı´. Prˇi odstranˇovańı´ rekurze vycha´zı´me z toho, zˇe k te´muzˇ rˇeteˇzci lze dojı´t vıće ru˚zny´mi zpu˚soby. Uka´zˇeme si odstraneˇnı´ prˇ´ıme´ rekurze, jejı´zˇ existence je patrna´ prˇ´ımo z pravidla.

C

KAPITOLA 4


67

Prˇı´klad 4.12 Na´sledujıćı´ gramatiku zbavı´me prˇ´ıme´ leve´ rekurze. G = ({S, A, B}, {a, b, c}, P, S) S → aAb | b A → Aa | bB | ab B → Ba | Bb | ca Leva´ rekurze je v pravidlech A → Aa a da´le B → Ba | Bb. Nejdrˇ´ıv vyrˇesˇ´ıme prvnı´ z teˇchto pravidel – pro netermina´l A. Mnozˇinu pravidel A → Aa | bB | ab nahradı´me jinou mnozˇinou, ktera´ generuje tenty´zˇ rˇeteˇzec. Jak mu˚zˇe vypadat derivace z netermina´lu A? A ⇒ Aa ⇒ Aaa ⇒ Aaaa ⇒∗ Aai ⇒ bBai (generujeme zprava doleva, a to nejdrˇ´ıv rekurzı´vnı´m pravidlem, rekurze je pak ukoncˇena vlevo neˇktery´m nerekurzı´vnı´m pravidlem). Stejny´ rˇeteˇzec lze generovat pravou rekurzı´, a to prˇidańı´m nove´ho netermina´lu a u´pravou pravidel (pu˚vodnı´ pravidla jsou A → Aa | bB | ab): A → bBA0 | abA0 | bB | ab A0 → aA0 | a Derivace ze symbolu A pak vypada´ na´sledovneˇ: A ⇒ bBA0 ⇒ bBaA0 ⇒ bBaaA0 ⇒∗ bBai−1 A0 ⇒ bBai Zby´va´ upravit pravidla pro netermina´l B – B → Ba | Bb | ca, nahradı´me je pravidly B → caB 0 | ca B 0 → aB 0 | bB 0 | a | b Vytvorˇili jsme tedy ekvivalentnı´ gramatiku bez prˇ´ıme´ leve´ rekurze: 0 G = ({S, A, A0 , B, B 0 }, {a, b, c}, P 0 , S) S → aAb | b A → bBA0 | abA0 | bB | ab A0 → aA0 | a B → caB 0 | ca B 0 → aB 0 | bB 0 | a | b

M

Uvedeny´ postup je pouzˇitelny´ pouze na vlastnı´ gramatiku (tj. gramatiku bez cyklu, nezkracujıćı´, bez nadbytecˇnyćh symbolu˚). Gramatika z prˇedchozı´ho prˇ´ıkladu je vlastnı´, proto nebylo trˇeba ji prˇedem upravovat. Prˇı´klad 4.13 Odstranı´me prˇ´ımou levou rekurzi v na´sledujıćı´ gramatice: G = ({S, A, B}, {a, b, c}, P, S) S → bAa | c | A A → Ba | b | Abb B → aBb | Bbc | ca | ε Tato gramatika nenı´ vlastnı´. Je trˇeba nejdrˇ´ıv prˇeve´st ji na nezkracujıćı´, odstranit jednoducha´ pravidla a teprve potom mu˚zˇeme odstranit levou rekurzi.

M

KAPITOLA 4


68

1. Odstranı´me ε-pravidla (resp. jedine´, B → ε): G0 = ({S, A, B}, {a, b, c}, P 0 , S) S → bAa | c | A A → Ba | a | b | Abb B → aBb | ab | Bbc | bc | ca

2. Odstranı´me jednoduche´ pravidlo S → A: G00 = ({S, A, B}, {a, b, c}, P 00 , S) S → bAa | c | Ba | a | b | Abb A → Ba | a | b | Abb B → aBb | ab | Bbc | bc | ca

3. Odstranı´me prˇ´ımou levou rekurzi. Pravidla A → Ba | a | b | Abb nahradı´me pravidly A → BaA0 | aA0 | bA0 | Ba | a | b A0 → bbA0 | bb

Da´le pravidla B → aBb | ab | Bbc | bc | ca nahradı´me pravidly B → aBbB 0 | abB 0 | aB 0 | |bcB 0 | caB 0 | aBb | ab | bc | ca B 0 → bcB 0 | bc

Vytvorˇili jsme tuto gramatiku: = ({S, A, A0 , B, B 0 }, {a, b, c}, P 000 , S) S → bAa | c | Ba | a | b | Abb A → BaA0 | aA0 | bA0 | Ba | a | b A0 → bbA0 | bb B → aBbB 0 | abB 0 | aB 0 | |bcB 0 | caB 0 | aBb | ab | bc | ca B 0 → bcB 0 | bc G000

Prˇı´klad 4.14 Odstranı´me prˇ´ımou pravou rekurzi v te´to gramatice: G = ({S, A, B}, {a, b, c}, P, S) S → aAb | AB A → abA | c | Sc B → bbB | cB | a Jde o vlastnı´ gramatiku, nemusı´me ji prˇedem do tohoto tvaru upravovat. Postupujeme stejneˇ jako u odstraneˇnı´ leve´ rekurze, jen zameˇnı´me levou a pravou stranu. Prˇida´me nove´ netermina´ly a upravı´me pravidla. Z netermina´lu A mu˚zˇe by´t naprˇ´ıklad tato derivace: A ⇒ abA ⇒ ababA ⇒∗ (ab)i A ⇒ (ab)i c Pravidla A → abA | c | Sc nahradı´me pravidly A → A0 c | A0 Sc | c | Sc A0 → A0 ab | ab

M

KAPITOLA 4


69

Derivace z netermina´lu A se zmeˇnı´: A ⇒ A0 c ⇒ A0 abc ⇒ A0 ababc ⇒∗ A0 (ab)i−1 c ⇒ (ab)i c Vygenerovany´ rˇeteˇzec je tenty´zˇ, ale zatı´mco u prave´ rekurze byl generovań zleva doprava, u leve´ rekurze je generovań opacˇneˇ – zprava doleva. Podobneˇ upravı´me pravidla B → bbB | cB | a: B → B0a | a B 0 → B 0 bb | B 0 c | bb | c Vycha´zı´ na´m tato gramatika: G0 = ({S, A, A0 , B, B 0 }, {a, b, c}, P 0 , S) S → aAb | AB A → A0 c | A0 Sc | c | Sc A0 → A0 ab | ab B → B0a | a B 0 → B 0 bb | B 0 c | bb | c Rekurze mu˚zˇe by´t take´ neprˇ´ıma´, naprˇ´ıklad v pravidlech A → Bba | a B → Aab | b Levou rekurzi, vcˇetneˇ neprˇ´ıme´, odstranı´me tak, zˇe pravidla prˇevedeme do tvaru, kdy prava´ strana pravidla zacˇ´ına´ netermina´lem pouze za prˇesneˇ urcˇenyćh okolnostı´. Postup: 1. Stanovı´me porˇadı´ netermina´lu˚. Mu˚zˇeme si je naprˇ´ıklad oznacˇit indexy, prˇejmenovat nebo ´ cˇelem algoritmu jednodusˇe urcˇit jejich porˇadı´. Necht’porˇadı´ netermina´lu˚ je (A1 , A2 , . . . , An ). U je upravit pravidla tak, aby mohla zacˇ´ınat pouze netermina´ly s vysˇsˇ´ım indexem nezˇ je index prˇepisovane´ho netermina´lu. Tı´m zcela odstranı´me levou rekurzi. 2. Pro netermina´ly Ai , Aj , 1 ≤ i, j ≤ n postupneˇ transformujeme pravidla. Pro prvnı´ krok stanovı´me i = 1, j = 1. • Pokud j < i a existuje pravidlo Ai → Aj α, kde α je jaky´koliv rˇeteˇzec (tj. pravidlo pro Ai zacˇ´ına´ netermina´lem Aj ), pak symbol Aj v pravidle nahradı´me postupneˇ vsˇemi pravy´mi stranami pravidel pro Aj , naprˇ´ıklad Ai → Aj abB Aj → bDAi a | CAj a

Prvnı´ z uvedenenyćh pravidel nahradı´me pravidly Ai → bdAi aabB | CAj aabB. Provedeme j = j + 1.

• Pokud j = i, pak odstranı´me prˇ´ımou levou rekurzi podle postupu, ktery´ uzˇ zna´me. Provedeme j = j + 1. • Pokud j > i, provedeme i = i + 1, j = 1. 3. Bod 2 postupu provedeme pro vsˇechna i, 1 ≤ i ≤ n. Aby byl postup pouzˇitelny´, musı´ by´t uplatneˇn pouze na vlastnı´ gramatiku. Postup pro pravou rekurzi je obdobny´, jen zameˇnı´me levou za pravou stranu.

KAPITOLA 4


70

Prˇı´klad 4.15 Odstranı´me levou rekurzi v na´sledujıćı´ gramatice: G = ({S, A, B}, {a, b, c}, P, S) S → aA | AB | b A → SBa | a B → Bb | Aa | c Prˇ´ıma´ leva´ rekurze je zde jen v jednom pravidle, ale neprˇ´ıma´ rekurze se ty´ka´ vıće pravidel. Gramatika je vlastnı´, nenı´ trˇeba ji do tohoto tvaru upravovat. Stanovı´me porˇadı´ netermina´lu˚: (A1 , A2 , A3 ) = (S, A, B). • i = 1, j = 1 : nenı´ trˇeba upravovat, pravidla pro S neobsahujı´ prˇ´ımou rekurzi. • i = 2, j = 1 : jedno z pravidel pro A zacˇ´ına´ netermina´lem s „nizˇsˇ´ım indexem“, S; upravı´me: A → aABa | ABBa | bBa | a

• i = 2, j = 2 : rˇesˇ´ıme prˇ´ımou rekurzi (protozˇe i = j): A → aABaA0 | bBaA0 | aA0 | aABa | bBa | a A0 → BBaA0 | BBa

• i = 3, j = 1 : zˇa´dne´ z pravidel pro B nezacˇ´ına´ symbolem S • i = 3, j = 2 : zmeˇna se ty´ka´ druhe´ho pravidla pro symbol B (zacˇ´ına´ symbolem A, jehozˇ index je 2). Prˇi nahrazenı´ symbolu A v tomto pravidle pouzˇijeme jizˇ upravena´ pravidla pro A: B → Bb | aABaA0 a | bBaA0 a | aA0 a | aABaa | bBaa | aa | c

• i = 3, j = 3 : odstranı´me prˇ´ımou rekurzi:

B → aABaA0 aB 0 | bBaA0 aB 0 | aA0 aB 0 | aABaaB 0 | bBaaB 0 | aaB 0 | cB 0 | aABaA0 a | bBaA0 a | aA0 a | aABaa | bBaa | aa | c 0 B → bB 0 | b Cela´ gramatika bez leve´ rekurze: G0 = ({S, A, A0 , B, B 0 }, {a, b, c}, P 0 , S) S → aA | AB | b A → aABaA0 | bBaA0 | aA0 | aABa | bBa | a A0 → BBaA0 | BBa B → aABaA0 aB 0 | bBaA0 aB 0 | aA0 aB 0 | aABaaB 0 | bBaaB 0 | aaB 0 | cB 0 | aABaA0 a | bBaA0 a | aA0 a | aABaa | bBaa | aa | c 0 B → bB 0 | b

M

KAPITOLA 4


71

Odstraneˇnı´m prˇ´ıme´ rekurze rozsˇirˇujeme mnozˇinu netermina´lu˚, proto je nutne´ dynamicky upravovat take´ nadefinovanou posloupnost netermina´lu˚ urcˇujıćı´ porˇadı´. Netermina´ly s pravidly, ktere´ takto vytvorˇ´ıme, je trˇeba zahrnout do algoritmu. Prˇı´klad 4.16 Odstranı´me levou rekurzi v na´sledujıćı´ gramatice: G = ({S, A, B}, {a, b}, P, S) S → aA | bB A → BaA | ab B → BaA | b

M

Postupujeme podle algoritmu. Stanovı´me porˇadı´ netermina´lu˚ na (S, A, B). Da´le: • i = 1, j = 1 : nenı´ trˇeba upravovat, pravidla pro S neobsahujı´ prˇ´ımou rekurzi.

• i = 2, j = 1, 2 : nenı´ trˇeba upravovat, pravidla pro A nezacˇ´ınajı´ symboly S a A.

• i = 3, j = 1, 2 : nenı´ trˇeba upravovat, pravidla pro B nezacˇ´ınajı´ symboly S a A. • i = 3, j = 3 : odstranı´me prˇ´ımou rekurzi. B → bB 0 | b B 0 → AaB 0 | Aa

Meˇnı´me posloupnost: (A1 , A2 , A3 , A4 ) = (S, A, B, B 0 ) • i = 4, j = 1 : nenı´ trˇeba upravovat, pravidla pro B 0 nezacˇ´ınajı´ symbolem S. • i = 4, j = 2 :

B 0 → BaAaB 0 | abaB 0 | BaAa | aba

• i = 4, j = 3 :

B 0 → bB 0 aAaB 0 | baAaB 0 | abaB 0 | bB 0 aAa | baAa | aba

• i = 4, j = 4 : nenı´ trˇeba upravovat.

Vy´sledna´ gramatika: G0 = ({S, A, B, B 0 }, {a, b}, P 0 , S) S → aA | bB A → BaA | ab B → bB 0 | b B 0 → AaB 0 | Aa B 0 → bB 0 aAaB 0 | baAaB 0 | abaB 0 | bB 0 aAa | baAa | aba

´ koly U 1. Odstranˇte levou rekurzi v teˇchto gramatikaćh (zvazˇte, zda nenı´ trˇeba gramatiku prˇedem upravit):

C

KAPITOLA 4


72

G1 = ({S, A, B}, {a, b, c}, P, S)

G2 = ({S, A, B}, {a, b}, P, S)

S → aAB | b | SB | ε A → bA | Aac | AB | a B → BbA | c

S → AB | BA A → ABbA | bA | ε B → SA | a | BbA

2. Odstranˇte pravou rekurzi v teˇchto gramatikaćh (prˇ´ıp. gramatiku prˇedem upravte): G1 = ({S, A, B}, {0, 1}, P, S)

G2 = ({S, A, B}, {a, b}, P, S)

S → 11A | 01B | ε A → 11A | B01 | 10 B → 01B | 00AB | 1A1 | 01

S → aAb | abB | ASA A → bA | B | ε B → bbB | abAB | abb

Kapitola

5

Za´sobnı´kovy´ automat 5.1

Co je to za´sobnı´kovy´ automat

Konecˇne´ automaty jsou uzˇitecˇne´ (to zjistı´me prˇedevsˇ´ım v prˇedmeˇtu Prˇekladacˇe, kdy se naucˇ´ıme pouzˇ´ıvat stavove´ programovańı´), nicmeńeˇ nejsou zdaleka vsˇemocne´. Na neˇktere´ u´koly nestacˇ´ı, proto potrˇebujeme i slozˇiteˇjsˇ´ı formy automatu˚/stroju˚. O neˇco slozˇiteˇjsˇ´ı nezˇ konecˇny´ automat je automat za´sobnı´kovy´.

5.1.1

Definice

Za´sobnı´kovy´ automat dostaneme tak, zˇe • konecˇny´ automat obohatı´me o za´sobnı´kovou pa´sku,

• zajistı´me, aby vy´pocˇet byl rˇ´ızen prˇedevsˇ´ım podle te´to za´sobnı´kove´ pa´sky, • netrva´me na tom, aby byl v kazˇde´m kroku cˇten vstup.

Za´sobnı´kovy´ automat je usporˇa´dana´ sedmice A = (Q, Σ, Γ, δ, q0 , Z0 , F ), kde • Q je konecˇna´ nepra´zdna´ mnozˇina stavu˚, • Σ je konecˇna´ nepra´zdna´ abeceda,

• Γ je konecˇna´ nepra´zdna´ za´sobnı´kova´ abeceda, • δ je prˇechodova´ funkce definovana´ nı´zˇe, • q0 je pocˇa´tecˇnı´ stav automatu, q0 ∈ Q,

• Z0 je pocˇa´tecˇnı´ za´sobnı´kovy´ symbol, Z0 ∈ Γ,

• F je mnozˇina koncovyćh stavu˚, F ⊆ Q (mu˚zˇe by´t i pra´zdna´).

Prˇechodova´ funkce δ, ktera´ popisuje cˇinnost automatu, je zobrazenı´ δ : Q × (Σ ∪ {ε}) × Γ −→ Q × Γ∗ . To mu˚zˇeme take´ zapsat jako δ(qi , a, Z) 3 (qj , γ), qi , qj ∈ Q, a ∈ (Σ ∪ {ε}), Z ∈ Γ, γ ∈ Γ∗ Konfigurace vy´sˇe definovane´ho za´sobnı´kove´ho automatu A je Q × Σ∗ × Γ∗ , take´ mu˚zˇeme zapsat ve tvaru (q, α, γ), q ∈ Q, α ∈ Σ∗ , γ ∈ Γ∗ . 73

P

KAPITOLA 5

ZA´SOBNI´KOVY´ AUTOMAT

74

Pocˇa´tecˇnı´ konfigurace je (q0 , w, Z0 ), kde w je slovo, ktere´ bylo dańo na vstup automatu. Koncova´ konfigurace za´visı´ na typu za´sobnı´kove´ho automatu. Prˇechod mezi konfiguracemi za´sobnı´kove´ho automatu je relace (qi , aα, Zβ) ` (qj , α, γβ)

⇐⇒

(qj , β) ∈ δ(qi , a, Z)

kde a ∈ (Σ ∪ {ε}), Z ∈ (Γ ∪ {ε}), α ∈ Σ∗ . Za´sobnı´kovy´ automat pracuje takto: 1. vyjme symbol na vrcholu za´sobnı´ku, 2. mu˚zˇe/nemusı´ prˇecˇ´ıst jeden symbol ze vstupnı´ pa´sky, pokud prˇecˇte, posune se o polıćˇko da´l, 3. da´le se rozhoduje podle • sve´ho vnitrˇnı´ho stavu, • symbolu, ktery´ vyndal ze za´sobnı´ku, • pokud cˇetl ze vstupnı´ pa´sky, pak i podle prˇecˇtene´ho symbolu,

4. akce automatu spocˇ´ıva´ v

• prˇechodu do neˇktere´ho dalsˇ´ıho stavu • a v ulozˇenı´ rˇeteˇzce znaku˚ do za´sobnı´ku.

5.1.2

Typy za´sobnı´kovyćh automatu˚

Rozezna´va´me tyto za´kladnı´ typy za´sobnı´kovyćh automatu˚: 1. za´sobnı´kovy´ automat koncˇ´ıcı´ prˇechodem do koncove´ho stavu, 2. za´sobnı´kovy´ automat koncˇ´ıcı´ pra´zdny´m za´sobnı´kem. Existuje take´ jejich kombinace – za´sobnı´kovy´ automat koncˇ´ıcı´ prˇechodem do koncove´ho stavu prˇi pra´zdne´m za´sobnı´ku. Za´sobnı´kovy´ automat koncˇıćı´ prˇechodem do koncove´ho stavu znacˇ´ıme AF . Jeho koncova´ konfigurace ma´ tento tvar: (qf , ε, γ), qf ∈ F, γ ∈ Γ∗

P

Rozpozna´vany´ jazyk je L(AF ) = {w ∈ Σ∗ ; (q0 , w, Z0 ) ` ∗ (qf , ε, γ), qf ∈ F, γ ∈ Γ∗ } To znamena´, zˇe abychom mohli skoncˇit, musı´me prˇecˇ´ıst cely´ vstup a dostat se do neˇktere´ho koncove´ho stavu. Mnozˇina koncovyćh stavu˚ zde neby´va´ pra´zdna´ (kdyby byla, automat by rozpozna´val pra´zdny´ jazyk). Za´sobnı´kovy´ automat koncˇıćı´ s pra´zdny´m za´sobnı´kem znacˇ´ıme A∅ . Koncova´ konfigurace vypada´ na´sledovneˇ: (q, ε, ε), q ∈ Q

P

KAPITOLA 5


75

Rozpozna´vany´ jazyk je L(A∅ ) = {w ∈ Σ∗ ; (q0 , w, Z0 ) ` ∗ (q, ε, ε), q ∈ Q} Abychom mohli skoncˇit, musı´me prˇecˇ´ıst cely´ vstup a vypra´zdnit za´sobnı´k. Koncove´ stavy nepotrˇebujeme, proto je mnozˇina koncovyćh stavu˚ obvykle pra´zdna´. Za´sobnı´kovy´ automat koncˇıćı´ prˇechodem do koncove´ho stavu prˇi pra´zdne´m za´sobnı´ku znacˇ´ıme AF,∅ . Jeho koncova´ konfigurace je (qf , ε, ε), qf ∈ F

P

Rozpozna´vany´ jazyk je L(AF,∅ ) = {w ∈ Σ∗ ; (q0 , w, Z0 ) ` ∗ (qf , ε, ε), qf ∈ F } Je trˇeba splnit podmıńky obou prˇedchozıćh typu˚ za´rovenˇ – abychom mohli skoncˇit vy´pocˇet (u´speˇsˇneˇ), je trˇeba prˇecˇ´ıst cely´ vstup, vypra´zdnit za´sobnı´k a navıć by´t v koncove´m stavu. Vsˇechny trˇi typy za´sobnı´kovyćh automatu˚ koncˇ´ı samozrˇejmeˇ vy´pocˇet i tehdy, kdyzˇ nejsou v zˇa´dne´ koncove´ konfiguraci, ale do zˇa´dne´ dalsˇ´ı se nemohou dostat (prˇechodova´ funkce neda´va´ mozˇnost reagovat v dane´m stavu s dany´m obsahem za´sobnı´ku a vstupnı´ pa´sky). V tomto prˇ´ıpadeˇ vsˇak koncˇ´ıme s tı´m, zˇe zpracova´vane´ slovo nepatrˇ´ı do jazyka rozpozna´vane´ho automatem. Prˇı´klad 5.1 Sestrojı´me za´sobnı´kovy´ automat (da´le ZA) koncˇ´ıcı´ s pra´zdny´m za´sobnı´kem rozpozna´vajıćı´ jazyk L=

n

wcwR

; w∈

{a, b}∗

o

Vytvorˇ´ıme za´sobnı´kovy´ automat rozpozna´vajıćı´ pra´zdny´m za´sobnı´kem. To znamena´, zˇe koncˇit budeme tehdy, kdyzˇ cely´ vstup bude prˇecˇteny´ a cely´ za´sobnı´k bude vypra´zneˇny´ (vcˇetneˇ symbolu konce za´sobnı´ku Z0 ). Mnozˇina koncovyćh stavu˚ bude pra´zdna´, protozˇe zˇa´dny´ koncovy´ stav nepotrˇebujeme. Automat bude pracovat takto: • v prvnı´ fa´zi bude cˇ´ıst obsah vstupu (prvnı´ polovina slova) a ukla´dat do za´sobnı´ku (vzˇdy co v kazˇde´m kroku vyjmeme, vra´tı´me do za´sobnı´ku za´rovenˇ se symbolem ze vstupu, tedy ukla´da´me dva symboly), jsme ve stavu q0 , • dı´ky principu za´sobnı´ku (cˇteme v opacˇne´m porˇadı´, nezˇ jak byly symboly ulozˇeny) je ukla´dana´ prvnı´ polovina slova za´rovenˇ zrcadloveˇ prˇevraćena, • kdyzˇ na vstupu narazı´me na c (hranice, polovina slova), prˇejdeme do stavu q1 a tı´m zmeˇnı´me zpu˚sob praće automatu, • kdyzˇ jsme ve stavu q1 , nic do za´sobnı´ku neukla´da´me, symbol, ktery´ v kazˇde´m kroku vyjmeme, porovna´me s tı´m, co je na vstupu – kdyzˇ souhlası´, mu˚zˇeme pokracˇovat (tj. v kazˇde´m kroku se posuneme na vstupu a za´rovenˇ ubereme symbol ze za´sobnı´ku). Na´sleduje na´kres s obsahem za´sobnı´ku, vstupu a stavem v jednotlivyćh krocıćh vy´pocˇtu:

M

KAPITOLA 5

ZA´SOBNI´KOVY´ AUTOMAT Prˇed prvnı´m krokem:

q0 →

Z0

Prˇed druhy´m krokem:

q0 →

a Z0

vstup: aabcbaa

vstup: abcbaa

Prˇed pa´ty´m krokem:

Prˇed sˇesty´m krokem:

q1 →

b a a Z0

vstup: baa

q1 →

a a Z0

76 Prˇed trˇetı´m krokem:

q0 →

a a Z0

vstup: bcbaa Prˇed sedmy´m krokem:

q1 →

vstup: aa

a Z0

vstup: a

Prˇed cˇtvrty´m krokem:

q0 →

b a a Z0

vstup: cbaa Prˇed osmy´m krokem:

q1 →

Z0

vstup: ε

Po osme´m kroku:

q2 → vstup: ε

V plne´ specifikaci uvedeme stavy, abecedu, za´sobnı´kovou abecedu, pocˇa´tecˇnı´ stav, symbol konce za´sobnı´ku, δ-funkci a mnozˇinu koncovyćh stavu˚ (zde pra´zdnou), da´le uprˇesnı´me prˇedpis δ-funkce: A∅ = ({q0 , q1 }, {a, b}, {a, b, Z0 }, q0 , Z0 , δ, ∅) δ(q0 , a, Z0 ) = (q0 , aZ0 ) δ(q0 , b, Z0 ) = (q0 , bZ0 ) δ(q0 , a, X) = (q0 , aX), X ∈ {a, b} δ(q0 , c, X) = (q1 , X), X ∈ {a, b} δ(q1 , a, a) = (q1 , ε) δ(q1 , b, b) = (q1 , ε) δ(q1 , ε, Z0 ) = (q1 , ε)

na zacˇa´tku vy´pocˇtu, slovo zacˇ´ına´ a na zacˇa´tku vy´pocˇtu, slovo zacˇ´ına´ b zatı´m jen nacˇ´ıta´me a ukla´da´me do za´sobnı´ku jsme na hranici shoda a v obou polovinaćh slova shoda b v obou polovinaćh slova skoncˇili jsme na vstupu i v za´sobnı´ku

Uka´zka vy´pocˇtu automatu na slovo abcba: (q0 , abcba, Z0 ) ` (q0 , bcba, aZ0 ) ` ` (q0 , cba, baZ0 ) ` ` (q1 , ba, baZ0 ) ` (q1 , a, aZ0 ) ` ` (q1 , ε, Z0 ) ` (q1 , ε, ε)

q0 : prˇena´sˇ´ıme do za´sobnı´ku obsah vstupu hranicˇnı´ bod, prˇejdeme do mo´du q1 q1 : jen vybı´ra´me ze za´sobnı´ku a porovna´va´me konec

Za´sobnı´kovy´ automat koncˇ´ıcı´ v koncove´m stavu (a vlastneˇ i „hybridnı´“ typ) bychom z prˇedesˇle´ho vytvorˇili jednodusˇe – stacˇ´ı poslednı´ cˇa´st definice δ funkce prˇepsat takto: δ(q1 , ε, Z0 ) = (q2 , ε) s tı´m, zˇe Q = {q0 , q1 , q2 }, F = {q2 }. Prˇı´klad 5.2 Vytvorˇ´ıme za´sobnı´kovy´ automat koncˇ´ıcı´ v koncove´m stavu reprezentovany´ stavovy´m diagramem pro jazyk z prˇ´ıkladu 5.1 o n L = wcwR ; w ∈ {a, b}∗ .

L M

KAPITOLA 5


77

Narozdı´l od konecˇnyćh automatu˚, u za´sobnı´kovyćh na´m nestacˇ´ı ohodnotit sˇipky pouze symbolem nacˇ´ıtany´m ze vstupnı´ pa´sky. Musı´me vzˇdy zadat trˇi u´daje (ve spra´vne´m porˇadı´!) • symbol nacˇteny´ ze vstupu (nebo ε, kdyzˇ ze vstupu nic nenacˇ´ıta´me),

• symbol, ktery´ vyjı´ma´me ze za´sobnı´ku (nesmı´ zde by´t ε!, v kazˇde´m kroku musı´me neˇjaky´ symbol vyndat), • rˇeteˇzec, ktery´ ukla´da´me do za´sobnı´ku. Diagram vytvorˇ´ıme podle δ funkce v prˇ´ıkladu 5.1, jen navıć zakomponujeme zmeˇnu zahrnutou v pozna´mce nad tı´mto prˇ´ıkladem. Vy´sledny´ diagram vidı´me na obra´zku nı´zˇe. a, X, aX b, X, bX

c, X, X

q0

X ∈ {a, b, Z0 }

a, a, ε b, b, ε

ε, Z0 , ε

q1

q2

U konecˇnyćh automatu˚ byl diagram jesˇteˇ celkem pouzˇitelny´, ale u za´sobnı´kovyćh automatu˚ ho jizˇ nepouzˇ´ıva´me (ve slozˇiteˇjsˇ´ıch prˇ´ıpadech je naprosto neprˇehledny´). Typicky pouzˇ´ıva´me za´pis pomocı´ δ-funkce. ´ koly U 1. Podle postupu˚ v prˇn edchozıćh prˇ´ıkladecho sestrojte δ-funkci automatu koncˇ´ıcı´ho v koncove´m stavu pro jazyk L = wcwR ; w ∈ {a, b}∗ .

L C

2. Sestrojte za´sobnı´kovy´ automat pro jazyk L = {an bn ; n ≥ 1}.

Na´poveˇda: prvnı´ polovinu slova (stav q0 ) cˇteˇte a prˇitom ukla´dejte do za´sobnı´ku, v prˇ´ıpadeˇ druhe´ poloviny slova (stav q1 , tam prˇejdeme, kdyzˇ narazı´me na prvnı´ b) ze za´sobnı´ku vybı´rejte ulozˇene´ symboly a jejich pocˇet srovna´vejte s cˇteny´mi symboly b (za kazˇde´ a v za´sobnı´ku musı´ by´t jedno b na vstupu). Pozor na ukoncˇenı´ – vyzkousˇejte, zda automat spolehliveˇ funguje (musı´ prˇijmout naprˇ´ıklad slova ab a aabb, ale odmı´tnout pra´zdne´ slovo).

5.2

Vytva´rˇı´me za´sobnı´kovy´ automat

Prˇi konstrukci za´sobnı´kove´ho automatu si prˇedevsˇ´ım musı´me promyslet, jaky´m zpu˚sobem bude ve ktere´m kroku zacha´zeno se za´sobnı´kem. Prˇı´klad 5.3 Sestrojı´me za´sobnı´kovy´ automat rozpozna´vajıćı´ jazyk L = {an b2n ; n ≥ 0} Mu˚zˇeme postupovat podobneˇ, jak bylo doporucˇeno v prˇedchozı´m u´kolu. Ale pozor – pocˇet symbolu˚ b je dvojna´sobny´. Aby na´m „nenadby´valy“ symboly na vstupu, zvolı´me δ-funkci na´sledovneˇ:

M

KAPITOLA 5


78

• stav q0 : pokud je na vstupu a (a v za´sobnı´ku cokoliv), ulozˇ´ıme do za´sobnı´ku pu˚vodnı´ vyjmuty´ symbol a da´le dva symboly a (tj. rˇeteˇzec aa), • stav q0 : pokud je na vstupu b (na vrcholu za´sobnı´ku musı´ by´t a, protozˇe jinak by slovo nepatrˇilo do rozpozna´vane´ho jazyka), symbol a jizˇ do za´sobnı´ku nebudeme vracet, „spa´rujeme“ ho s prˇecˇteny´m symbolem b, prˇejdeme do stavu q1 , • stav q1 : pokud je na vstupu b (na vrcholu za´sobnı´ku musı´ by´t a), reagujeme stejneˇ jako v prˇedchozı´m prˇ´ıpadeˇ, • koncˇ´ıme s pra´zdny´m za´sobnı´kem, do jazyka patrˇ´ı i pra´zdne´ slovo. Prˇed prvnı´m krokem:

Prˇed druhy´m krokem:

Prˇed trˇetı´m krokem:

q0 → q0 → q0 →

Z0

vstup: a2 b4 Prˇed pa´ty´m krokem:

q1 →

vstup: ab4 Prˇed sˇesty´m krokem:

a a Z0

vstup: b

a a Z0

q1 → 2

a Z0

vstup: b

a a a a Z0

Prˇed cˇtvrty´m krokem:

q1 →

vstup: b4 Prˇed sedmy´m krokem:

q1 →

Z0

a a a Z0

vstup: b3 Po sedme´m kroku:

q2 →

vstup: ε

vstup: ε

A = ({q0 , q1 }, {a, b}, {Z0 , a}, δ, q0 , Z0 , ∅) δ(q0 , a, Z0 ) = (q0 , aaZ0 ) δ(q0 , a, a) = (q0 , aaa) δ(q0 , b, a) = (q1 , ε) δ(q1 , b, a) = (q1 , ε) δ(q0 , ε, Z0 ) = (q0 , ε) δ(q1 , ε, Z0 ) = (q1 , ε) Poslednı´ dva prˇedpisy prˇechodove´ funkce urcˇujı´ chovańı´ vedoucı´ k ukoncˇenı´ vy´pocˇtu. V okamzˇiku, kdy ze za´sobnı´ku vyjmeme Z0 (za ktery´m uzˇ zˇa´dny´ symbol by´t nemu˚zˇe), nelze da´l pokracˇovat, protozˇe v kazˇde´m kroku vy´pocˇtu je nutno vyjmout symbol ze za´sobnı´ku (nenı´ co vyjmout). Podle sestrojene´ho automatu zpracujeme neˇkolik slov (to bychom meˇli vzˇdy udeˇlat, abychom meˇli jistotu, zˇe automat pracuje spra´vneˇ): (q0 , aabbbb, Z0 ) ` (q0 , abbbb, aaZ0 ) ` (q0 , bbbb, aaaaZ0 ) ` (q1 , bbb, aaaZ0 ) ` (q1 , bb, aaZ0 ) ` ` (q1 , b, aZ0 ) ` (q1 , ε, Z0 ) ` (q1 , ε, ε) (q0 , abb, Z0 ) ` (q0 , bb, aaZ0 ) ` (q1 , b, aZ0 ) ` (q1 , ε, Z0 ) ` (q1 , ε, ε)

KAPITOLA 5


79

(q0 , ε, Z0 ) ` (q0 , ε, ε)

(q0 , ab, Z0 ) ` (q0 , b, aaZ0 ) ` (q1 , ε, aZ0 ) konec, slovo ab ∈ / L, tato konfigurace nenı´ koncova´

(q0 , abbb, Z0 ) ` (q0 , bbb, aaZ0 ) ` (q1 , bb, aZ0 ) ` (q1 , b, Z0 ) ` (q1 , b, ε) opeˇt nejde o koncovou konfiguraci, proto abbb ∈ / L (vsˇimneˇte si poslednı´ho provedene´ho kroku odvozenı´)

´ koly U 1. Sestrojte za´sobnı´kovy´ automat rozpozna´vajıćı´ jazyk

C

L = {an bn ck ; n, k ≥ 1}. Na´poveˇda: slova se skla´dajı´ ze trˇ´ı cˇa´stı´. Prvnı´ dveˇ cˇa´sti musejı´ by´t stejneˇ dlouhe´, tedy pro neˇ musı´me pouzˇ´ıt synchronizaci za´sobnı´kem (stav q0 : symboly a cˇteme a ukla´da´me do za´sobnı´ku, stav q1 : symboly b cˇteme a srovna´va´me se za´sobnı´kem, stav q2 : uzˇ za´sobnı´k nepotrˇebujeme, jen cˇteme symboly c tak dlouho, dokud jsou na vstupu). Nezapomenˇte oveˇrˇit, zda automat prˇijı´ma´ slova abc, a2 b2 c, abc2 (to jen pro kontrolu), a jestli neprˇijı´ma´ slova ε, a, ab, b, c, ac (ta nepatrˇ´ı do jazyka rozpozna´vane´ho automatem). 2. Sestrojte za´sobnı´kovy´ automat rozpozna´vajıćı´ jazyk L = {an bk cn ; n, k ≥ 0}.

3. Sestrojte za´sobnı´kovy´ automat rozpozna´vajıćı´ jazyk L = {(01)n (10)n ; n ≥ 0}.

4. Sestrojte za´sobnı´kovy´ automat rozpozna´vajıćı´ jazyk L = {0n 1n+3 ; n ≥ 0}. Pozor, budeme potrˇebovat dostatek stavu˚. Oveˇrˇte, zda automat na´hodou neprˇijı´ma´ i ta slova, ktera´ nepatrˇ´ı do jazyka L. 5. Sestrojte za´sobnı´kovy´ automat rozpozna´vajıćı´ jazyk L = {an bn cak bk ; n ≥ 0, k ≥ 1}.

5.3

Nedeterminismus

Jaky´ je rozdı´l mezi deterministicky´m a nedeterministicky´m za´sobnı´kovy´m automatem? Deterministicky´ v kazˇde´m roku reaguje jednoznacˇneˇ. Narozdı´l od konecˇne´ho automatu se to trochu hu˚rˇe pozna´ v krocıćh, ve kteryćh automat necˇte ze vstupu. Podı´vejme se na automaty, ktere´ jsme zkonstruovali v prˇ´ıkladech v te´to kapitole. Prˇı´klad 5.4 Automat v prˇ´ıkladu 5.1 je deterministicky´, protozˇe v kazˇde´m kroku doka´zˇeme reagovat zcela jednoznacˇneˇ. Jedna´ se o deterministicky´ za´sobnı´kovy´ automat. Podobneˇ i v na´sledujıćı´m prˇ´ıkladeˇ. Pokud

M

KAPITOLA 5


80

doka´zˇeme pro jazyk zkonstruovat deterministicky´ automat, vı´me, zˇe ten jazyk je deterministicky´. Protonjazyk o L = wcwR ; w ∈ {a, b}∗ je deterministicky´ bezkontextovy´ jazyk.

Prˇı´klad 5.5 Za´sobnı´kovy´ automat z prˇ´ıkladu 5.3 naproti tomu deterministicky´ nenı´. Procˇ? Podı´vejme se na tyto dva rˇa´dky prˇedpisu δ-funkce: δ(q0 , a, Z0 ) = (q0 , aaZ0 ) δ(q0 , ε, Z0 ) = (q0 , ε) V obou prˇ´ıpadech reagujeme ve stavu q0 a ze za´sobnı´ku jsme vyta´hli symbol Z0 . V prvnı´m prˇ´ıpadeˇ sice cˇteme ze vstupu symbol a a v druhe´m prˇ´ıpadeˇ vstup necˇteme („nevsˇ´ıma´me“ si ho), ale musı´me si uveˇdomit, zˇe v zˇa´dne´m kroku vlastneˇ nejsme nuceni cˇ´ıst vstup. Takzˇe naprˇ´ıklad v konfiguraci (q0 , abb, Z0 ) jsou ve skutecˇnosti dveˇ mozˇnosti jak reagovat: (q0 , abb, Z0 ) ` (q0 , bb, aZ0 ) (q0 , abb, Z0 ) ` (q0 , abb, ε) Druha´ mozˇnost sice nevede ke koncove´ konfiguraci (vlastneˇ ani na´sledujıćı´ krok jizˇ nenı´ mozˇne´ prove´st), ale to u nedeterministicke´ho automatu nehraje roli, je du˚lezˇite´, zˇe dany´ krok lze prove´st. Z toho vyply´va´, zˇe tento automat je nedeterministicky´. Kdyby bylo mozˇne´ pro dany´ jazyk sestrojit alesponˇ jeden deterministicky´ automat, byl by tento jazyk deterministicky´, ale to nelze (procˇ?). Proto mu˚zˇeme rˇ´ıct, zˇe jazyk L = {an b2n ; n ≥ 0} je nedeterministicky´ bezkontextovy´ jazyk.

´ koly U n

o

1. Jazyk L = wwR ; w ∈ {a, b}∗ nenı´ deterministicky´. Sestrojte za´sobnı´kovy´ automat, ktery´ ho rozpozna´va´, a zdu˚vodneˇte, procˇ nenı´ deterministicky´. Na´poveˇda: v prˇ´ıkladu 5.1 je automat pro podobny´ jazyk, jen chybı´ „hranicˇnı´“ symbol c. Do stavu q1 tedy musı´me prˇejı´t neˇkde na hranici, kterou ale nedoka´zˇeme detekovat jednoznacˇneˇ. Rozhodneˇ to bude v mı´steˇ, kde na vstupu cˇteme tenty´zˇ symbol jako je ten, ktery´ jsme vyndali ze za´sobnı´ku, v teˇchto prˇ´ıpadech se tedy musı´ automat ve stavu q0 chovat nedeterministicky. 2. Ukazˇte, zˇe jazyk L = {an b2n ; n ≥ 1} je deterministicky´ bezkontextovy´ jazyk. Na´poveˇda: sestrojte za´sobnı´kovy´ automat a vsˇimneˇte si rozdı´lu oproti automatu z prˇ´ıkladu 5.3.

M

C

KAPITOLA 5

5.4


81

Za´sobnı´kovy´ automat podle bezkontextove´ gramatiky

Mezi za´sobnı´kovy´mi automaty a bezkontextovy´mi gramatikami existuje podobny´ vztah jako mezi konecˇny´mi automaty a regula´rnı´mi gramatikami. Existuje algoritmus, jak podle bezkontextove´ gramatiky sestrojit ekvivalentnı´ za´sobnı´kovy´ automat (ten si za chvı´li uka´zˇeme) a naopak jak podle za´sobnı´kove´ho automatu sestrojit bezkontextovou gramatiku (ten je slozˇiteˇjsˇ´ı, necha´me si ho na dalsˇ´ı semestr). Postup bude zalozˇen na u´plneˇ jine´m principu nezˇ u regula´rnıćh jazyku˚. Cokoliv se bude dı´t, to se bude dı´t na za´sobnı´ku. Budeme potrˇebovat jen jediny´ stav (resp. stav pro na´s nebude prˇedstavovat zˇa´dnou relevantnı´ informaci, ten jeden ma´me jen proto, zˇe neˇjaky´ stav by´t musı´). Podle zadane´ gramatiky sestrojı´me za´sobnı´kovy´ automat koncˇ´ıcı´ pra´zdny´m za´sobnı´kem. Postupujeme takto: • jediny´ stav q, je za´rovenˇ pocˇa´tecˇnı´,

P

• abecedu automatu vezmeme z mnozˇiny termina´lnıćh symbolu˚,

• za´sobnı´kovou abecedu utvorˇ´ıme z mnozˇin termina´lnıćh a netermina´lnıćh symbolu˚ (vsˇe se deˇje na za´sobnı´ku, tj. musı´me sem zarˇadit vsˇechny „stavebnı´ kameny“), • δ-funkci sestrojı´me prˇedevsˇ´ım podle pravidel, jak uvidı´me o neˇco da´le, • jako symbol konce za´sobnı´ku pouzˇijeme startovacı´ symbol gramatiky,

• mnozˇina koncovyćh stavu˚ bude pra´zdna´ (koncˇ´ıme pra´zdny´m za´sobnı´kem). Zby´va´ urcˇit δ-funkci. Jejı´ prˇedpis se bude skla´dat ze dvou cˇa´stı´: 1. prvnı´ cˇa´st sestrojı´me podle pravidel gramatiky, pouzˇijeme tehdy, kdyzˇ je na vrcholu za´sobnı´ku netermina´l: A→α

=⇒

δ(q, ε, A) 3 (q, α)

znamena´: pokud je na vrcholu za´sobnı´ku netermina´l A, nebudeme si vsˇ´ımat vstupu, vyjmeme A ze za´sobnı´ku a mı´sto neˇj tam da´me α (pravou stranu pravidla) 2. druha´ cˇa´st se pouzˇije tehdy, kdyzˇ bude na vrcholu za´sobnı´ku termina´lnı´ symbol: δ(q, a, a) = (q, ε) znamena´: pokud je na vrcholu za´sobnı´ku termina´l a a na vstupu bude tenty´zˇ termina´l, vyjmeme a ze za´sobnı´ku a nic tam uzˇ da´vat nebudeme. Prˇı´klad 5.6 Podle zadane´ gramatiky sestrojı´me za´sobnı´kovy´ automat: G = ({S, A, B}, {a, b, c}, P, S) S → abSba | A A → cAc | aB B → aB | ε

M

KAPITOLA 5


82

Pouzˇijeme jediny´ stav q, za´sobnı´kova´ abeceda bude obsahovat vsˇechny termina´ly a netermina´ly. Vy´sledny´ automat bude na´sledujıćı´: A = ({q}, {a, b, c}, {S, A, B, a, b, c}, δ, q, S, ∅) Prvnı´ cˇa´st – podle pravidel: δ(q, ε, S) = {(q, abSba), (q, A)} δ(q, ε, A) = {(q, cAc), (q, aB)} δ(q, ε, B) = {(q, aB), (q, ε)}

Druha´ cˇa´st – podle termina´lu˚: δ(q, a, a) = {(q, ε)} δ(q, b, b) = {(q, ε)} δ(q, c, c) = {(q, ε)}

V gramatice odvodı´me slovo a tote´zˇ slovo rozpozna´me ve vytvorˇene´m automatu: S ⇒ abSba ⇒ abAba ⇒ abaBba ⇒ abaaBba ⇒ abaaba

Ekvivalentnı´ zpracovańı´ (te´hozˇ) slova v automatu: (q, abaaba, S) ` (q, abaaba, abSba) ` (q, baaba, bSba) ` (q, aaba, Sba) ` (q, aaba, Aba) ` ` (q, aaba, aBba) ` (q, aba, Bba) ` (q, aba, aBba) ` (q, ba, Bba) ` (q, ba, ba) ` (q, a, a) ` (q, ε, ε)

Co se vlastneˇ deˇje v takto zkonstruovane´m automatu? Vsˇimneˇte si obsahu za´sobnı´ku, srovnejte ho s odvozenı´m slova v gramatice. Kdyzˇ si odmyslı´me manipulaci s termina´ly v za´sobnı´ku (zleva je „umaza´va´me“), je jasne´, zˇe vlastneˇ prova´dı´me simulaci. V za´sobnı´ku simulujeme odvozenı´ slova, a pokud se podarˇ´ı v simulaci dojı´t v za´sobnı´ku ke slovu, ktere´ jsme meˇli na vstupu (prˇesneˇji cele´ ho v za´sobnı´ku po odvozenı´ „zlikvidovat“), mu˚zˇeme tvrdit, zˇe slovo ze vstupu lze vygenerovat gramatikou, podle ktere´ byl automat sestrojen. ´ koly U 1. Podle odvozenı´ (derivace) na konci prˇ´ıkladu 5.6 sestrojte derivacˇnı´ strom. V tomto derivacˇnı´m stromeˇ sledujte, co se deˇje v souvislosti s rozpozna´vańı´m slova v ekvivalentnı´m automatu. Da´ se rˇ´ıct, zˇe automat procha´zı´ urcˇity´m zpu˚sobem tento derivacˇnı´ strom? 2. Sestrojte za´sobnı´kove´ automaty ekvivalentnı´ s teˇmito gramatikami: G1 = ({S}, {a, b}, P, S) S → aSa | bSb | c

G2 = ({S, A, B}, {a, b}, P, S) S → bAB | aBA | ε A → abAab | ε B → baBba | ε

L C

Teorie jazyků a automatů I

Recommend Documents