´ ´I PR ˇ ´IKLADY 1 UVODN
J. Hora, P. Jedliˇcka
1
´ Uvodn´ ı pˇ r´ıklady
Pod slovem automat si vˇetˇsina lid´ı pˇredstav´ı automat na k´avu. Jin´ ym toto slovo m˚ uˇze navodit pˇredstavu nonstop herny a automat˚ u, na kter´ ych se toˇc´ı tˇri kotouˇce s obr´ azky ban´an˚ u, pomeranˇc˚ u a sedmiˇcek. Ani jedno z tˇechto zaˇr´ızen´ı nen´ı koneˇcn´ y automat ve smyslu definice, kter´ a bude uvedena n´ıˇze, pˇresto m´a jejich fungov´an´ı s nimi mnoho spoleˇcn´eho. Proto se nejdˇr´ıve budeme vˇenovat jednoduch´emu automatu na k´avu a nakresl´ıme si jeho diagram. Tento pˇr´ıklad i pˇr´ıklad n´ asleduj´ıc´ı jsou klasick´ ymi uk´azkami toho, jak zhruba funguj´ı koneˇcn´e automaty, a proto se vyskytuj´ı v mnoha materi´ alech t´ ykaj´ıc´ıch se t´eto problematiky. Pˇ r´ıklad. Pˇredstavme si jednoduch´ y automat na k´avu z devades´at´ ych let minul´eho stolet´ı. Je schopen pˇripravit pouze jeden druh k´avy (nevaln´e chuti), kter´ y stoj´ı pˇet korun. Automat pˇrij´ım´ a mince v hodnot´ ach 1, 2 a 5 korun a nevrac´ı zpˇet. Z´ akladn´ı u ´vahu, kterou mus´ıme udˇelat, je, v jak´ ych stavech se automat m˚ uˇze nach´ azet. Kdyˇz automat poprv´e zapneme, bude nepochybnˇe ve stavu s kreditem 0 Kˇc. Pˇredstavme si nejdˇr´ıve, ˇze postupnˇe vhazujeme korunov´e mince. Po vhozen´ı prvn´ı z nich se automat pˇresune do stavu s kreditem 1 Kˇc. Stavy automat˚ u budeme oznaˇcovat koleˇcky, ve kter´ ych bude pˇr´ıpadnˇe uveden jejich n´ azev. Pˇrechody mezi nimi budou zn´azornˇeny ˇsipkami, u kter´ ych je vyznaˇceno, jak´ y vstup tento pˇrechod vyvolal. Stav s nulov´ ym kreditem naz´ yv´ame inici´ aln´ı (poˇca´teˇcn´ı) a je oznaˇcen ˇsipkou pˇrich´ azej´ıc´ı odnikud“. Pr´avˇe popsan´a ˇca´st au” tomatu na k´avu je na obr´ azku 1. 1 Kˇc 1
1 2 Kˇc
2
0 Kˇc
Obr´azek 1: Automat na k´avu – zaˇca´tek konstrukce. Po vhozen´ı dalˇs´ıch tˇr´ı minc´ı se automat postupnˇe pˇresouv´a do stav˚ u s kreditem 2, 3 a 4. Po p´ at´e korunov´e minci automat vyd´a k´avu, pˇr´ıpadnˇe, pokud zapomnˇel technik doplnit kel´ımky, ji uvid´ıme prot´ect do odpadov´e mˇr´ıˇzky. Automat se vr´ at´ı do stavu s kreditem 0 Kˇc. Vid´ıme, ˇze popisovan´ y automat si vystaˇc´ı s pˇeti stavy podle aktu´aln´ıho kreditu. Pokud tedy tento automat naprogramujeme, potˇrebujeme, abychom mohli do jeho pamˇeti RAM uloˇzit jednu z pˇeti hodnot nula aˇz ˇctyˇri, kter´ a vyjadˇruje aktu´aln´ı kredit. Staˇc´ı tedy tˇri bity. Nav´ıc m˚ uˇzeme v budoucnu zv´ yˇsit cenu k´avy aˇz na osm korun, aniˇz bychom museli upgradovat pamˇet’. V pˇr´ıpadˇe, ˇze vhazujeme dvoukoruny, zvyˇsuje se samozˇrejmˇe kredit o dvˇe. Pˇredpokl´ad´ame, ˇze automat je poctiv´ y, a tak v pˇr´ıpadˇe ˇctyˇrkorunov´eho kreditu a vhozen´ı dvoukoruny dostaneme k´avu a automat pˇrejde do stavu s kreditem jedna, nebot’ automat nevrac´ı. Pokud v libovoln´em stavu vhod´ıme pˇetikorunu, dostaneme k´avu a kredit se nezmˇen´ı, ˇcili automat z˚ ustane 1
´ ´I PR ˇ ´IKLADY 1 UVODN
J. Hora, P. Jedliˇcka 5, 1 Kˇc
1
5,
0 Kˇc
2
2
2,
2
4 Kˇc
1
2, 1,
5, 2 Kˇc
1
1 3 Kˇc 5,
5, Obr´azek 2: Automat na k´avu. v p˚ uvodn´ım stavu. Cel´e sch´ema je na obr´ azku 2. Pˇ r´ıklad. Na obr´ azku 3 je sch´ema obvodu se schodiˇst’ov´ ym vyp´ınaˇcem. Oznaˇcme zleva b
b
b
b
b
b
Obr´azek 3: Schodiˇst’ov´ y vyp´ınaˇc. vyp´ınaˇce A, respektive B. Tento syst´em se m˚ uˇze nach´ azet ve ˇctyˇrech r˚ uzn´ ych stavech, podle pozice jednotliv´ ych vyp´ınaˇc˚ u. Pojmenujme tyto stavy U U , U D, DU a DD, podle anglick´ ych slov up and down a pozice vyp´ınaˇc˚ u na obr´ azku 3. Vstupem pro tento syst´em je posloupnost sloˇzen´a ze symbol˚ u A a B odpov´ıdaj´ıc´ı stisk˚ um jednotliv´ ych vyp´ınaˇc˚ u. Pokud jsou vyp´ınaˇce ve stavu U U a stiskneme napˇr´ıklad vyp´ınaˇc A, pˇrejde syst´em do stavu DU . Cel´e sch´ema je na obr´ azku 4. Stavy U U a DD jsou oznaˇceny dvojit´ ym koleˇckem zn´azorˇ nuj´ıc´ım, ˇze se jedn´a o stavy, kdy ˇza´rovka sv´ıt´ı. A UU DU A B
B
B
UD
A A
B
DD
Obr´azek 4: Sch´ema vyp´ınaˇc˚ u.
2
J. Hora, P. Jedliˇcka
2
ˇ ´IKLADY DEFINICE A PR
V pˇredchoz´ıch dvou pˇr´ıkladech se objevily vˇsechny aspekty, kter´e tvoˇr´ı koneˇcn´ y automat. Pˇresto ani jeden z nich nen´ı koneˇcn´ y automat a je tˇreba ch´ apat tyto pˇr´ıklady pouze jako ilustraˇcn´ı.
2
Definice a pˇ r´ıklady
Jeˇstˇe neˇz budeme moci definovat koneˇcn´ y automat, uvedeme nˇekolik pojm˚ u, kter´e jsou pro tuto definici potˇrebn´e. Definice. Abeceda je jak´ akoli koneˇcn´a mnoˇzina symbol˚ u (znak˚ u). Abecedu budeme obvykle znaˇcit symbolem Σ (velk´e ˇreck´e p´ısmeno Sigma). Pˇr´ıkladem abecedy m˚ uˇze b´ yt bin´arn´ı abeceda Σ1 = {0, 1}, kterou na nejniˇzˇs´ı u ´rovni pouˇz´ıvaj´ı veˇsker´ a elektronick´a zaˇr´ızen´ı, abecedou pro automat na k´avu byla mnoˇzina Σ2 = {1, 2, 5}. Pˇri pouˇzit´ı automatu pro vyhled´av´ an´ı v textu m˚ uˇze b´ yt abecedou napˇr´ıklad mnoˇzina Σ3 = ASCII, tedy mnoˇzina znak˚ u, ze kter´ ych se skl´ ad´a prohled´avan´ y text. Vstupem pro automat ale obvykle neb´ yv´a jen jeden znak, ale posloupnost v´ıce znak˚ u: Definice. Slovo nad abecedou Σ je kaˇzd´a koneˇcn´a posloupnost znak˚ u t´eto abecedy. Definice. D´elkou slova w rozum´ıme poˇcet jeho znak˚ u a znaˇc´ıme ji | w |. D´elka slova w = abbab nad abecedou {a, b} je rovna pˇeti, a tak | w |= 5. Znaˇ cen´ı. Pr´ azdn´e slovo (ˇcili slovo neobsahuj´ıc´ı ˇza´dn´ y znak) znaˇc´ıme ε (ˇcti epsilon), a plat´ı | ε |= 0. Znaˇ cen´ı. Mnoˇzinu vˇsech slov nad abecedou Σ znaˇc´ıme Σ∗ . Pokud je abeceda nepr´ azdn´ a, coˇz je samozˇrejmˇe rozumn´ y pˇredpoklad, je Σ∗ nekoneˇcn´a mnoˇzina. Definice. Jazyk je jak´ akoli podmnoˇzina mnoˇziny Σ∗ . Nyn´ı jiˇz m˚ uˇzeme definovat koneˇcn´ y automat a dalˇs´ı souvisej´ıc´ı pojmy. Tyto definice budou vysvˇetleny na pˇr´ıkladu, kter´ y po nich n´ asleduje. Definice. Koneˇcn´y automat (d´ale jen automat) je uspoˇr´adan´ a pˇetice (Q, Σ, δ, q0 , F ), kde Q je koneˇcn´a mnoˇzina stav˚ u, Σ je koneˇcn´a vstupn´ı abeceda, δ : Q × Σ → Q je pˇrechodov´a funkce, q0 ∈ Q je inici´ aln´ı stav a F ⊆ Q je mnoˇzina pˇrij´ımaj´ıc´ıch stav˚ u. Pozn´ amka. Pˇredchoz´ı definice je definic´ı tvz. koneˇcn´eho deterministick´eho automatu, jelikoˇz se ale v tomto materi´ alu nebudeme nedeterministick´ ymi automaty zab´ yvat, nen´ı
3
J. Hora, P. Jedliˇcka
2
ˇ ´IKLADY DEFINICE A PR
tato vlastnost v definici uvedena. Definice. V´ypoˇcet automatu nad slovem w = x1 . . . xn je posloupnost stav˚ u r0 , . . . , rn tak, ˇze r0 = q0 je inici´ aln´ı stav a δ(ri−1 , xi ) = ri , pro i = 1, . . . n. Prvn´ım stavem kaˇzd´eho v´ ypoˇctu je vˇzdy inici´ aln´ı stav, coˇz je moˇzn´e ch´ apat tak, ˇze se po zpracov´an´ı pˇredchoz´ıho slova automat vˇzdy uvede do p˚ uvodn´ıho nastaven´ı. Tato situace neodpov´ıd´a automatu na k´avu, nebot’ po vyd´an´ı n´ apoje m˚ uˇze b´ yt kredit i nenulov´ y, a je tedy nutn´e ch´ apat posloupnost vˇsech vhozen´ ych minc´ı jako jeden dlouh´ y vstup. Definice. Automat dan´e slovo pˇrij´ım´ a, pokud v´ ypoˇcet nad t´ımto slovem konˇc´ı ve stavu n´ aleˇzej´ıc´ım do F . Pˇ r´ıklad. Zjistˇete, jak´ y jazyk pˇrij´ım´ a automat na obr´ azku 5. 0
0 q0
1 1
q1
Obr´azek 5: Lich´ y poˇcet jedniˇcek. ˇ sen´ı. Reˇ Mnoˇzina stav˚ u dan´eho automatu je dvouprvkov´a Q = {q0 , q1 }. Vstupn´ı abeceda je tak´e dvouprvkov´a Σ = {0, 1} a z kaˇzd´eho stavu tedy vedou pr´avˇe dvˇe ˇsipky, jedna oznaˇcen´ a nulou, jedna jedniˇckou. Mnoˇzina pˇrij´ımaj´ıc´ıch stav˚ u je jednoprvkov´a F = {q1 }. Pˇrechodov´a funkce δ je ve schematu zn´azornˇena zm´ınˇen´ ymi ˇsipkami. Napˇr´ıklad ze stavu q0 vede ˇsipka oznaˇcen´a jedniˇckou do stavu q1 , coˇz vyjadˇruje fakt, ˇze v pˇr´ıpadˇe, kdy se automat nach´ az´ı ve stavu q0 a pˇreˇcte symbol 1, pˇresune se do stavu q1 . V matematick´em z´ apisu vyj´adˇreno δ(q0 , 1) = q1 . Neobr´ azkov´ y popis automatu, kter´ y obsahuje vˇsechny informace, se obvykle ˇ adky jsou oznaˇceny stavy, sloupce uv´ ad´ı ve formˇe tabulky, viz. Tabulka 1. R´ 0 q0 q1
→ q0 ← q1
1 q1 q0
Tabulka 1: Lich´ y poˇcet jedniˇcek. znaky vstupn´ı abecedy. Na pˇr´ısluˇsn´em pol´ıˇcku pak je stav, do kter´eho automat pˇrejde z dan´eho stavu pˇri pˇrijet´ı dan´eho znaku. Tabulka tedy obsahuje vˇsechny ˇ hodnoty pˇrechodov´e funkce δ. Sipkou dovnitˇr je oznaˇcen inici´ aln´ı stav a ˇsipkami ven stavy pˇrij´ımac´ı. Uvaˇzujme napˇr´ıklad slovo w = 100110. V´ ypoˇcet automatu nad t´ımto slovem zaˇc´ın´a ve stavu q0 . Pˇri pˇreˇcten´ı prvn´ıho znaku 1 se pˇresune do stavu q1 . Pak 4
J. Hora, P. Jedliˇcka
2
ˇ ´IKLADY DEFINICE A PR
pˇreˇcte nulu a z˚ ustane ve stavu q1 atd. Cel´ y v´ ypoˇcet nad slovem w je tedy q0 q1 q1 q1 q0 q1 q1 , a tedy automat slovo w pˇrij´ım´ a, nebot’ posledn´ı stav v´ ypoˇctu je pˇrij´ımaj´ıc´ı. Z diagramu automatu vid´ıme, ˇze pˇrijet´ı symbolu 0 nemˇen´ı stav. Automat pˇrij´ım´ a napˇr´ıklad slova 1, 111 ˇci 11111 a zjiˇst’ujeme, ˇze automat pˇrij´ım´ a pr´avˇe ta slova, kter´ a obsahuj´ı lich´ y poˇcet jedniˇcek. Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat nad abecedou Σ = {0, 1} pˇrij´ımaj´ıc´ı pr´avˇe ta slova, kter´ a obsahuj´ı alespoˇ n dva znaky. ˇ sen´ı. Reˇ D´ıky tomu, ˇze pˇrijet´ı slova nez´avis´ı na tom, z jak´ ych znak˚ u se skl´ad´a, povedou z kaˇzd´eho stavu obˇe ˇsipky do stejn´eho stavu a m˚ uˇzeme je tedy kreslit jako jednu s dvojit´ ym popiskem. Inici´aln´ı stav q0 je nepˇrij´ımaj´ıc´ı. Po pˇreˇcten´ı prvn´ıho znaku se automat pˇresune do stavu q1 , tak´e nepˇrij´ımaj´ıc´ıho. Dalˇs´ı znak jiˇz pˇresune automat do pˇrij´ımaj´ıc´ıho stavu q2 a dalˇs´ı stavy jiˇz nejsou potˇreba, nebot’ slovo bude uˇz vˇzdy pˇrijato, at’ obsahuje jak´ekoli dalˇs´ı znaky. Automat je na obr´ azku 6.
q0
0,1
0,1
q1
0,1 q2
Obr´azek 6: Slova obsahuj´ıc´ı alespoˇ n dva znaky. Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat nad abecedou Σ = {0, 1} pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´ a maj´ı poˇcet jedniˇcek dˇeliteln´ y tˇremi. ˇ sen´ı. Reˇ Jelikoˇz vlastnost, kter´ a n´ as u dan´eho slova zaj´ım´ a je dˇelitelnost poˇctu jedniˇcek v nˇem obsaˇzen´ ych, mus´ıme navrhnout automat tak, aby si pamatoval, jak´ y je zbytek po dˇelen´ı poˇctu jedniˇcek ˇc´ıslem tˇri. Tento zbytek m˚ uˇze nab´ yvat hodnot ˇ budou staˇcit tˇri stavy. Inici´aln´ı stav q0 mus´ı b´ 0, 1 nebo 2. Cili yt pˇrij´ımaj´ıc´ı, protoˇze poˇcet jedniˇcek v pr´azdn´em slovˇe je roven nule, coˇz je ˇc´ıslo dˇeliteln´e tˇremi. Pˇri ˇcten´ı jedniˇcek se bude automat cyklicky pˇresouvat po tˇechto tˇrech stavech. Nuly ve slovˇe obsaˇzen´e nemˇen´ı fakt, jestli je slovo pˇrij´ım´ ano ˇci nikoli, a proto automat pˇri pˇreˇcten´ı symbolu 0 nemˇen´ı sv˚ uj stav, dan´e ˇsipky jsou smyˇcky. Automat je na obr´ azku 7. 0 q1 0 1 q0
1 1
q2
0
Obr´azek 7: Poˇcet jedniˇcek je dˇeliteln´ y tˇremi.
5
J. Hora, P. Jedliˇcka
2
ˇ ´IKLADY DEFINICE A PR
Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat nad abecedou Σ = {0, 1} pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´ a maj´ı prvn´ı a posledn´ı znak stejn´ y, a to vˇcetnˇe slov jednoznakov´ ych. ˇ Reˇ sen´ı. Automat mus´ı b´ yt schopen si nˇejak´ ym zp˚ usobem zapamatovat, jak´ y byl prvn´ı znak a po pˇreˇcten´ı kaˇzd´eho dalˇs´ıho znaku se pˇresunout do pˇrij´ımaj´ıc´ıho ˇci nepˇrij´ımaj´ıc´ıho stavu podle toho, zda se shoduje se znakem prvn´ım. Je proto nutn´e, aby se automat v pˇr´ıpadˇe, kdy prvn´ı znak je nula, pˇresunul do mnoˇziny stav˚ u, do kter´e se nem˚ uˇze dostat, pokud byl prvn´ı znak jedniˇcka, a naopak. Inici´aln´ı stav q0 povaˇzujeme za nepˇrij´ımaj´ıc´ı, i kdyˇz je lehce nejasn´e, zda se prvn´ı znak pr´azdn´eho slova shoduje s posledn´ım. Po pˇrijet´ı prvn´ıho znaku, at’ uˇz se jedn´a o nulu ˇci jedniˇcku, se automat pˇresune do pˇrij´ımaj´ıc´ıho stavu (bud’ q1 nebo q3 ). V pˇr´ıpadˇe, ˇze byl prvn´ı znak nula, bude se dalˇs´ı v´ ypoˇcet nad dan´ ym slovem odehr´ avat jen ve stavech q1 a q2 . Do stavu q1 se automat pˇresune vˇzdy, kdyˇz byl posledn´ı pˇreˇcten´ y znak nula, a do stavu q2 , kdyˇz se jednalo o jedniˇcku. Pokud byla prvn´ım znakem jedniˇcka, je situace analogick´a. Automat je na obr´ azku 8. 0 1 1 q1 q2 0 0 q0 1 0 1 0 q3 q4 1 Obr´azek 8: Prvn´ı a posledn´ı znak stejn´ y. Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat nad abecedou Σ = {A, B} pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´ a zaˇc´ınaj´ı na BABA, ˇ sen´ı. Reˇ Posloupnost znak˚ u BABA hraje v tomto automatu kl´ıˇcovou roli, proto je dobr´e zaˇc´ıt n´ avrh automatu (a i dalˇs´ıch dvou) posloupnost´ı pˇeti stav˚ u q0 aˇz q4 spolu se ˇctyˇrmi z´ akladn´ımi ˇsipkami, viz. obr´ azek 9. Stav q4 je pˇrij´ımaj´ıc´ı. V pˇr´ıpadˇe, q0
B
q1
A
q2
B
q3
A
q4
Obr´azek 9: Zaˇca´tek n´ avrhu automatu. ˇze jako prvn´ı pˇrijde znak A, dan´e slovo nesplˇ nuje podm´ınku zad´an´ı a nem˚ uˇze uˇz b´ yt nikdy pˇrijato, proto je nutn´ y jeˇstˇe dalˇs´ı stav q5 , ze kter´eho se automat uˇz nikdy nedostane. Ze stejn´eho d˚ uvodu povedou do stavu q5 zbyl´e ˇsipky ze stav˚ u q2 , q3 , q4 . Pokud slovo zaˇc´ınalo na sekvenci BABA, nez´aleˇz´ı na dalˇs´ıch znac´ıch 6
J. Hora, P. Jedliˇcka
2
ˇ ´IKLADY DEFINICE A PR
a slovo mus´ı b´ yt automatem pˇrijato, proto obˇe ˇsipky ze stavu q5 jsou smyˇcky. Cel´ y automat je na obr´ azku 10. B
q0
A
q1
B
q2
B
A
A
A,B
A
q3
q4
B
q5
A,B
Obr´azek 10: Slova zaˇc´ınaj´ıc´ı na BABA. Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat nad abecedou Σ = {A, B} pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´ a obsahuj´ı BABA, ˇ sen´ı. Reˇ Zaˇcneme stejnou kostrou“ automatu jako v pˇredchoz´ım pˇr´ıkladu. Stav q4 je ” stav, do kter´eho se v´ ypoˇcet automatu dostane ve chv´ıli, kdy pˇreˇcte ze vstupn´ıho slova sekvenci BABA. Takov´e slovo uˇz mus´ı b´ yt kaˇzdop´ adnˇe pˇrijato, a proto automat uˇz z˚ ust´ av´ a v tomto stavu a ˇcek´a“ na konec vstupu. Pokud se automat ” nach´ az´ı ve stavu q1 a pˇrijde znak B, z˚ ust´ av´ a automat v tomto stavu, nebot’ z hledan´e posloupnosti nalezl pr´avˇe tento znak. V pˇr´ıpadˇe, ˇze dva posledn´ı znaky byly BA (automat je ve stavu q2 ) a pˇreˇcten znak A, mus´ı se vr´ atit do inici´ aln´ıho stavu, coˇz znamen´ a, ˇze z hledan´e sekvence aktu´alnˇe nenaˇsel ˇza´dnou ˇca´st. Podobnˇe bychom mohli ch´ apat (a pˇr´ıpadnˇe i oznaˇcit) stav q3 jako stav, ve kter´em se automat nach´ az´ı, pokud posledn´ı tˇri znaky byly BAB. N´ asleduj´ıc´ı znak B mus´ı automat pˇresunout do stavu q1 , viz. obr´ azek 11. A q0
B
q1
A,B
B
B A
q2
B
q3
A
q4
A Obr´azek 11: Slova obsahuj´ıc´ı BABA. Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat nad abecedou Σ = {A, B} pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´ a konˇc´ı na BABA. ˇ sen´ı. Reˇ N´ avrh tohoto automatu je velice podobn´ y pˇredchoz´ımu, nebot’ automat ve vstupn´ım slovˇe vyhled´ av´ a sekvenci BABA. Proto budou vˇsechny ˇsipky ze stav˚ u q0 , q1 , q2 a q3 stejn´e jako v automatu pˇredeˇsl´em. Pˇredpokl´adejme, ˇze automat pˇreˇcetl ˇca´st vstupn´ıho slova, kter´ a konˇcila na sekvenci BABA. Pak se nach´ az´ı ve
7
J. Hora, P. Jedliˇcka
A q0
ˇ ´IKLADY DEFINICE A PR
2
B
B B
q1
A
q2
A
q3
B
B
A
q4 A
Obr´azek 12: Slova konˇc´ıc´ı na BABA. stavu q4 a pokud vstupn´ı slovo neobsahuje dalˇs´ı znaky, je pˇrijato. Tento automat ale v pˇr´ıpadˇe, kdy po sekvenci BABA pˇrijde dalˇs´ı znak, ˇreknˇeme A, nem˚ uˇze z˚ ustat v pˇrij´ımac´ım stavu, nebot’ pˇreˇcten´ a ˇca´st vstupn´ıho slova jiˇz nekonˇc´ı na BAB. V tomto pˇr´ıpadˇe se automat pˇresune do stavu q0 , jelikoˇz aktu´aln´ı vstup nekonˇc´ı ani na B, ani na BA, ani na BAB. Jin´ a je situace, kdy po znac´ıch BABA pˇrijde B. Pak jsou posledn´ı tˇri znaky BAB a automat se pˇresouv´a do stavu q3 (pokud by n´ asledovalo dalˇs´ı A, mus´ı se automat pˇresunout do pˇrij´ımaj´ıc´ıho stavu q4 ). Podobnˇe jako v pˇredchoz´ım pˇr´ıkladu je moˇzn´e pro u ´ˇcely n´ avrhu automatu oznaˇcit jednotliv´e stavy pˇr´ısluˇsnou ˇc´ıst´ı hledan´eho slova, viz. obr´ azek 12. Pˇ r´ıklad. →A B Zjistˇete, jak´ y jazyk pˇrij´ım´ a automat C ←D E
0 E C D E E
1 B E E E E
ˇ sen´ı. Reˇ Nejdˇr´ıve je nutn´e automat nakreslit, viz. obr´ azek 13. Jako prvn´ı si vˇsimneme, A
1
0
B
1 0
C 1 E
0
D
0, 1 0, 1
Obr´azek 13: Automat pˇrij´ımaj´ıc´ı jedin´e slovo. ˇze jakmile se automat dostane do stavu E, uˇz v nˇem z˚ ustane a nikdy dan´e slovo nepˇrijme. Do jedin´eho pˇrij´ımaj´ıc´ıho stavu D se automat dostane pouze v pˇr´ıpadˇe, kdy prvn´ı tˇri znaky budou 100. Jin´e slovo ovˇsem automat nepˇrij´ım´ a, nebot’ pˇrijet´ı jak´ehokoli dalˇs´ıho znaku pˇresune automat do stavu E.
8
J. Hora, P. Jedliˇcka
´ ´I JAZYKY A OPERACE S NIMI 3 REGULARN
Pˇ r´ıklad. →1 Zjistˇete, jak´ y jazyk pˇrij´ım´ a automat ←2 3
a 2 1 3
b 3 3 3
ˇ sen´ı. Reˇ Automat je na obr´ azku 14. Stav 3 opˇet hraje roli odpadkov´eho koˇse“, ˇcili ” a 1 2 a b
b 3
a, b
Obr´azek 14: Automat pˇrij´ımaj´ıc´ı lich´ y poˇcet a. nepˇrij´ımaj´ıc´ıho stavu, ze kter´eho se automat jiˇz nem˚ uˇze dostat. Pˇrijet´ı znaku b ve stavech 1 i 2 pˇresune automat pr´avˇe do stavu 3. Pr´azdn´e slovo automat nepˇr´ıj´ım´ a, m˚ uˇze tedy pˇrij´ımat jen slova sloˇzen´a ze znak˚ u a, ne vˇsak vˇsechna. Snadno nahl´edneme, ˇze pˇrij´ım´ a slova a, aaa nebo aaaaa a vid´ıme, ˇze jazyk automatu jsou pr´avˇe slova sloˇzen´a z lich´eho poˇctu ´aˇcek.
3
Regul´ arn´ı jazyky a operace s nimi
Definice. Jazyk automatu A je mnoˇzina slov, kter´e automat pˇrij´ım´ a. Znaˇc´ıme ji L(A). Definice. Jazyk L se naz´ yv´a regul´ arn´ı, pokud existuje koneˇcn´ y automat A, kter´ y ho pˇrij´ım´ a, tedy L = L(A). Posledn´ı definice naznaˇcuje, ˇze ne kaˇzd´ y jazyk je regul´ arn´ı. Pˇr´ıklad takov´ehoto jazyka uvid´ıme pozdˇeji. V n´ asleduj´ıc´ıch pˇr´ıkladech a vˇet´ach uk´aˇzeme, ˇze pr˚ unik i sjednocen´ı dvou regul´ arn´ıch jazyk˚ u je opˇet regul´ arn´ı jazyk, a tak´e ˇze doplˇ nek regul´ arn´ıho jazyka je regul´ arn´ı. Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat, kter´ y pˇrij´ım´ a pr´avˇe slova neobsahuj´ıc´ı sekvenci 001. ˇ sen´ı. Reˇ Zad´an´ı tohoto pˇr´ıkladu se od pˇredchoz´ıch liˇs´ı t´ım, ˇze podm´ınka je zad´ana negativnˇe. V takov´ ych pˇr´ıpadech je mnohdy tˇeˇzk´e navrhnout dan´ y automat pˇr´ımo a navrhuje se nejdˇr´ıve automat bez negace v zad´an´ı. Automat pˇrij´ımaj´ıc´ı slova, kter´ a obsahuj´ı sekvenci 001, je na obr´ azku 15. Nyn´ı se jiˇz staˇc´ı zamyslet nad t´ım, v jak´em stavu tohoto automatu skonˇc´ı v´ ypoˇcet v pˇr´ıpadˇe, ˇze vstupn´ı slovo
9
´ ´I JAZYKY A OPERACE S NIMI 3 REGULARN
J. Hora, P. Jedliˇcka
1 q0
0, 1
0 0 1
0
q1
1
q2
q3
Obr´azek 15: Automat pˇrij´ımaj´ıc´ı slova obsahuj´ıc´ı 001. sekvenci 001 neobsahuje. Je zˇrejm´e, ˇze to bude jeden ze stav˚ u q0 , q1 nebo q2 . Pokud tedy zamˇen´ıme pˇrij´ımaj´ıc´ı a nepˇrij´ımaj´ıc´ı stavy, dostaneme automat, kter´ y ˇ sen´ı je na obr´ pˇrij´ım´ a pr´avˇe slova nepˇrij´ıman´a p˚ uvodn´ım automatem. Reˇ azku 16. 1 q0
0 0 1
0
q1
q2
0, 1 1
q3
Obr´azek 16: Automat pˇrij´ımaj´ıc´ı slova neobsahuj´ıc´ı 001. Princip pouˇzit´ y v pˇredchoz´ım pˇr´ıkladu lze zobecnit. Jelikoˇz negace vstupn´ı podm´ınky popisuje doplnˇek p˚ uvodn´ıho jazyka, dost´av´ ame n´ asleduj´ıc´ı vˇetu: Vˇ eta. Doplnˇek L0 = Σ∗ \L regul´ arn´ıho jazyka L je regul´ arn´ı jazyk. Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´ a konˇc´ı na 1 a z´ aroveˇ n obsahuj´ı sekvenci 110. ˇ sen´ı. Reˇ Zad´an´ı obsahuje dvˇe podm´ınky spojen´e logickou spojkou a souˇcasnˇe“. Automat ” je samozˇrejmˇe moˇzn´e navrhnout pˇr´ımo, coˇz v tomto konkr´etn´ım pˇr´ıpadˇe nen´ı obt´ıˇzn´e (staˇc´ı pˇet stav˚ u), c´ılem tohoto pˇr´ıkladu je vˇsak uk´azat ˇreˇsen´ı, ve kter´em staˇc´ı navrhnout automaty pro jednotliv´e podm´ınky a n´ aslednˇe je vhodnˇe spojit do automatu jedin´eho. Automat A1 pˇrij´ımaj´ıc´ı slova konˇc´ıc´ı na 1 je na obr´ azku 17 vlevo a automat A2 pˇrij´ımaj´ıc´ı slova, kter´ a obsahuj´ı sekvenci 110 na obr´ azku 17 vpravo. V´ ysledn´ y automat A bude simulovat pr´aci obou tˇechto automat˚ u, A 0 1 B
0, 1
1
0
0
1
I
0
1
II
1
III
0
IV
Obr´azek 17: Dva automaty – pˇrij´ımaj´ıc´ı 1 na konci a obsahuj´ıc´ı 110 proto jeho stavy budou kombinace stav˚ u A, B a I,II,III,IV, ˇcili jich bude celkovˇe osm. Inici´aln´ım stavem bude stav AI jakoˇzto kombinace p˚ uvodn´ıch inici´ aln´ıch stav˚ u. Pˇrechodovou funkci odvod´ıme z pˇrechodov´ ych funkc´ı mal´ ych automat˚ u. 10
´ ´I JAZYKY A OPERACE S NIMI 3 REGULARN
J. Hora, P. Jedliˇcka
Pokud se automat A nach´ az´ı ve stavu AI a na vstupu pˇreˇcte symbol 1, pˇresune se do stavu BII, nebot’ automat A1 by se ze stavu A pˇresunul do B a automat A2 ze stavu I do stavu II. V pˇr´ıpadˇe, ˇze ve stavu AI pˇrijde 0, automat z˚ ustane ve stavu AI, protoˇze ani jeden z z p˚ uvodn´ıch automat˚ u nemˇen´ı v t´eto situaci sv˚ uj stav. T´ımto zp˚ usobem lze definovat pˇrechodovou funkci automatu A pro vˇsechny jeho stavy. Zb´ yv´a urˇcit, kter´e stavy budou pˇrij´ımaj´ıc´ı. Jelikoˇz maj´ı b´ yt splnˇeny obˇe vstupn´ı podm´ınky z´ aroveˇ n, pˇrij´ımaj´ıc´ı stav bude pouze jeden, a to BIV. Cel´ y automat A je na obr´ azku 18. Pr´avˇe popsan´ y souˇcin automat˚ u je tak´e moˇzn´e prov´est pomoc´ı tabulek, jak je vidˇet v tabulce 2. 0
0
AI
AII 1
0
1
1
0
BI
1
0
AIII
BII
0
0 1
BIII
1
0
AIV 1
1
BIV
Obr´azek 18: Automat pˇrij´ımaj´ıc´ı pr˚ unik jazyk˚ u
A1 →A ←B
0 A A
1 B B
A2 →I II III ← IV
0 I I IV IV
1 II III III IV
A1 × A2 → AI AII AIII AIV BI BII BIII ← BIV
0 AI AI AIV AIV AI AI AIV AIV
1 BII BIII BIII BIV BII BIII BIII BIV
Tabulka 2: Souˇcin automat˚ u ˇ adky v´ R´ ysledn´eho automatu simuluj´ı automat A2 a sloupce automat A1 . Nev´ yhodou t´eto konstrukce je, ˇze v´ ysledn´ y automat m´a mnohdy v´ıce stav˚ u, neˇz je pro dan´ y jazyk nutn´e. Tento nedostatek je moˇzn´e ˇreˇsit jeho n´ aslednou minimalizac´ı, kter´ a bude uvedena n´ıˇze. Uveden´ y postup je obecn´ y a v´ ysledn´ y automat A pˇrij´ım´ a slova, kter´ a n´ aleˇz´ı jak do jakyku L(A1 ) tak do jazyku L(A2 ), ˇcili L(A) = L(A1 ) ∩ L(A2 ). Tuto konstrukci lze nav´ıc pouˇz´ıt v´ıcekr´at, a tak dost´av´ ame: Vˇ eta. Pr˚ unik dvou (koneˇcnˇe mnoha) regul´ arn´ıch jazyk˚ u je regul´arn´ı jazyk. Pˇ r´ıklad. Navrhnˇete koneˇcn´ y automat pˇrij´ımaj´ıc´ı pr´avˇe slova, kter´ a konˇc´ı na 1 nebo obsahuj´ı sekvenci 110. 11
´ ´I JAZYKY A OPERACE S NIMI 3 REGULARN
J. Hora, P. Jedliˇcka
ˇ sen´ı. Reˇ Zad´an´ı je stejn´e jako v pˇredchoz´ım pˇr´ıkladu, jen jsou podm´ınky spojeny spojkou nebo“. Takov´e automaty je obvykle obt´ıˇznˇejˇs´ı navrhnout pˇr´ımo. Na druhou ” stranu lze pouˇz´ıt stejnou konstrukci jako v pˇredchoz´ım pˇr´ıkladu a sestrojit automat, kter´ y simuluje pr´aci obou automat˚ u A1 a A2 . Jedin´ y rozd´ıl bude v mnoˇzinˇe pˇrij´ımaj´ıc´ıch stav˚ u. Tentokr´ at staˇc´ı, aby bylo vstupn´ı slovo pˇrijato jedn´ım z automat˚ u. Aby bylo slovo pˇrijato automatem A1 , mus´ı v´ ypoˇcet skonˇcit ve stavu B, a tak budou pˇrij´ımaj´ıc´ı vˇsechny stavy BI, BII, BIII, BIV. Podobnˇe pro automat A2 dost´av´ ame pˇrij´ımaj´ıc´ı stavy AIV a BIV. Celkovˇe m´a tedy automat pˇet pˇrij´ımaj´ıc´ıch stav˚ u, viz. obr. 19. 0
0
AI 0 BI
AII 1
AIII 1
0 1
BII
1
1 BIII
0
AIV
0
0 1
0
1
BIV
1
Obr´azek 19: Automat pˇrij´ımaj´ıc´ı sjednocen´ı jazyk˚ u Logick´a spojka nebo“ reprezentuje v ˇreˇci mnoˇzin sjednocen´ı, m´ame L(A) = ” L(A1 ) ∪ L(A2 ). Vˇ eta. Sjednocen´ı dvou (koneˇcnˇe mnoha) regul´ arn´ıch jazyk˚ u je regul´ arn´ı jazyk. Jazyk obsahuj´ıc´ı pr´avˇe jedno slovo je vˇzdy regul´ arn´ı, pˇr´ısluˇsn´ y automat je moˇzn´e sestrojit podobnˇe jako na obr´ azku 13. V kombinaci s pˇredchoz´ı vˇetou dost´av´ ame, ˇze kaˇzd´ y koneˇcn´ y jazyk je regul´ arn´ı. N´ asleduj´ıc´ı pˇr´ıklad ukazuje, ˇze existuj´ı i neregul´arn´ı jazyky. Pˇ r´ıklad. Dokaˇzte, ˇze neexistuje koneˇcn´ y automat, kter´ y pˇrij´ım´a pr´avˇe slova {ε, ab, aabb, aaabbb, . . .} = {ai bi , i ∈ N}. ˇ sen´ı. Reˇ Pˇredpokl´adejme sporem, ˇze takov´ y automat A existuje a oznaˇcme poˇcet jeho stav˚ u n. Uvaˇzme slovo w = an bn . At’ q0 q1 . . . qn qn+1 . . . q2n je v´ ypoˇcet pˇredpokl´adan´eho automatu nad slovem w. Jelikoˇz m´a automat A n stav˚ u, mus´ı jiˇz bˇehem zpracov´av´ an´ı prvn´ı (a-ˇckov´e) ˇca´sti slova w doj´ıt k situaci, kdy se v´ ypoˇcet dostane do stavu, ve kter´em se jiˇz nach´ azel, ˇcili existuj´ı stavy qi = qj pro i 6= j, 0 ≤ i, j ≤ n. Jin´ ymi slovy se v´ ypoˇcet zacyklil. D´elka tohoto cyklu je j − i. Z v´ ypoˇctu nad slovem w ovˇsem vypl´ yv´a, ˇze pokud automatu pˇredloˇz´ıme slovo w0 = an−(j−i) bn , kter´e vznikne ze slova w vyˇr´ıznut´ım“ zm´ınˇen´eho cyklu, ” bude v´ ypoˇcet nad t´ımto slovem q0 q1 . . . qi qj+1 . . . qn qn+1 . . . q2n , a tedy automat A pˇrijme i slovo w0 , coˇz je spor, nebot’ toto slovo neobsahuje stejnˇe a-ˇcek a b-ˇcek. Argument pro neexistenci automatu pro dan´ y jazyk pouˇzit´ y v pˇredchoz´ım 12
˚ 4 MINIMALIZACE AUTOMATU
J. Hora, P. Jedliˇcka
pˇr´ıkladu se naz´ yv´a pumping lemma a lze ho pouˇz´ıt i v pro jin´e jazyky. Jeho princip je zaloˇzen na faktu, ˇze jedin´ a moˇznost, jak si m˚ uˇze automat nˇeco pamatovat, je pomoc´ı stav˚ u, ve kter´ ych se nach´ az´ı. Pokud ovˇsem automatu pˇredloˇz´ıme dostateˇcnˇe dlouh´e slovo, jeho pamˇet’ (poˇcet stav˚ u) nestaˇc´ı na to, aby si zapamatoval, kolik a-ˇcek tvoˇrilo prvn´ı ˇca´st vstupn´ıho slova, a nem˚ uˇze tak tento poˇcet porovnat s poˇctem n´ asledn´ ych b-ˇcek.
4
Minimalizace automat˚ u
Pˇri n´ avrhu automatu nˇekdy doch´ az´ı k tomu, ˇze m´a v´ ysledn´ y automat v´ıce stav˚ u, neˇz je nutn´e. Napˇr´ıklad pˇri pouˇzit´ı souˇcinov´e konstrukce je to bˇeˇzn´e, viz. obr. 18. V t´eto kapitole si uk´ aˇzeme, jak minimalizovat dan´ y (zkonstruovan´ y) automat minimalizovat, ˇcili nal´ezt automat s minim´aln´ım poˇctem stav˚ u pˇrij´ımaj´ıc´ı stejn´ y jazyk. Vlastn´ı proces minimalizace m´a dvˇe f´aze. Prvn´ı z nich je odstranˇen´ı zbyteˇcn´ ych“ stav˚ u. ” Pˇ r´ıklad. 0 1 →← A B D B D B Zjistˇete, jak´ y jazyk pˇrij´ım´ a automat ←C C B D B D ←E B D ˇ sen´ı. Reˇ Automat je na obr´ azku 20. Z nˇej je vidˇet, ˇze po pˇreˇcten´ı prvn´ıho znaku bude 0
1 B
0 A
1
0
1
C
0 0 D
1
E
1 Obr´azek 20: Prvn´ı a posledn´ı znak stejn´ y. automat vˇzdy v jednom ze stav˚ u B nebo D. Jelikoˇz pˇrij´ımaj´ıc´ı stavy jsou C a E, do kter´ ych se v´ ypoˇcet nad ˇza´dn´ ym slovem nedostane, a stav A, sest´av´ a jazyk z jedin´eho slova, toho pr´azdn´eho. Vid´ıme, ˇze odstranˇen´ım stav˚ u C a E dostaneme menˇs´ı automat se stejnou funkˇcnost´ı. Pozor, nen´ı moˇzn´e odstranit z automatu libovolnou mnoˇzinu stav˚ u. Definice. Stav q se naz´ yv´a dosaˇziteln´y, pokud existuje slovo w takov´e, ˇze v´ ypoˇcet nad t´ımto slovem konˇc´ı ve stavu q. 13
˚ 4 MINIMALIZACE AUTOMATU
J. Hora, P. Jedliˇcka
Definice. Koneˇcn´ y automat se naz´ yv´a dosaˇziteln´y, pokud jsou dosaˇziteln´e vˇsechny jeho stavy. Pˇ r´ıklad. Naleznˇete dosaˇzitelnou ˇca´st automatu A a n´ aslednˇe urˇcete, jak´ y jazyk dan´ y automat pˇrij´ım´ a. A →1 ←2 3 4 5 6 7 ←8
a 5 2 4 6 1 5 8 2
b 5 7 6 1 3 4 1 5
ˇ sen´ı. Reˇ Inici´aln´ı stav je vˇzdy dosaˇziteln´ y. Nalezen´e dosaˇziteln´e stavy budeme oznaˇcovat v posledn´ım sloupci tabulky. Ze inici´ aln´ıho stavu 1 m˚ uˇze automat pˇrej´ıt pouze do stavu 5. Ten je tedy tak´e dosaˇziteln´ y. Ze stavu 5 m˚ uˇze v´ ypoˇcet pokraˇcovat do stavu 1 nebo 3, o stavu 1 uˇz v´ıme, ˇze je dosaˇziteln´ y, oznaˇc´ıme tedy jen stav 3. Tento postup, ˇcili oznaˇcen´ı jako dosaˇziteln´ ych vˇsech stav˚ u, kter´ ymi m˚ uˇze v´ ypoˇcet pokraˇcovat z jiˇz oznaˇcen´ ych stav˚ u, opakujeme, dokud se mnoˇzina dosaˇziteln´ ych stav˚ u zvˇetˇsuje. Cel´ y postup pro tento automat je v tabulk´ach 3. A →1 ←2 3 4 5 6 7 ←8
a 5 2 4 6 1 5 8 2
b 5 7 6 1 3 4 1 5
D D
A →1 ←2 3 4 5 6 7 ←8
a 5 2 4 6 1 5 8 2
b 5 7 6 1 3 4 1 5
D D
D
A →1 ←2 3 4 5 6 7 ←8
a 5 2 4 6 1 5 8 2
b 5 7 6 1 3 4 1 5
D D D D
A →1 ←2 3 4 5 6 7 ←8
a 5 2 4 6 1 5 8 2
b 5 7 6 1 3 4 1 5
D D D D D D
Tabulka 3: Hled´an´ı dosaˇziteln´ ych stav˚ u Obecn´ y z´ apis algoritmu je n´ asleduj´ıc´ı. Bud’ D0 = {q0 } mnoˇzina obsahuj´ıc´ı inici´ aln´ı stav. Mnoˇzinu Di , i ≥ 1 zkonstruujeme z mnoˇziny Di−1 : Di = Di−1 ∪ {δ(q, x), q ∈ Di−1 , x ∈ Σ}. Mnoˇzina dosaˇziteln´ ych stav˚ u automatu A je takov´a mnoˇzina Dk , pro kterou plat´ı Dk = Dk+1 . Staˇc´ı nal´ezt nejmenˇs´ı takov´e k. Druh´a ˇca´st minimalizace ˇreˇs´ı situaci, kdy maj´ı nˇekter´e stavy automatu stej” nou funkci“ ve smyslu v´ ypoˇctu. Pˇr´ıklad takov´ ych stav˚ u je na obr´ azku 4. Toto 14
˚ 4 MINIMALIZACE AUTOMATU
J. Hora, P. Jedliˇcka
ˇctyˇrstavov´e zaˇr´ızen´ı lze nahradit dvoustavov´ ym (pˇrestoˇze jsou vˇsechny jeho stavy dosaˇziteln´e), viz. obr. 21, nebot’ dvojice stav˚ u U U , DD a U D, DU lze UD DU
A, B
UU DD
A, B
Obr´azek 21: Sch´ema vyp´ınaˇc˚ u zjednoduˇsen´e. slouˇcit aniˇz by se zmˇenila jeho funkce. Postup si uk´aˇzeme na pˇr´ıkladu ˇsestistavov´eho automatu. Pˇ r´ıklad. Naleznˇete minim´ aln´ı automat, kter´ y pˇrij´ım´ a stejn´ y jazyk jako automat A. A →1 2 ←3 4 5 ←6
a 1 1 6 1 2 6
b 3 3 5 5 4 2
ˇ sen´ı. Reˇ Automat je dosaˇziteln´ y, nebot’ D0 = {1}, D1 = {1, 3}, D2 = {1, 3, 5, 6}, D3 = {1, 2, 3, 4, 5, 6}. V prvn´ı f´ azi rozdˇel´ıme stavy automatu na dvˇe mnoˇziny, a to mnoˇzinu pˇrij´ımaj´ıc´ıch stav˚ u P , a mnoˇzinu nepˇrij´ımaj´ıc´ıch stav˚ u N . Myˇslenkou tohoto algoritmu je snaha slouˇcit stavy, kter´e se vzhledem k pˇrijet´ı ˇci nepˇrijet´ı jak´ehokoli slova chovaj´ı stejnˇe. Dva stavy, kter´e nepatˇr´ı do stejn´e mnoˇziny (P a N ) nen´ı moˇzn´e slouˇcit do jednoho stavu, jelikoˇz by v´ ysledn´ y stav musel b´ yt z´ aroveˇ n pˇrij´ımaj´ıc´ı i nepˇrij´ımaj´ıc´ı. Pro pˇrehlednost zmˇen´ıme v tabulce poˇrad´ı ˇr´adk˚ u tak, aby byly stavy tˇechto skupin u sebe, viz. tabulka 4. Nyn´ı nap´ıˇseme A →1 2 4 5 ←3 ←6
a 1 1 1 2 6 6
b 3 3 5 4 5 2
Tabulka 4: Tabulka automatu se zmˇenˇen´ ym poˇrad´ım stav˚ u tabulku automatu A, ale m´ısto konkr´etn´ıch stav˚ u ji vypln´ıme skupinou (P nebo N ), do kter´e stav v pˇr´ısluˇsn´em pol´ıˇcku patˇr´ı. Tato tabulka (ˇc. 5 vlevo) ukazuje, zda je moˇzn´e zadan´ y automat zmenˇsit na automat dvoustavov´ y. Jelikoˇz skupina N obsahuje dva r˚ uzn´e typy ˇr´adk˚ u (N P a N N ), je nutn´e stavy odˇ adky skupiny P jsou stejn´e a pov´ıdaj´ıc´ı tˇemto ˇr´adk˚ u rozdˇelit do dvou skupin. R´ 15
˚ 4 MINIMALIZACE AUTOMATU
J. Hora, P. Jedliˇcka
proto ji nen´ı nutn´e v t´eto chv´ıli dˇelit. Vid´ıme, ˇze v´ ysledn´ y minim´aln´ı automat mus´ı obsahovat alespoˇ n tˇri stavy odpov´ıdaj´ıc´ı skupin´am p˚ uvodn´ıch stav˚ u {1, 2}, {4, 5} a {3, 6}. Pojmenujme tyto skupiny postupnˇe α, β, γ a napiˇsme opˇet tabulku automatu A vyplnˇenou tˇemito skupinami, viz. tabulka 5 uprostˇred. Ve skupinˇe γ jsou dva r˚ uzn´e ˇr´adky a mus´ıme ji tedy d´ ale rozdˇelit na dvˇe podskupiny. Skupiny α a β m˚ uˇzeme ponechat. Abychom zabr´anili nejasnostem ve znaˇcen´ı skupin v jednotliv´ ych f´az´ıch minimalizace, oznaˇcme nov´e skupiny A →1 2 4 5 ←3 ←6
N
P
a N N N N P P
b P P N N N N
A →1 2 4 5 ←3 ←6
a α α α α γ γ
α β γ
A →1 2 4 5 ←3 ←6
b γ γ β β β α
I II III IV
a I I I I IV IV
b III III II II II I
Tabulka 5: Tabulka minimalizace automatu ˇr´ımsk´ ymi ˇc´ıslicemi, viz. tabulka 5 vpravo. Ta je opˇet m´ısto konkr´etn´ıch stav˚ u vyplnˇena pˇr´ısluˇsn´ ymi (ˇr´ımsk´ ymi) skupinami. D´ıky tomu, ˇze jsou ˇr´adky v jednotliv´ ych skupin´ach jiˇz stejn´e, algoritmus konˇc´ı. Posledn´ı tabulka je tabulkou minim´ aln´ıho automatu, kter´ y pˇrij´ım´ a stejn´ y jazyk jako automat A s t´ım, ˇze obsahuje nˇekter´e ˇr´adky v´ıckr´ at. V´ yslednou tabulku dostaneme vynech´ an´ım zdvojen´ ych ˇr´adk˚ u. Tu i s obr´ azkem m´ame na obr´ azku 22. A →I II ← III ← IV
a I I IV IV
b III II II I
a I
a
b a
II
b
III
b
a
IV b
Obr´azek 22: Minimalizovan´ y automat. Poznamenejme, ˇze postup uveden´ y v pˇredchoz´ım pˇr´ıkladu se opakuje, dokud nˇekter´a skupina obsahuje r˚ uzn´e ˇr´adky, a skupiny se pouze dˇel´ı, nikdy se nesluˇcuj´ı, i kdyby byly jejich ˇr´adky shodn´e. Poˇcet krok˚ u tohoto algoritmu nelze dobˇre pˇredem odhadnout. Pokud byl p˚ uvodn´ı automat jiˇz minim´aln´ı moˇzn´ y pro dan´ y jazyk, budou se skupin dˇelit, dokud nebude kaˇzd´a obsahovat pouze jeden stav a v´ ysledn´ y automat bude stejn´ y jako automat zadan´ y, pouze budou pˇrejmenovan´e stavy. V´ ysledn´ y automat se naz´ yv´a maxim´ aln´ı faktorizace p˚ uvodn´ıho automatu. Uved’me jej´ı pˇresnou definici: Definice. Bud’ A = (Q, Σ, δ, q0 , F ) koneˇcn´ y automat. Stavy q1 a q2 se naz´ yvaj´ı ekvivalentn´ı
16
˚ 4 MINIMALIZACE AUTOMATU
J. Hora, P. Jedliˇcka
(znaˇc´ıme q1 ∼ q2 ), pokud automaty (Q, Σ, δ, q1 , F ) a (Q, Σ, δ, q2 , F ), pˇrij´ımaj´ı stejn´ y jazyk. Definice. Automat A/ ∼ = (Q/ ∼, Σ, δ/ ∼, [q0 ]∼ , F/ ∼) se naz´ yv´a maxim´ aln´ı faktorizace automatu A. N´ asleduj´ıc´ı vˇeta shrnuje uveden´ y postup minimalizace koneˇcn´eho automatu: Vˇ eta. Maxim´aln´ı faktorizace automatu A pˇrij´ım´ a stejn´ y jazyk jako automat A. Pokud byl automat A dosaˇziteln´ y, je tato maxim´ aln´ı faktorizace minim´aln´ım automatem (vzhledem k poˇctu stav˚ u) pˇrij´ımaj´ıc´ım jazyk L(A). Abychom mohli vyslovit z´ avˇereˇcn´e (a nejd˚ uleˇzitˇejˇs´ı) vˇety teorie koneˇcn´ ych automat˚ u, uvedeme jeˇstˇe dvˇe definice, kter´e zjednoduˇs´ı jejich znˇen´ı. Definice. Dva automaty se naz´ yvaj´ı ekvivalentn´ı, pokud pˇrij´ımaj´ı stejn´ y jazyk. Definice. Automat A se naz´ yv´a redukovan´y, pokud je dosaˇziteln´ y a jeho maxim´ aln´ı faktorizace m´a stejn´ y poˇcet stav˚ u jako automat p˚ uvodn´ı. Vˇ eta. Bud’te A1 a A2 dva redukovan´e automaty pˇrij´ımaj´ıc´ı stejn´ y jazyk. Pak jsou tyto automaty stejn´e aˇz na pˇrejmenov´an´ı stav˚ u. Vˇ eta. Dva automaty jsou ekvivalentn´ı (pˇrij´ımaj´ı stejn´ y jazyk) pr´avˇe tehdy, kdyˇz maxim´ aln´ı faktorizace dosaˇziteln´ ych ˇca´st´ı tˇechto automat˚ u jsou shodn´e aˇz na pˇrejmenov´an´ı stav˚ u. Uveden´e vˇety ˇr´ıkaj´ı, ˇze pro dan´ y jazyk existuje pr´avˇe jeden minim´aln´ı automat, kter´ y jej pˇr´ıj´ım´ a (aˇz na n´ azvy stav˚ u). D´ıky tomu m˚ uˇzeme zjistit, zda dva automaty pˇrij´ımaj´ı stejn´ y jazyk tak, ˇze provedeme jejich minimalizaci a porovn´ ame v´ ysledn´e maxim´ aln´ı faktorizace.
17
