[161014-1204 ]
11
2.1.35 Konstrukce relace ∼. Postupnˇe konstruujeme na mnoˇzinˇe vˇsech stav˚ u Q relace ∼i , kde i = 0, 1, . . ., takto: • p ∼0 q pr´ avˇe tehdy, kdyˇz bud’ p, q ∈ F nebo p, q 6∈ F . • Dokud ∼i+1 6= ∼i konstruujeme p ∼i+1 q pr´ avˇe tehdy, kdyˇz p ∼i q a pro kaˇzd´e a ∈ Σ m´ame δ(p, a) ∼i δ(q, a). • Poloˇz´ıme ∼ := ∼i pro ∼i+1 = ∼i . Spr´ avnost tohoto postupu vyplyne z n´asleduj´ıc´ıch tvrzen´ı. 2.1.36
Tvrzen´ı. Plat´ı ∼0 ⊇ ∼ 1 ⊇ . . . ⊇ ∼ i ⊇ . . .
Existuje k takov´e, ˇze ∼k je rovna ∼k+1 . Pak pro kaˇzd´e j ≥ 1 plat´ı ∼k = ∼k+j a tedy ∼k = ∼. 2.1.37 Tvrzen´ı. Pro relace ∼i z 2.1.35 plat´ı p ∼i q pr´avˇe tehdy, kdyˇz pro kaˇzd´e slovo u d´elky menˇs´ı nebo rovn´e i plat´ı δ ? (p, u) ∈ F iff δ ? (q, u) ∈ F. 2.1.38 Pozn´ amka. Ekvivalence ∼i v praxi konstruujeme tak, ˇze konstruujeme odpov´ıdaj´ıc´ı rozklady Ri mnoˇziny stav˚ u Q na tˇr´ıdy ekvivalence ∼i . 2.1.39
Algoritmus redukce. Je d´an DFA M = (Q, Σ, δ, q0 , F ).
1. Zkonstruujeme mnoˇzinu Q0 vˇsech dosaˇziteln´ ych stav˚ u automatu M podle postupu 2.1.25. 2. Podle pˇredchoz´ıho odstavce zkonstruujeme rozklady Ri ekvivalenc´ı ∼i pro DFA M 0 = (Q0 , Σ, δ, q0 , F ∩ Q0 ). Konˇc´ıme tehdy, kdyˇz ∼i = ∼i+1 . Pak ∼ = ∼i . Oznaˇcme [q]∼ tˇr´ıdu ekvivalence ∼ obsahuj´ıc´ı stav q. 3. Vytvoˇr´ıme DFA M1 = (Q1 , Σ, δ1 , q1 , F1 ), kde • Q1 := {[q]∼ | q ∈ Q0 }, • q1 := [q0 ]∼ , • δ1 ([q]∼ , a) = [δ(q, a)]∼ , • F1 = {[q]∼ | F ∩ [q]∼ 6= ∅}. Slovnˇe m˚ uˇzeme automat M1 popsat takto: za stavy jsme vzali tˇr´ıdy ekvivalence ∼, poˇc´ateˇcn´ı stav je tˇr´ıda, ve kter´e leˇz´ı p˚ uvodn´ı poˇc´ ateˇcn´ı stav q0 , pˇrechodov´a funkce pracuje“ na tˇr´ıd´ach (coˇz je ” moˇzn´e vzhledem k vlastnosti ∼), a mnoˇzina koncov´ ych stav˚ u je mnoˇzina tˇech tˇr´ıd, ve kter´ ych leˇz´ı alespoˇ n jeden koncov´ y stav automatu M 0 . 2.1.40 Pˇ r´ıklad. K DFA automatu M , kter´ y je d´an n´asleduj´ıc´ı tabulkou, najdˇete redukovan´ y automat M1 . a b → 1 2 3 2 2 4 ← 3 3 5 4 2 7 ← 5 6 3 ← 6 6 6 7 7 4 8 2 3 ← 9 9 4 Marie Demlov´ a: Jazyky, automaty a gramatiky
Pˇred. 3: 17/10/2016
12
[161014-1204 ]
ˇ sen´ı. Nejprve najdeme vˇsechny dosaˇziteln´e stavy automatu M . Jsou to stavy {1, 2, 3, 4, 5, 6, 7}. Reˇ Tedy Q0 = {1, 2, 3, 4, 5, 6, 7}, F 0 = F = {3, 5, 6}. Automat M 0 je d´ an tabulkou: a b → 1 2 3 2 2 4 ← 3 3 5 4 2 7 ← 5 6 3 ← 6 6 6 7 7 4 Podle definice ekvivalence ∼0 je rozklad R0 tvoˇren dvˇema tˇr´ıdami: O = {1, 2, 4, 7}
F = {3, 5, 6}.
Plat´ı δ(1, a) = 2, δ(2, a) = 2, δ(4, a) = 2, δ(7, a) = 7, tj. vˇsechny v´ ysledky leˇz´ı ve tˇr´ıdˇe O. δ(1, b) = 3, δ(2, b) = 4, δ(4, b) = 7, δ(7, b) = 4, tj. δ(1, b) ∈ F a δ(2, b), δ(4, b), δ(7, b) ∈ O. Proto mus´ıme mnoˇzinu O rozdˇelit na dvˇe podmnoˇziny: {1} a {2, 4, 7}. D´ ale δ(3, a) = 3 ∈ F, δ(5, a) = 6 ∈ F, δ(6, a) = 6 ∈ F, δ(3, b) = 5 ∈ F, δ(5, b) = 3 ∈ F, δ(6, b) = 6 ∈ F. Proto mnoˇzinu F nedˇel´ıme. Rozklad odpov´ıdaj´ıc´ı ekvivalenci ∼1 je A = {1}, O = {2, 4, 7}, F = {3, 5, 6}. V´ ypoˇcet zahrneme do tabulky
→ ← ← ←
1 2 3 4 5 6 7
a 2 2 3 2 6 6 7
∼0 O O F O F F O
b 3 4 5 7 3 6 4
a O O F O F F O
b F O F O F F O
∼1 A O F O F F O
Analogicky vytv´ aˇr´ıme ekvivalence ∼2 . V´ ypoˇcet jiˇz zkr´at´ıme jen do tabulky.
→ 1 2 ← 3 4 ← 5 ← 6 7
a 2 2 3 2 6 6 7
b 3 4 5 7 3 6 4
∼0 O O F O F F O
a O O F O F F O
Marie Demlov´ a: Jazyky, automaty a gramatiky
b F O F O F F O
∼1 A O F O F F O
a O O F O F F O
b F O F O F F O
∼2 A O F O F F O Pˇred. 3: 17/10/2016
2.2. Nedeterministick´e koneˇcn´e automaty
[161014-1204 ]
13
Z tabulky vypl´ yv´ a, ˇze ∼1 = ∼2 . Proto ∼1 = ∼ je hledan´a ekvivalence. M´ame tedy tˇri tˇr´ıdy ekvivalence, a to A, O a F . Redukovan´ y automat M1 m´a tˇri stavy a je d´an tabulkou → ←
A O F
a O O F
b F O F
Nen´ı tˇeˇzk´e nahl´ednout, ˇze automat M1 pˇrij´ım´a vˇsechna slova jazyka L = {bu | u ∈ {a, b}? }. 2.1.41 Vˇ eta. Automat M i k nˇemu redukovan´ y automat M1 pˇrij´ımaj´ı stejn´ y jazyk, tj. jsou ekvivalentn´ı. Myˇ slenka d˚ ukazu t´eto vˇety vypl´ yv´a z konstrukce redukovan´eho automatu. Nejprve jsme odstranili nedosaˇziteln´e stavy, kter´e se nemohou vyskytnout pˇri pˇrijet´ı ˇz´adn´eho slova. N´aslednˇe jsme pouze slepovali“ ty stavy a to tak, ˇze jestliˇze jsme se po orientovan´em sledu z q0 dostali do ” koncov´eho stavu v p˚ uvodn´ım automatu, tak to sam´e platilo v redukovan´em, a naopak. 2.1.42 Vˇ eta. Dva DFA M1 a M2 pˇrij´ımaj´ı stejn´ y jazyk (tj. jsou ekvivalentn´ı) pr´avˇe tehdy, kdyˇz jejich odpov´ıdaj´ıc´ı redukovan´e automaty se liˇs´ı pouze pojmenov´an´ım stav˚ u. Myˇ slenka d˚ ukazu. Jestliˇze se redukovan´e automaty k automat˚ um M1 a M2 liˇs´ı pouze pojmenov´ an´ım stav˚ u, pak jsou automaty M1 a M2 ekvivalentn´ı. To vypl´ yv´a z pˇredchoz´ı vˇety. Pˇredpokl´ adejme, ˇze automaty M1 a M2 jsou ekvivalentn´ı. Utvoˇrme k nim redukovan´e automaty M1 a M2 ; oznaˇcme M1 = (Q1 , Σ, δ1 , q1 , F1 ) a M2 = (Q2 , Σ, δ2 , q2 , F2 ). Vytvoˇr´ıme pˇriˇrazen´ı stav˚ u Q1 stav˚ um Q2 takto: • Poˇc´ ateˇcn´ı stavy si odpov´ıdaj´ı, tj. q1 ; q2 . • Protoˇze vˇsechny stavy M1 jsou dosaˇziteln´e (a tak´e vˇsechny stavy M2 jsou dosaˇziteln´e), pro kaˇzd´e q ∈ Q1 existuje slovo w tak, ˇze δ1 (q1 , w) = q. Poloˇz´ıme δ1 (q1 , w) ; δ2 (q2 , w). D´ a se dok´ azat, ˇze se jedn´ a o pˇrejmenov´an´ı stav˚ u, kter´e je dobˇre definovan´e, zachov´av´a pˇrechodov´e funkce a stavy z F1 odpov´ıdaj´ı stav˚ um z F2 .
2.2
Nedeterministick´ e koneˇ cn´ e automaty
Koneˇcn´ y deterministick´ y automat mˇel tu vlastnost, ˇze v kaˇzd´em stavu reagoval na kaˇzd´e p´ısmeno pˇrenˇe jedn´ım zp˚ usobem (pˇrechodov´a funkce byla zobrazen´ı z mnoˇziny Q × Σ do Q). Nedeterministick´e automaty se liˇs´ı t´ım, ˇze jsme-li ve stavu q a ˇcteme vstupn´ı p´ısmeno a, m˚ uˇzeme pˇrej´ıt do nˇekolika (a tak´e ˇz´ adn´eho) stavu. V t´eto sekci uk´aˇzeme, ˇze ke kaˇzd´emu nedeterministick´emu automatu existuje deterministick´ y koneˇcn´ y automat, kter´ y pˇrij´ım´a stejn´ y jazyk. To n´am, spolu s faktem, ˇze nedeterministick´e automaty se sn´aze navrhuj´ı, umoˇzn´ı zjednoduˇsit postup pˇri n´avrhu koneˇcn´eho automatu pˇrij´ımaj´ıc´ıho dan´ y jazyk. 2.2.1 • • • • •
Definice. Nedeterministick´y koneˇcn´y automat, zkr´acenˇe NFA, je pˇetice (Q, Σ, δ, I, F ), kde Q je koneˇcn´ a nepr´ azdn´ a mnoˇzina stav˚ u, Σ je koneˇcn´ a nepr´ azdn´ a mnoˇzina vstup˚ u, δ je pˇrechodov´ a funkce, I ⊆ Q je mnoˇzina poˇc´ ateˇcn´ıch stav˚ u, F ⊆ Q je mnoˇzina koncov´ ych stav˚ u.
Nedeterministick´ y koneˇcn´ y automat se od deterministick´eho koneˇcn´eho automatu liˇs´ı t´ım, ˇze Marie Demlov´ a: Jazyky, automaty a gramatiky
Pˇred. 3: 17/10/2016
14
[161014-1204 ]
1. NFA m˚ uˇze m´ıt v´ıc poˇc´ ateˇcn´ıch stav˚ u, nejen jeden, 2. kaˇzd´emu stavu q a kaˇzd´emu vstupn´ımu p´ısmenu a pˇriˇrazuje pˇrechodov´a funkce δ nˇekolik stav˚ u (i ˇz´ adn´ y stav); tj. δ(q, a) je mnoˇzina stav˚ u, tˇreba i pr´azdn´a. Form´ alnˇe: δ: Q × Σ → P(Q), kde P(Q) je mnoˇzina vˇsech podmnoˇzin mnoˇziny stav˚ u Q. 2.2.2 Stavov´ y diagram NFA. Je d´an nedeterministick´ y automat M = (Q, Σ, δ, I, F ). Stavov´y diagram automatu M je orientovan´ y ohodnocen´ y graf, jehoˇz mnoˇzina vrchol˚ u je mnoˇzina stav˚ u Q, z vrcholu q do vrcholu p vede hrana ohodnocen´a vstupn´ım symbolem a pr´avˇe tehdy, kdyˇz p ∈ δ(q, a). (Poˇc´ ateˇcn´ı i koncov´e stavy jsou oznaˇceny stejnˇe jako u stavov´eho diagramu deterministick´eho automatu; tj. do kaˇzd´eho poˇc´ateˇcn´ıho stavu a z kaˇzd´eho koncov´eho stavu vede ˇsipka.) Rozd´ıl mezi stavov´ ym diagramem NFA a DFA je jen v tom, ˇze ve stavov´em diagramu nedeterministick´eho automatu mohou existovat stavy, ze kter´ ych vych´az´ı nˇekolik orientovan´ ych hran ohodnocen´ ych stejn´ ym p´ısmenem i stavy, ze kter´ ych nevych´az´ı ˇz´adn´a hrana ohodnocen´ a nˇekter´ ym p´ısmenem. Dˇr´ıve neˇz definujeme rozˇs´ıˇrenou pˇrechodovou funkci, zavedeme n´asleduj´ıc´ı znaˇcen´ı. Pro danou mnoˇzinu stav˚ u X ⊆ Q a a ∈ Σ poloˇz´ıme δ(X, a) =
[ {δ(q, a) | q ∈ X}.
2.2.3 Rozˇ s´ıˇ ren´ a pˇ rechodov´ a funkce NFA. Je d´an automat (Q, Σ, δ, I, F ). Rozˇs´ıˇren´ a pˇrechodov´ a funkce δ ? : Q × Σ? → P(Q) je definovan´a induktivnˇe takto: 1. δ ? (q, ε) = {q}, pro vˇsechna q ∈ Q, 2. δ ? (q, ua) = δ(δ ? (q, u), a)(= 2.2.4
S
{δ(p, a) | p ∈ δ ? (q, u)}), pro vˇsechna q ∈ Q, a ∈ Σ, u ∈ Σ? .
Pˇ r´ıklad. Je d´ an NFA tabulkou
→ ←
q0 q1 q2
0 {q0 } {q2 } ∅
1 {q0 , q1 } ∅ ∅
Rozˇs´ıˇren´ a pˇrechodov´ a funkce δ ? pracuje nad slovem 0110 takto: 1. δ ? (q0 , 0) = {q0 }; 2. δ ? (q0 , 01) = δ(q0 , 1) = {q0 , q1 }; 3. δ ? (q0 , 011) = δ(q0 , 1) ∪ δ(q1 , 1) = {q0 , q1 } ∪ ∅ = {q0 , q1 }; 4. δ ? (q0 , 0110) = δ(q0 , 0) ∪ δ(q1 , 0) = {q0 } ∪ {q2 } = {q0 , q2 }. 2.2.5 Tvrzen´ı. Je d´ an NFA M = (Q, Σ, δ, I, F ). Pak pro kaˇzd´ y stav q a kaˇzd´e slovo w ∈ Σ? jsou n´ asleduj´ıc´ı dvˇe vlastnost´ı ekvivalentn´ı: 1. p ∈ δ ? (q, w) 2. existuje orientovan´ y sled ve stavov´em diagramu z vrcholu q do vrcholu p oznaˇcen´ y slovem w. Marie Demlov´ a: Jazyky, automaty a gramatiky
Pˇred. 3: 17/10/2016
2.2. Nedeterministick´e koneˇcn´e automaty
[161014-1204 ]
15
ˇ 2.2.6 Slovo pˇ rij´ıman´ e NFA. Rekneme, ˇze NFA M = (Q, Σ, δ, I, F ) pˇrij´ım´ a slovo w ∈ Σ? ? pr´ avˇe tehdy, kdyˇz δ (I, w) ∩ F =6= ∅; jin´ ymi slovy pro nˇejak´ y z poˇc´ateˇcn´ıch stav˚ u q0 ∈ I plat´ı δ ? (q0 , w) ∩ F 6= ∅. Pˇredchoz´ı definici m˚ uˇzeme pˇreformulovat i takto: slovo w je pˇrij´ım´ano NFA pr´avˇe tehdy, kdyˇz ve stavov´em diagramu existuje orientovan´ y sled oznaˇcen´ y slovem w, kter´ y zaˇc´ın´a v nˇekter´em z poˇc´ ateˇcn´ıch stav˚ u automatu a konˇc´ı v nˇekter´em z koncov´ ych stav˚ u. V pˇr´ıkladu 2.2.4, NFA pˇrij´ım´ a slovo 0110. 2.2.7 Jazyk pˇ rij´ıman´ y NFA. Je d´an NFA M = (Q, Σ, δ, I, F ). Jazyk L(M ) pˇrij´ıman´y NFA M se skl´ ad´ a z pr´ avˇe vˇsech slov, kter´e jsou pˇrij´ım´any M . 2.2.8 Pozorov´ an´ı. Kaˇzd´ y deterministick´ y automat M = (Q, Σ, δ, q0 , F ) m˚ uˇzeme povaˇzovat za nedeterministick´ y. Staˇc´ı ˇr´ıci, ˇze mnoˇzina poˇc´ateˇcn´ıch stav˚ u obsahuje jen q0 a u pˇrechodov´e funkce δ(q, a) = p ztotoˇznit stav p s jednoprvkovou mnoˇzinou {p}. 2.2.9 Tvrzen´ı. Ke kaˇzd´emu nedeterministick´emu automatu M existuje deterministick´ y autoc, kter´ mat M y pˇrij´ım´ a stejn´ y jazyk; tj. c). L(M ) = L(M c konstruuje, se naz´ Zp˚ usob, kter´ ym se DFA M yv´a podmnoˇzinov´ a konstrukce. 2.2.10 Podmnoˇ zinov´ a konstrukce. Je d´an nedeterministick´ y automat M = (Q, Σ, δ, I, F ). b c b b Definujeme deterministick´ y automat M = (Q, Σ, δ, q0 , F ) takto: b je mnoˇzina vˇsech podmnoˇzin mnoˇziny Q (tj. Q b = P(Q)); • Q • q0 = I; • Fb je mnoˇzina vˇsech tˇech podmnoˇzin Q, kter´e obsahuj´ı aspoˇ n jeden koncov´ y stav M , (tj. Fb = {X ⊆ Q | X ∩ F 6= ∅}); S b b • δ(X, a) = {δ(q, a) | q ∈ X} (tj. δ(X, a) je podmnoˇzina vˇsech stav˚ u, do kter´ ych vede hrana oznaˇcen´ a p´ısmenem a z nˇekter´eho stavu mnoˇziny X.) 2.2.11 Modifikace podmnoˇ zinov´ e konstrukce — hled´ an´ı pouze dosaˇ ziteln´ ych stav˚ u Obdobnˇe jako v 2.1.25 se jedn´ a o modifikaci prohled´av´an´ı stavov´eho diagramu do ˇs´ıˇrky. Je d´ an nedeterministick´ y automat M = (Q, Σ, I, δ, F ). 1. Q := {I}; A := {I}; 2. if A 6= ∅ do B := ∅; for all X ∈ A do b for all a ∈ Σ do δ(X, a) := δ(X, a); if δ(X, a) 6∈ Q then B := B ∪ {δ(X, a)}; 3. if B 6= ∅ do Q := Q ∪ B; A := B go to 2 b := Q; Fb := {X ∈ Q b | X ∩ F 6= ∅}; 4. qb0 := I; Q b c b b 5. return M = (Q, Σ, qb0 , δ, F ) 2.2.12 Vˇ eta. Jazyk L je pˇrij´ım´ an nˇejak´ ym nedeterministick´ ym automatem pr´avˇe tehdy, kdyˇz existuje deterministick´ y automat M1 takov´ y, ˇze L = L(M1 ). Jin´ ymi slovy, automaty NFA i DFA pˇrij´ımaj´ı stejnou tˇr´ıdu jazyk˚ u, a to regul´arn´ı jazyky. D˚ ukaz: Jedna implikace vypl´ yv´ a z pozorov´an´ı 2.2.8. Marie Demlov´ a: Jazyky, automaty a gramatiky
Pˇred. 3: 17/10/2016
16
[161014-1204 ]
Druh´ a implikace vypl´ yv´ a z podmnoˇzinov´e konstrukce 2.2.10. Indukc´ı podle d´elky slova u ∈ Σ? se d´ a dok´ azat: Pro kaˇzdou podmnoˇzinu X a kaˇzd´e slovo u ∈ Σ? plat´ı δb? (X, u) =
[ {δ ? (q, u) | q ∈ X}.
c dost´ Tedy z definice DFA M av´ ame c). L(M ) = L(M c vytvoˇren´ Proto M y postupem 2.2.11, tj. podmnoˇzinovou konstrukc´ı, je hledan´ y DFA M1 . c z pˇredchoz´ı vˇety m˚ 2.2.13 Pozn´ amka. Poznamenejme, ˇze poˇcet stav˚ u DFA M uˇze vzr˚ ust exponenci´ alnˇe oproti poˇctu stav˚ u NFA M . 2.2.14
Pˇ r´ıklad. Je d´ an NFA tabulkou
→ p q r ← s ← t
0 {p, q} {r, s} {p, r} ∅ ∅
1 {p} {t} {t} ∅ ∅
c, kter´ Najdˇete DFA M y pˇrij´ım´ a stejn´ y jazyk. ˇ sen´ı. DFA vytvoˇr´ıme pomoc´ı postupu 2.2.11. Na zaˇc´atku pr´ace algoritmu m´ame I = {p}, Reˇ Q = {{p}}, A = {{p}}. Mnoˇzinu stav˚ u Q i pˇrechodovou funkci δb konstruujeme takto: • Po prvn´ım pr˚ uchodu bodem 2 dost´av´ame: b δ({p}, 0) := δ(p, 0) = {p, q},
b δ({p}, 1) := δ(p, 1) = {p} a proto B := {{p, q}}.
V kroku 3 Q := {{p}, {p, q}} a A := {{p, q}}. • Po druh´em pr˚ uchodu bodem 2 dost´av´ame: b δ({p, q}, 0) := δ(p, 0) ∪ δ(q, 0) = {p, q, r, s} b δ({p, q}, 1) := δ(p, 1) ∪ δ(q, 1) = {p, t}
a
B := {{p, q, r, s}, {p, t}}.
V kroku 3 Q := {{p}, {p, q}, {p, q, r, s}, {p, t}} a
A := {{p, q, r, s}, {p, t}}.
• Po tˇret´ım pr˚ uchodu bodem 2 dost´av´ame: b δ({p, q, r, s}, 0) = {p, q, r, s}
a
b δ({p, q, r, s}, 1) = {p, t},
b b δ({p, t}, 0) = {p, q}, δ({p, t}, 1) = {p} a B := ∅. V kroku 4 pak definujeme: b := {{p}, {p, q}, {p, q, r, s}, {p, t}}, qb0 := {p}, Fb := {{p, q, r, s}, {p, t}}. Q Marie Demlov´ a: Jazyky, automaty a gramatiky
Pˇred. 3: 17/10/2016
2.2. Nedeterministick´e koneˇcn´e automaty
[161014-1204 ]
17
Pˇredchoz´ı postup je zn´ azornˇen v n´ asleduj´ıc´ı tabulce:
→ ← ←
{p} {p, q} {p, q, r, s} {p, t}
0 {p, q} {p, q, r, s} {p, q, r, s} {p, q}
1 {p} {p, t} {p, t} {p}
Oznaˇc´ıme-li I = {p}, A = {p, q}, B = {p, q, r, s} a C = {p, t}, dostaneme n´asleduj´ıc´ı tabulku.
→ ← ←
I A B C
0 A B B A
1 I C C I
c) se skl´ad´a ze vˇsech bin´arn´ıch slov, Nen´ı tˇeˇzk´e nahl´ednout, ˇze jazyk pˇrij´ıman´ y automatem M (i M kter´e konˇc´ı bud’ 01 nebo 00, tj. ze vˇsech bin´arn´ıch slov, kter´e maj´ı jako pˇredposledn´ı symbol 0.
Marie Demlov´ a: Jazyky, automaty a gramatiky
Pˇred. 3: 17/10/2016
