Automaty a jazyky Úvod V historii i v současnosti matematiky a informatiky hrály a hrají důležitou roli předpisy k řešení konkrétních úloh, např. předpisy pro čtyři základní aritmetické operace s přirozenými čísly zapsanými v desítkové soustavě. Předpisy tohoto charakteru se zabýval počátkem devátého století arabský matematik Abdalláh Muhammad ibn Músa, al-Chwárizmí (nebo alChorezmí) al-Madžúsí, latinské zkomolení části jeho jména uvedlo do evropských jazyků slovo algoritmus. Známe-li etymologii slova, neznamená to, že bychom znali jeho význam. Uveďme filosofické vymezení tohoto pojmu. Algoritmem rozumíme přesný předpis, podle kterého máme vykonat v určitém pořadí konečný počet operací, které vedou k řešení každé úlohy či každého problému daného typu. Uveďme několik příkladů známých algoritmů. (1) Výše zmíněné čtyři základní aritmetické operace s přirozenými čísly zapsané v desítkové číselné soustavě (nebo v soustavě o jiném základu, např. 2). (2) Stará čínská matematika měla pro řešení nejrůznějších typů úloh zásobu algoritmů, které byly pečlivě předávány z generace na generaci. Ke zjištění, zda přirozené číslo n je prvočíslo, měli čínští matematici jednoduchý algoritmus – stačilo zjistit, zda číslo n dělí beze zbytku číslo 2n – 2. Pokud ano, jde o prvočíslo, pokud je zbytek nenulový, jde o číslo složené. Tento algoritmus má jeden kaz, na který staří Číňané nepřišli – jde o nesprávný algoritmus. Nejmenší číslo, které dává chybnou odpověď, je 341, protože číslo 2341 – 2 je dělitelné číslem 341, ale 341 = 11 . 31, tzn. 341 není prvočíslo, ale číslo složené. Existuje obrana proti takovým nepříjemným překvapením? Odpověď nalezneme, srovnáme-li matematické tradice staré Číny se starou řeckou matematikou. V Číně se uvedl předpis a dále se nezkoumal, tj. zasvěcenec předal algoritmus zasvěcenci („program přehrál z paměti do paměti“) a ten jej začal používat. V antickém Řecku následovala ještě fáze – proč algoritmus skutečně dělá to, co se tvrdí? Tj. algoritmus doprovázel důkaz1. (3) Již ve starověku známý Euklidův algoritmus popsat takto: Jsou-li m a n kladná přirozená čísla, potom největšího společného dělitele čísel m a n určíme v následujících postupných krocích. 1. krok – dělme číslo m číslem n. Zbytek dělení označme r (0 ≤ r < n). 2. krok – je-li r = 0, potom n je největší společný dělitel; je-li r > 0, potom pokračujme třetím krokem. 3. krok – dosaďme za m číslo n a za n číslo r a opakujme postup od prvního kroku. Vymezení pojmu algoritmus, které jsme uvedli, slouží jako vodítko pro vyšetření, zda konkrétní předpis je algoritmus. Možnosti takové „definice“ jsou z hlediska matematiky a informatiky nedostatečné. Problematika automatů a formálních jazyků, jimž je věnována tato kapitola, patří mezi nejdéle studované a nejpodrobněji zpracované disciplíny tvořící matematickou informatiku. Dosažené výsledky se uplatňují nejen při návrhu počítačů, ale i např. při studiu živých organismů. Uveďme některé základní pojmy. X je abeceda, jestliže X je konečná neprázdná množina symbolů, tj. X = {a1, a2, a3, a4,…, an}. Symbolem ε označíme prázdný symbol. Některé abecedy mohou obsahovat i tento symbol. Slovem v abecedě X rozumíme libovolný konečný řetězec sestavený ze symbolů abecedy X, počet členů tohoto řetězce nazýváme délkou slova. Uvažujeme i prázdné slovo (tj. slovo délky 1
Tento algoritmus sebou nese poučení, jehož důležitost snad ani nelze dostatečně zdůraznit – i algoritmus, který byl dlouhou dobu používán a testován, může být špatný. A to natolik špatný, že nejrozumnější náprava je jej zahodit a hledat jiný algoritmus.
0), které označujeme Λ. Slovo A je podslovem slova B v abecedě X, jestliže slovo A tvoří souvislý řetězec ve slově B. Jsou-li A a B slova v abecedě X, potom zřetězením slov A a B rozumíme slovo AB. Jsou-li a a b symboly abecedy X, potom symbolem a2b3 označuje slovo aabbb. Symbolem X* označíme množinu všech slov v abecedě X a symbolem X+ označíme množinu všech neprázdných slov v abecedě X, tj. X* = X+ U {Λ} a X* – {Λ} = X+. Je-li X abeceda, potom L nazveme jazykem nad abecedou X, jestliže L je podmnožinou množiny X*. Ve smyslu tohoto označení je každý přirozený jazyk, např. i čeština, jazykem nad abecedou. Řetězce tohoto jazyka jsou všechny správně utvořené české věty. Do příslušné abecedy patří kromě všech symbolů české abecedy ještě všechna interpunkční znaménka a mezera (tj. prázdný symbol ε). Jiným typem objektů, které je užitečné zkoumat aparátem formálních jazyků, jsou programovací jazyky – řetězcem v příslušném jazyku je zpravidla každý syntakticky správný program v příslušném jazyku. Automaty Teorie automatů vznikla primárně z impulsů nematematických. Samotný název automat nebo adjektivum automatický označuje objekt nebo činnost, která probíhá v jednoduchých krocích, které se opakují při řešení téže úlohy. Teorie automatů vznikla v rámci kybernetiky a přinesla do matematiky nový pohled na různé problémy. Vývoj vedl k tomu, že se do středu zájmu dostaly partie, které dříve stály na okraji. Již ve starověku Herón Alexandrijský (žil nejspíše v 1. stol. n. l.), zvaný Méchanikos, zkonstruoval automat na prodej „svěcené vody“ a automat na otvírání chrámových dveří. Tyto mechanismy měly stejný funkční princip jako moderní prodejní automaty, tj. bezprostředně po vhození vhodné mince vydaly příslušné množství vody nebo otevřely dveře. Simulovaly nejjednodušší reakce organismů – nepodmíněné reflexy. Teorie automatů vznikla ve třicátých letech dvacátého století. V r. 1936 definoval Turing stroj, který se dnes nazývá Turingův stroj. Z dnešního hlediska jde o automat s nekonečnou pamětí. My se budeme věnovat automatům s pamětí konečnou. V r. 1943 americký fyziolog McCulloch a americký matematik Pitts vytvořili idealizovaný model neuronové sítě, který je v jistém smyslu předobrazem automatu. Po r. 1950 vyšly první práce, ve kterých byl definován konečný automat, touto problematikou se zabývali mj. Mealy a Moore. Od té doby se teorie automatů rozvíjela někdy i velmi bouřlivým tempem. Automaty můžeme zkoumat ze dvou hledisek – strukturálního a behavioristického. Zkoumáme-li automat ze strukturálního hlediska, pak nás zajímá, z čeho je sestrojen, tj. jaké součástky jsme při jeho výstavbě použili. Zajímalo by nás také jak minimalizovat množství součástek, aby zařízení vykonávalo právě činnost, kterou si představujeme. Vyšetřujeme-li automat z hlediska behavioristického2, zajímá nás jiná situace – prostředí obklopující automat působí na něj prostřednictvím několika vstupních kanálů, automat na vstupní signály reaguje a vydává výstupními kanály výstupní signály, jimiž zpětně působí na okolní prostředí. Jde o to věnovat se závislosti mezi vstupními a výstupními signály (zkráceně vstupy a výstupy). Při našem zkoumání vyjdeme z behavioristického hlediska (viz obr. 1). vstupní kanály
automat
výstupní kanály
Obr. 1.
2
Ze slova behaviour v britské angličtině nebo behavior v americké angličtině, které znamená chování.
Otázky tohoto typu se někomu mohou zdát na první pohled umělé. To je způsobeno jistou dosti vžitou, ale mylnou představou o automatech. Podle této povrchní představy je automat charakterizován právě tím, že vztah mezi vstupem a výstupem je velmi jednoduchý, např. - vhodíme minci, vypadne krabička s filmem; - vhodíme minci a restauraci zaplaví ryčná hudba; - rozbijeme výlohu, začne houkat siréna atd. Podobně se tvrdívá, že jeden z rozdílů mezi automatem a živým organismem lze charakterizovat tím, že automat reaguje na stejné podněty stále stejně, zatímco reakce živého organismu se na tytéž podněty měnívá. V učebnicích psychologie najdeme schéma uvedené na obr. 2. Reakce organismu je spoluurčena ještě dalším faktorem, jímž je „intervenující“ proměnná. O vztahu mezi podnětem a reakcí např. u prodejních automatů není potřeba dlouze uvažovat. Vztahy určené druhým z uvedených schémat jsou alespoň v nějaké formě předmětem každodenních úvah každého z nás. Již v útlém věku pozorujeme, že druzí lidé reagují na stejné podněty za různých okolností různě a to za okolností, které se navzájem liší různým „stavem“ (náladou, novými zkušenostmi, únavou apod.) reagujícího člověka. Jinak reaguje otec na první synovu pětku, jinak na pátou pětku. Jinak reaguje člověk (ve většině případů) na první sklenku vína než na šestou. Jinak reaguje člověk v tramvaji na větu z tlampače: Vystupte si, zatahujeme!, slyší-li ji poprvé v daném dnu, než když ji slyší tentýž den počtvrté. Mnohdy je pro nás důležité uhodnout, jak druhý reaguje na opakovaný podnět (Řekni to ještě jednou!). Bylo to právě chování člověka a chování živých organismů, které daly impuls k rozvoji teorie automatů. I Turing navrhl své stroje tak, že je definoval na základě analýzy činnosti živého výpočtáře, který pracuje algoritmicky. podnět
reakce organismu
intervenující
reakce
proměnná
Obr. 2. Růst významu samočinných počítačů jako impulsu k rozvoji teorie automatů je daleko pozdějšího data. V dnešní době otázky, které souvisejí s počítači, zaujímají v teorii automatů centrální postavení. Svůj význam si ovšem podržely i otázky biologicky motivované (celulární automaty, otázky samoreprodukce automatů, modely zkoumání růstu jednoduchých organismů atp.). Na konci 20. stol. nabyly na důležitosti i aplikace teorie automatů ve společenskovědních oborech (stabilita systémů). O automatech, kterými se budeme zabývat, lze obecně říci: (a) Vstupní signály takového automatu budou prvky nějaké abecedy X (tzv. vstupní abecedy). Budeme hovořit o vstupních symbolech. (b) Výstupní signály (výstupní symboly) budou prvky abecedy Y (tzv. výstupní abecedy). (c) Automat bude pracovat v diskrétní časové škále t0, t1, t2, … V každém časovém okamžiku bude na vstupu jeden symbol ze vstupní abecedy X a automat vydá jeden symbol z výstupní abecedy Y. V dalším budeme časové okamžiky značit přirozenými čísly 0, 1, 2, … Okamžik t+1 označuje časový okamžik následující bezprostředně po časovém okamžiku t. (d) Reakce automatu bude určena obdrženým vstupním signálem a vnitřním stavem, ve kterém se automat nachází. (e) Předpokládáme, že se automat může nacházet v konečně mnoha vnitřních stavech.
Konečné automaty Mealyho automatem3 (nebo automatem) rozumíme uspořádanou šestici A = [Q, X, Y, q0, δ, λ], kde Q je neprázdná konečná množina vnitřních stavů, X je vstupní abeceda, Y je výstupní abeceda, q0 je počáteční vnitřní stav (q0 є Q), δ je zobrazení nazývané přechodová funkce, která všem vnitřním stavům a všem prvkům vstupní abecedy přiřazuje vnitřní stavy, λ je zobrazení nazývané výstupní funkce, která všem vnitřním stavům a všem prvkům vstupní abecedy přiřazuje prvky výstupní abecedy. 1. příklad Uvažujme automat A takový, že Q = {q0, q1, q2}, kde q0 je počáteční vnitřní stav, vstupní abeceda X = {0, 1}, výstupní abeceda Y = {a, b}, přechodová funkce δ je definována δ(q0,0) = q1, δ(q1,0) = q2, δ(q0,1) = q0, δ(q1,1) = q0, výstupní funkce λ je definována λ(q0,0) = b, λ(q0,1) = b,
δ(q2,0) = q2, δ(q2,1) = q2,
λ(q1,0) = b, λ(q1,1) = b,
λ(q2,0) = a, λ(q2,1) = a.
Tento automat lze reprezentovat několika způsoby. (1) Tabulkami přechodové a výstupní funkce, tj. δ q0 q1 q2
0 q1 q2 q2
1 q0 q0 q2
λ q0 q1 q2
0 b b a
1 b b a
(2) Smíšenou tabulkou pro přechodovou a výstupní funkci δ, λ 0 1 q0 q1, b q0, b q1 q2, b q0, b q2 q2, a q2, a (2) Stavovým diagramem, což je orientovaný pojmenovaný multigraf, jehož vrcholy tvoří vnitřní stavy, orientovaná hrana z vrcholu q do vrcholu q’ označená c/d vyjadřuje hodnotu přechodové funkce δ(q, c) = q’ a λ(q, c) = d, kde c je prvek vstupní abecedy a d je prvek výstupní abecedy (viz obr. 3). Předpokládáme, že automat přijímá vstupní slovo od konce. Mějme např. vstupní slovo 0100101101, které lze také zapsat 0102101201. Automat A začíná svou činnost v počátečním vnitřním stavu q0. Označme symbolem t časový okamžik, x(t) vstupní symbol v okamžiku t, δ(t) vnitřní stav automatu v okamžiku t a λ(t) výstupní symbol v okamžiku t. V čase t = 0 je automat A v počátečním vnitřním stavu q0 a na vstupu je poslední znak vstupního slova 1. V čase t = 1 automat zpracuje vstupní symbol 1 a vydá výstupní symbol λ(1) = λ(q0, 1) = b (což je poslední znak výstupního slova), přejde do vnitřního stavu δ(1) = δ(q0, 1) = q0. a na vstupu se objeví předposlední znak vstupního slova 0. 3
Také se používá termín konečný automat nebo konečný sekvenční stroj nebo krátce stroj.
V čase t = 2 automat zpracuje vstupní symbol 0 a vydá výstupní symbol λ(2) = λ(q0, 0) = b (což je předposlední znak výstupního slova), přejde do vnitřního stavu δ(2) = δ(q0, 0) = q1. a na vstupu se objeví další znak vstupního slova 1. V tabulce můžeme zapsat t 0 1 2 x(t) 1 0 1 δ(t) q0 q0 q1 λ(t) b b V dalších časových okamžicích budeme postupovat analogicky až v čase t = 9 bude na vstupu první znak vstupního slova 0, automat bude ve vnitřním stavu q2 a dostaneme se do časového okamžiku t = 10, vydá výstupní symbol λ(10) = λ(q2, 0) = a (což je první znak výstupního slova), přejde do vnitřního stavu δ(10) = δ(q2, 0) = q2. Zpracování celého vstupního slova můžeme zapsat v tabulce t 0 1 2 3 4 5 6 7 8 9 10 x(t) 1 0 1 1 0 1 0 0 1 0 δ(t) q0 q0 q1 q0 q0 q1 q0 q1 q2 q2 q2 λ(t) b b b b b b b b a a Výstupní slovo je aabbbbbbbb (i výstupní slovo je vydáváno od konce), které lze také zapsat a2b8. Všimněme si, že pro automat A platí – dostane-li se do vnitřního stavu q2, potom jej už neopustí a ve vnitřním stavu q2 začne vydávat samá a. Slovy lze popsat chování automatu A takto – automat vydává symbol b tak dlouho, dokud není ve vstupním slovu dvakrát za sebou symbol 0, od takového okamžiku vydává pouze symbol a.□ 0/b
q0
q1
1/b 1/b 0/b
q2 1/a
0/a Obr. 3.
Poznamenejme, že platí – je-li úloha řešitelná automatem, je také algoritmicky řešitelná (tj. existuje algoritmus, který ji řeší). Opačné tvrzení obecně neplatí – existují algoritmicky řešitelné úlohy, které nejsou řešitelné automaty. Mějme automat A = [Q, X, Y, q0, δ, λ]. Indukcí definujeme zobecněnou přechodovou funkci δ+ a zobecněnou výstupní funkci λ+: (a) Pro libovolný vnitřní stav q z Q a pro libovolný vstupní symbol x z X je δ+ + (q, x) = δ(q, x) a λ (q, x) = λ(q, x). (b) Pro libovolný vnitřní stav q z Q, pro libovolný vstupní symbol x z X a pro libovolné slovo P z X + je δ+(q, xP) = δ(δ+(q, P), x) a λ+(q, xP) = λ(δ+(q, P), x). 2. příklad Uvažujme automat A z 1. příkladu. Určíme postupně δ+(q0, 0102101201) i λ+(q0, 0102101201). δ+(q0, 1) = δ(q0, 1) = q0, λ+(q0, 1) = λ(q0, 1) = b; δ+(q0, 01) = δ(δ+(q0, 1), 0) = δ(δ(q0, 1), 0) = δ(q0, 0) = q1,
λ+(q0, 01) = λ(δ+(q0, 1), 0) = λ(δ(q0, 1), 0) = λ(q0, 0) = b; δ+(q0, 101) = δ(δ+(q0, 01), 1) = δ(q1, 1) = q0, λ+(q0, 101) = λ(δ+(q0, 01), 1) = λ(q1, 1) = b; δ+(q0, 1101) = δ(δ+(q0, 101), 1) = δ(q0, 1) = q0, λ+(q0, 1101) = λ(δ+(q0, 101), 1) = λ(q0, 1) = b; δ+(q0, 01101) = δ(δ+(q0, 1101), 0) = δ(q0, 0) = q1, λ+(q0, 01101) = λ(δ+(q0, 1101), 0) = λ(q0, 0) = b; δ+(q0, 101101) = δ(δ+(q0, 01101), 1) = δ(q1, 1) = q0, λ+(q0, 101101) = λ(δ+(q0, 01101), 1) = λ(q1, 1) = b; δ+(q0, 0101101) = δ(δ+(q0, 101101), 0) = δ(q0, 0) = q1, λ+(q0, 0101101) = λ(δ+(q0, 101101), 0) = λ(q0, 0) = b; δ+(q0, 00101101) = δ(δ+(q0, 0101101), 0) = δ(q1, 0) = q2, λ+(q0, 00101101) = λ(δ+(q0, 0101101), 0) = λ(q1, 0) = b; δ+(q0, 100101101) = δ(δ+(q0, 00101101), 1) = δ(q2, 1) = q2, λ+(q0, 100101101) = λ(δ+(q0, 00101101), 1) = λ(q2, 1) = a; δ+(q0, 0100101101) = δ(δ+(q0, 100101101), 0) = δ(q2, 1) = q2, λ+(q0, 0100101101) = λ(δ+(q0, 100101101), 0) = λ(q2, 1) = a. □ Je zřejmé, že hodnotou zobecněné výstupní funkce λ+(q, P) je první znak výstupního slova, který vydá automat začínající činnost ve vnitřním stavu q a zpracovávající neprázdné slovo P.
x(t) δ
q(t+1)
Z
λ
y(t+1)
Z
y(t)
q (t)
Obr. 4 Na obr. 4. je uvedena interpretace Mealyho automatu z hlediska časové závislosti. Symbolem δ je označeno zařízení realizující přechodovou funkci δ, symbolem λ zařízení realizující výstupní funkci λ a symbolem Z zpožďovací člen, který vydává příslušný symbol o jeden časový okamžik později. Půjde nám o to zkonstruovat nejúspornější automaty, tzn. automaty, které mají nejméně vnitřních stavů a řeší stejnou úlohu nebo stejný problém. Mějme automat A = [Q, X, Y, q0, δ, λ]. Vnitřní stav q nazveme dosažitelný, jestliže q = q0 nebo existuje neprázdné slovo P ze vstupní abecedy X takové, že δ+( q0, P) = q. Jestliže není vnitřní stav dosažitelný, nazývá se nedosažitelný. 3. příklad Uvažujme automat A takový, že Q = {q0, q1, q2, q3}, kde q0 je počáteční vnitřní stav, vstupní abeceda X = {a, b} a výstupní abeceda Y ={0, 1}, který je definován smíšenou tabulkou δ, λ a b q0 q1, 0 q0, 0 q1 q1, 0 q3, 0
q2 q1, 0 q3, 0 q3 q1, 0 q0, 0 Vnitřní stavy q0, q1 a q3 jsou dosažitelné a vnitřní stav je q2 nedosažitelný, protože (a) počáteční vnitřní stav q0 je vždy dosažitelný, (b) δ(q0, a) = δ+(q0, a) = q1, (c) δ+(q0, ba) = δ(δ+( q0, a), b) = δ(δ(q0, a), b) = δ(q1, b) = q3 a (d) do vnitřního stavu q2 se ze počátečního vnitřního stavu q0 nedostaneme žádným neprázdným slovem ze vstupní abecedy, neboť nefiguruje v žádné buňce smíšené tabulky. □ Mějme automaty A = [Q, X, Y, q0, δ, λ] a A1 = [1Q, X, Y, 1q0, 1δ, 1λ]. (1) Je- li q vnitřní stav automatu A a 1q vnitřní stav automatu A1, potom vnitřní stavy q a 1 q jsou behavioristicky ekvivalentní nebo b-ekvivalentní (což označíme q ≈ 1q), jestliže pro všechna slova P z X+ platí λ+(q, P) = 1λ+(1q, P). (2) Automaty A a A1 jsou behavioristicky ekvivalentní nebo zkráceně b-ekvivalentní (což označíme A ≈ A1), jestliže (a) q0 ≈ 1q0, (b) ke každému vnitřnímu stavu q automatu A a existuje vnitřní stav 1q automatu A1 takový, že q ≈ 1q a (c) ke každému vnitřnímu stavu 1q automatu A1 a existuje vnitřní stav q automatu A takový, že 1q ≈ q. Je-li A = [Q, X, Y, q0, δ, λ] automat a je-li S množina všech dosažitelných vnitřních stavů automatu A (tj. S je podmnožina množiny Q), potom automat B = [S, X, Y, q0, δ, λ], kde δ (resp. λ) je přechodová (resp. výstupní) funkce vytvořená z funkce δ (resp. λ) tak, že vynecháme nedosažitelné vnitřní stavy v definičním oboru, B ≈ A, přičemž automat B neobsahuje nedosažitelné vnitřní stavy. Jak zkonstruovat b-ekvivalentní automat, který neobsahuje žádný nedosažitelný vnitřní stav? Jestliže množina vnitřních stavů automatu A obsahuje právě vnitřní stavy q0, q1,…, qn , stačí vzít všechna neprázdná slova P ve vstupní abecedě, jejichž délka je maximálně n a množinu všech vnitřních stavů automatu B tvoří (a) počáteční vnitřní stav q0, (b) všechny vnitřní stavy q’ automatu A, pro které platí δ+( q0, P) = q’. 4. příklad Uvažujme automat A z 3. příkladu. Automat A má čtyři vnitřní stavy, vypišme všechna neprázdná slova ve vstupní abecedě, jejichž délka je 3: a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba a bbb. Potom δ+(q0, a) = q1, δ+(q0, b) = q0, δ+(q0, aa) = q1, δ+(q0, ab) = q1, δ+(q0, ba) = q3, δ+(q0, bb) = q0, δ+(q0, aaa) = q1, δ+(q0, aab) = q1, δ+(q0, aba) = q0, δ+(q0, abb) = q1, δ+(q0, baa) = q3, δ+(q0, bab) = q3, δ+(q0, bba) = q3, δ+(q0, bbb) = q0. Tudíž množina všech vnitřních stavů automatu B je S = {q0, q1, q3} a smíšená tabulka má tvar δ, λ a b q0 q1, 0 q0, 0 q1 q1, 0 q3, 0 q3 q1, 0 q0, 0 □ Realizace Mealyho automatů Booleovskou funkcí n proměnných (kde n je kladné přirozené číslo) rozumíme funkci f, která všem slovům v abecedě {0, 1} délky n přiřazuje buď 0, nebo 1. 5. příklad Definujme funkci f předpisem
f(000) = 0, f(001) = 0, f(010) = 0, f(011) = 1, f(100) = 0, f(101) = 1, f(110) = 0, f(111) = 0. Jde o booleovskou funkci tří proměnných. □ Booleovská funkce n proměnných představuje pravdivostní ohodnocení výrokové formule v disjunktivní normální formě s výrokovými proměnnými x1, x2, … , xn. 6. příklad Vraťme se k 5. příkladu. Funkční hodnotě f(011) = 1 odpovídá formule ─┐x1 Λ x2 Λ x3 a funkční hodnotě f(101) = 1 odpovídá formule x1 Λ ─┐x2 Λ x3, tudíž celé funkci f odpovídá formule (─┐x1 Λ x2 Λ x3 ) v (x1 Λ ─┐x2 Λ x3). kde x1, x2 a x3 jsou výrokové proměnné.□ Jestliže vstupní i výstupní abeceda obsahují jiné prvky než 0 a 1, je možné symboly těchto abeced zakódovat pomocí slov v abecedě {0, 1}. Podobně můžeme zakódovat i vnitřní stavy automatu. 7. příklad Uvažujme automat A takový, že Q = {q0, q1, q2}, kde q0 je počáteční vnitřní stav, vstupní abeceda X = {a, b, c} a výstupní abeceda Y = {0, 1}, který je definován smíšenou tabulkou δ, λ q0 q1 q2
a q0, 0 q0, 0 q1, 0
b q1, 0 q1, 1 q1, 1
c q1, 0 q2, 1 q2, 1
Prvním krokem je zakódování vstupních symbolů a vnitřních stavů, výstupním symbolům ponecháme v tomto případě jejich binární hodnoty. Vstupní symbol a zakódujeme slovem 00, b slovem 01 a c slovem 11, podobně počáteční vnitřní stav q0 zakódujeme slovem 00, vnitřní stav q1 slovem 10 a stav q2 slovem 11. Obecně může být volba kódování určena dodatečnými vnějšími požadavky na navrhovaný systém, nebo může být ponechána na libovůli návrháře. Ke kódování n-prvkové množiny je třeba volit slova délky k, kde k je nejmenší přirozené číslo takové, že n ≤ 2k. Jestliže n není mocninou dvojky, budou některá slova délky k nevyužita. V našem případě bude smíšená tabulka δ, λ 00 01 10 11
00 00, 0 00, 0 10, 0
01 10, 0 10, 1 10, 1
10 -
11 10, 0 11, 1 11, 1
Prázdná políčka v tabulce vyznačují hodnoty přechodové a výstupní funkce nejsou výchozím zadáním určeny, proto je možné je vyplnit libovolně. Jedno z možných doplnění je toto: δ, λ 00 01 10 11
00 00, 0 10, 0 00, 0 10, 0
01 10, 0 10, 0 10, 1 10, 1
10 00, 0 10, 0 01, 0 11, 0
11 10, 0 10, 0 11, 1 11, 1
Výstupní funkce je booleovská funkce čtyř proměnných, kterou lze zapsat λ (q1, q2, x1, x2). Metody umožňující co možná nejmenší kombinační sítě pro realizaci dané booleovské funkce podrobně rozpracovány, ale přesahují trámec našeho kursu. Spokojme se schématem výsledného sekvenčního obvodu na obrázku 5., kde symbolem Λ je označeno zařízení
realizující konjunkci, symbolem v zařízení realizující disjunkci a symbolem Z je označen zpožďovací člen. Samozřejmě změnou kódování i změnou v doplňování neurčených hodnot dostáváme odlišnou realizaci, která se může podstatně lišit složitostí kombinačních sítí pro přechodovou i výstupní funkci. □ x1
Λ
x2 v
Z Z y
Λ
Obr. 5 Mooreovy automaty Uvedeme dva speciální typy automatů, které jsou vhodné pro řešení některých typů problémů. Mějme automat A = [Q, X, Y, q0, δ, λ]. A je Mooreův automat 1. typu, jestliže existuje zobrazení ν takové, že pro všechna q z množiny vnitřních stavů Q a pro všechny vstupní symboly x z X je λ(q, x) = ν(q). Mooreův automat 1. typu A zapisujeme A = [Q, X, Y, q0, δ, ν] a zobrazení ν nazýváme značkovací funkce. Na stavovém diagramu snadno rozeznáme Mooreův automat 1. typu tak, že všechny hrany vystupující z jednoho uzlu mají stejný výstupní symbol. 5. příklad Automat A z 1. příkladu je Mooreův automat 1. typu. Stačí definovat značkovací funkci ν takto: ν(q0) = λ(q0,0) = λ(q0,1) = b, ν(q1) = λ(q1,0) = λ(q1,1) = b, ν(q2) = λ(q2,0) = λ(q2,1) = a.□
x(t) δ
q (t+1)
Z
q(t)
Obr. 6
ν
y(t)
Na obr. 6. je uvedena interpretace Mooreova automatu 1. typu z hlediska časové závislosti. Symbolem δ je označeno zařízení realizující přechodovou funkci δ, symbolem ν zařízení realizující značkovací funkci ν a symbolem Z zpožďovací člen, který vydává příslušný symbol o jeden časový okamžik později. Pro Mooreovy automaty 1. typu lze rozšířit zobecněnou přechodovou i zobecněnou výstupní funkci i na prázdné slovo, nebudeme je uvádět, vzhledem k tomu, že pro naše účely jsou nepotřebné. Mějme automat A = [Q, X, Y, q0, δ, λ]. A je Mooreův automat 2. typu, jestliže existuje zobrazení μ takové, že pro všechna q z množiny vnitřních stavů Q a pro všechny vstupní symboly x z X je λ(q, x) = μ(δ(q, x)). Mooreův automat 2. typu A zapisujeme A = [Q, X, Y, q0, δ, μ] a zobrazení ν nazýváme značkovací funkce. Na stavovém diagramu snadno rozeznáme Mooreův automat 2. typu tak, že všechny hrany vstupující do jednoho uzlu mají stejný výstupní symbol. 8. příklad Uvažujme automat A takový, že Q = {q0, q1, q2}, kde q0 je počáteční vnitřní stav, vstupní abeceda X = {0, 1}, výstupní abeceda Y = {a, b}, který je reprezentován smíšenou tabulkou pro přechodovou a výstupní funkci δ, λ 0 1 q0 q2, b q1, b q1 q2, a q0, a q2 q1, b q2, a Tento automat je Mooreovým automatem 2. typu se značkovací funkcí μ definovanou předpisem μ(q0) = a, μ(q1) = b, μ(q2) = b. Každý snadno ověří, že takto definovaná značkovací funkce vyhovuje požadavkům na Mooreovy automaty 2. typu. Automat je možné jednodušeji reprezentovat tabulkou δ 0 1 μ q0 q2 q1 a q1 q2 q0 b q2 q1 q2 b kterou budeme nazývat mooreovská tabulka tohoto automatu. □
x(t)
q(t+1)
δ
q(t)
μ
y(t)
Z
Obr. 7 Na obr. 7. je uvedena interpretace Mooreova automatu 2. typu z hlediska časové závislosti. Symbolem δ je označeno zařízení realizující přechodovou funkci δ, symbolem μ zařízení
realizující značkovací funkci μ a symbolem Z zpožďovací člen, který vydává příslušný symbol o jeden časový okamžik později. I pro Mooreovy automaty 2. typu lze rozšířit zobecněnou přechodovou i zobecněnou výstupní funkci i na prázdné slovo. Uveďme, jak jsou tyto funkce definovány. Mějme Mooreův automat 2. typu A = [Q, X, Y, q0, δ, λ] se značkovací funkcí μ. Indukcí definujeme zobecněnou přechodovou funkci δ* a zobecněnou výstupní funkci λ* (a) Pro libovolný vnitřní stav q z Q a pro libovolný vstupní symbol x z X je δ*(q, Λ) = q a λ*(q, Λ) = μ(q). (b) Pro libovolný vnitřní stav q z Q a pro libovolné slovo P z X + je δ*(q, P) = δ+(q, P) a λ*(q, P) = λ+(q, P). Z hlediska technické realizace jsou Mooreovy automaty 2. typu důležitější než Mealyho automaty i Mooreovy automaty 1. typu. Mealyho automaty jsou výhodnější pro řešení většiny úloh. Zdá se, že Mooreovy automaty 1. i 2. typu řeší méně úloh než Mealyho automaty. Položme si otázku, zda umí Mealyho automaty a Mooreovy automaty 2. typu řešit stejné úlohy. Protože Mooreovy automaty 1. a 2. typu jsou Mealyho automaty, potom každá úloha řešená Mooreovými automaty je řešitelná Mealyho automaty. Ukáže se, že ke každému Mealyho automatu lze zkonstruovat Mooreův automat 2.typu, který řeší stejnou úlohu. Platí: Ke každému Mealyho automatu A existuje Mooreův automat 2. typu M takový, že A ≈ M. Jak zkonstruovat k Mealyho automatu b-ekvivalentní Mooreův automat 2. typu? Vezme-li smíšenou tabulku Mealyho automatu, ve kterém je vnitřní stav qi v různých buňkách spojen např. s právě třemi výstupními symboly a, b a c, rozdělíme vnitřní stav qi na tři různé vnitřní stavy qi,a, qi,b a qi,c. Je-li vnitřní stav qi spojen s jediným nebo žádným výstupním symbolem, potom vnitřní stav qi ponecháme. Hodnoty značkovací funkce μ pro jednotlivé vnitřní stavy budou výstupní symboly, pokud je vnitřní stav ve smíšené tabulce spojen s výstupním symbolem, a náhodně vybraný výstupní symbol, pokud vnitřní stav není spojen s žádným výstupním symbolem. Zbývá ještě jeden problém. Který vnitřní stav zvolit jako počáteční? Počátečním stavem Mooreova automatu 2. typu můžeme zvolit (v případě, že se počáteční vnitřní stav q0 rozdělí na více vnitřních stavů) kterýkoli vnitřní stav, který vznikl ze stavu q0. 9. příklad Uvažujme automat A takový, že Q = {q0, q1, q2}, kde q0 je počáteční vnitřní stav, vstupní abeceda X = {0, 1} a výstupní abeceda Y = {a, b}, který je definován smíšenou tabulkou δ, λ 0 1 q0 q1, b q0, b q1 q2, b q0, b q2 q2, a q2, a K tomuto automatu sestrojíme b-ekvivalentní Mooreův automat 2. typu M. Jediný vnitřní stav, který nevyhovuje definici Mooreova automatu 2. typu, je vnitřní stav q2 (viz buňky smíšené tabulky se žlutým pozadím). Z vnitřního stavu q2 vzniknou dva vnitřní stavy q2,a a q2,b. Smíšená tabulka automatu M je δ, λ 0 1 q0 q1, b q0, b q1 q2,b, b q0, b q2,a q2,a, a q2,a, a q2,b q2,a, a q2,a, a
Uděláme-li mooreovskou tabulku se značkovací funkcí μ, má tabulka tvar δ 0 1 μ q0 q1 q0 b q1 q2,b q0 b q2,a q2,a q2,a a q2,b q2,a q2,a b □ 10. příklad Uvažujme automat A takový, že Q = {q0, q1, q2, q3, q4, q5}, kde q0 je počáteční vnitřní stav, vstupní abeceda X = {a, b, c} a výstupní abeceda Y = {0, 1}, který je definován smíšenou tabulkou δ, λ a b c q0 q2, 1 q1, 0 q1, 1 q1 q2, 0 q0, 0 q3, 0 q2 q1, 1 q3, 1 q4, 0 q3 q2, 0 q4, 1 q0, 1 q4 q5, 1 q2, 1 q4, 1 q5 q5, 1 q5, 1 q4, 1 Sestrojíme b-ekvivalentní Mooreův automat 2. typu. Ze smíšené tabulky je zřejmé, že definici Mooreova automatu 2. typu neodpovídají všechny vnitřní stavy kromě q5, které se všechny rozpadnou na dva vnitřní stavy qi,0 a qi,1 pro i = 0, 1, 2, 3 a 4. Jako počáteční vnitřní stav zvolíme q0,0. Mooreovská tabulka b-ekvivalentního Mooreova automatu 2. typu je δ a b c μ q0,0 q2,1 q1,0 q1,1 0 q0,1 q2,1 q1,0 q1,1 1 q1,0 q2,0 q0,0 q3,0 0 q1,1 q2,0 q0,0 q3,0 1 q2,0 q1,1 q3,1 q4,0 0 q2,1 q1,1 q3,1 q4,0 1 q3,0 q2,0 q4,1 q0,1 0 q3,1 q2,0 q4,1 q0,1 1 q4,0 q5 q2,1 q4,1 0 q4,1 q5 q2,1 q4,1 1 q5 q5 q5 q4,1 1 □ Již jsme uvedli, že budeme automaty minimalizovat tak, aby neobsahovaly zbytečné vnitřní stavy. První stavy, které jsme označili za zbytečné, byly nedosažitelné vnitřní stavy. Dalšími typy stavů, které jsou z hlediska výpočtu zbytečné, jsou vnitřní stavy, které stejným výstupem reagují na stejná slova vstupní abecedy. Mějme Moreovy automaty 2. typu A = [Q, X, Y, q0, δ, λ] a A1 = [1Q, X, Y, 1q0, 1δ, 1λ]. (1) Je- li q vnitřní stav automatu A a 1q vnitřní stav automatu A1, potom vnitřní stavy q a 1 q jsou mooreovsky ekvivalentní nebo m-ekvivalentní (což označíme q ≈ 1q), jestliže pro všechna slova P ze vstupní abecedy4 X platí λ*(q, P) = 1λ*(1q, P). (2) Automaty A a A1 jsou mooreovsky ekvivalentní nebo zkráceně m-ekvivalentní (což označíme A ≈ A1), jestliže (a) q0 ≈ 1q0, 4
Tj. včetně prázdného slova Λ.
(b) ke každému vnitřnímu stavu q automatu A a existuje vnitřní stav 1q automatu A1 takový, že q ≈ 1q a (c) ke každému vnitřnímu stavu 1q automatu A1 a existuje vnitřní stav q automatu A takový, že 1q ≈ q. Poznamenejme, že předcházející definici lze použít i v případě A = A1, tj. lze hovořit i o mekvivalenci vnitřních stavů jednoho Mooreova automatu 2. typu. Mějme Moreovy automaty 2. typu A = [Q, X, Y, q0, δ, λ] a A1 = [1Q, X, Y, 1q0, 1δ, 1λ]. Řekneme, že A1 je redukt automatu A, jestliže (a) A1 neobsahuje nedosažitelné vnitřní stavy, (b) Pro libovolné vnitřní stavy q a q’ automatu A1 platí: jestliže q ≈ q’, potom q = q’ a (c) A1 ≈ A. Jak sestrojit redukt Mooreova automatu 2. typu A = [Q, X, Y, q0, δ, λ] se značkovací funkcí μ? (1) Odstraníme nedosažitelné vnitřní stavy. (2) Použijeme algoritmus redukce5, tj. (a) pro každý vnitřní stav q automatu A vytvoříme množinu r0(q) takovou, že obsahuje všechny vnitřní stavy q’ takové, že μ(q) = μ(q’), vznikne množina R0 = { r0(q); q є Q}, která obsahuje množiny vnitřních stavů se stejnou hodnotou značkovací funkce, tzn. počet prvků množiny R0 je maximálně roven počtu prvků výstupní abecedy; (b) předpokládáme, že jsme pro libovolné přirozené číslo6 k sestrojili množiny rk(q) pro libovolný vnitřní stav q automatu A a množinu Rk = { rk(q); q є Q}. Sestrojíme množiny rk+1(q) pro libovolný vnitřní stav q automatu A a množinu Rk+1 = { rk+1(q); q є Q}. Pro vnitřní stav q’ automatu A platí: q’ є rk+1(q) právě tehdy, jestliže q’ є rk(q) a současně pro libovolný symbol x vstupní abecedy X je δ(q’, x) є rk(δ(q, x)). (c) Po konečně mnoha krocích (maximální počet kroků je dán počtem prvků množiny vnitřních stavů automatu A) musí nastat Rl = Rl+1. Množinu Rl v reduktu zvolíme jako množinu vnitřních stavů, jako počáteční vnitřní stav zvolíme množinu rl(q0). Algoritmus redukce lze popsat takto: (a) Sestrojíme množinu R0 a položíme k := 0. (b) Sestrojíme množinu Rk a provedeme přiřazení k := k + 1. (c) Jestliže Rk ≠ Rk+1, opakuje se operace (b), jinak se pokračuje operací (d). (d) Jako výsledná množina se označí Rk. 11. příklad Uvažujme Mooreův automat 2. typu A takový, že Q = {q0, q1, q2, q3, q4, q5}, kde q0 je počáteční vnitřní stav, vstupní abeceda X = {0, 1} a výstupní abeceda Y = {0, 1}, který je definován mooreovskou tabulkou δ 0 1 μ q0 q1 q1 0 q1 q2 q1 1 q2 q3 q3 1 q3 q4 q1 0 q4 q5 q1 1 q5 q3 q3 1 Automat A neobsahuje nedostižné vnitřní stavy. Přistoupíme k použití algoritmu redukce. 5 6
Jde vlastně o rozklad množiny vnitřních stavů na třídy m-ekvivalence. Uvažujeme přirozená čísla včetně 0.
1. krok – R0 = {{q0 , q3}, {q1, q2, q4, q5}}, protože μ(q0) = μ(q3) = 0 a μ(q1) = μ(q2) = μ(q4) = μ(q5) = 1. 2. krok – R1 = {{q0 , q3}, {q1, q4}, {q2, q5}}, protože (a) δ(q0, 0) = q1, δ(q3, 0) = q4, tj. δ(q0, 0) є {q1, q2, q4, q5}, δ(q3, 0) є {q1, q2, q4, q5} a δ(q0, 1) = δ(q3, 1) = q1, tj. δ(q0, 1) є {q1, q2, q4, q5}, δ(q3, 1) є {q1, q2, q4, q5}; (b) δ(q1, 0) = q2, δ(q4, 0) = q5, tj. δ(q1, 0) є {q1, q2, q4, q5}, δ(q4, 0) є {q1, q2, q4, q5} a δ(q1, 1) = δ(q4, 1) = q1, tj. δ(q1, 1) є {q1, q2, q4, q5}, δ(q4, 1) є {q1, q2, q4, q5}; (c) δ(q2, 0) = δ(q5, 0) = q3, tj. δ(q2, 0) є {q0 , q3}, δ(q5, 0) є {q0 , q3} a δ(q2, 1) = δ(q5, 1) = q3, tj. δ(q2, 1) є {q0 , q3}, δ(q5, 1) є {q0 , q3}. Neboť R0 ≠ R1, musíme pokračovat dále. 3. krok – R2 = {{q0 , q3}, {q1, q4}, {q2, q5}}, protože (a) δ(q0, 0) є {q1, q4}, δ(q3, 0) є {q1, q4} a δ(q0, 1) є {q1, q4}, δ(q3, 1) є {q1, q4}; (b) δ(q1, 0) є {q2, q5}, δ(q4, 0) є {q2, q5} a δ(q1, 1) є {q1, q4}, δ(q4, 1) є {q1, q4}; (c) δ(q2, 0) є {q0 , q3}, δ(q5, 0) є {q0 , q3} a δ(q2, 1) є {q0 , q3}, δ(q5, 1) є {q0 , q3}. Neboť R1 = R2, algoritmus redukce ukončí činnost. Pro redukt A1 automatu A množina vnitřních stavů Q obsahuje vnitřní stavy: q0 = {q0 , q3}, q1 = {q1, q4}, q2 = {q2, q5}. Mooreovská tabulka reduktu A1 má tvar (δ je přechodová funkce reduktu a μ značkovací funkce reduktu) δ 0 1 μ q0 q1 q1 0 q1 q2 q1 1 q2 q0 q0 1 □ Poznámka. Algoritmus redukce lze použít i na zjištění m-ekvivalence dvou Mooreových automatů 2. typu. Pro jeden z automatů přejmenujeme vnitřní stavy tak, aby tyto automaty neměly žádný společný vnitřní stav, mooreovské tabulky napíšeme pod sebe. Potom v jednotlivých množinách po použití algoritmu redukce musí být alespoň jeden vnitřní stav každého z automatů, přičemž počáteční vnitřní stavy musí být ve stejné množině.
Jazyky rozpoznávané automaty Jestliže L je jazyk nad abecedou X, potom L je rozpoznatelný konečným automatem, jestliže existuje Mooreův automat 2. typu A = [Q, X, {0, 1}, q0, δ, λ] takový, že pro libovolné slovo P abecedy X platí: P patří do jazyka L právě tehdy, jestliže λ*( q0, P) = 1. Uvedeme příklady jazyků a pro zjednodušení budeme předpokládat, že jde o jazyky nad abecedou X = {a, b}. 12. příklad Uvažujme jazyk L = Ø, tzn. tento jazyk neobsahuje žádné slovo. Potom např. Mooreův automat 2. typu A = [{q0}, {a, b}, {0, 1}, q0, δ, λ], který rozpoznává tento jazyk, je definován mooreovskou tabulkou δ
a
b
μ
q0
q0
q0
0
□ 13. příklad Mějme jazyk L = {Λ}, tzn. tento jazyk obsahuje pouze prázdné slovo. Potom např. Mooreův automat 2. typu A = [{q0, q1}, {a, b}, {0, 1}, q0, δ, λ], který rozpoznává tento jazyk, je definován mooreovskou tabulkou δ q0 q1
a q1 q1
b q1 q1
μ 1 0
□ 14. příklad Mějme jazyk L = {a}, tzn. tento jazyk obsahuje pouze slovo a délky 1. Potom např. Mooreův automat 2. typu A = [{q0, q1, q2}, {a, b}, {0, 1}, q0, δ, λ], který rozpoznává tento jazyk, je definován mooreovskou tabulkou δ a b μ q0 q1 q2 0 q1 q2 q2 1 q2 q2 q2 0 Analogicky lze řešit úlohu pro jazyk L = {b}, jen znaky a a b si vymění roli v Mooreově automatu 2. typu. □ 15. příklad Uvažujme jazyk L obsahující právě všechna slova v abecedě X, která jsou délky alespoň 2, která začínají a končí stejným symbolem. Potom např. Mooreův automat 2. typu A = [{q0, q1, q2, q3, q4, q5, q6}, {a, b}, {0, 1}, q0, δ, λ], který rozpoznává tento jazyk, je definován mooreovskou tabulkou δ a b μ q0 q1 q2 0 q1 q3 q4 0 q2 q6 q5 0 q3 q3 q4 1 q4 q3 q4 0 q5 q6 q5 1 q6 q6 q5 0 □ 16. příklad Uvažujme jazyk L obsahující právě všechna slova v abecedě X, která končí podslovem abba. Potom např. Mooreův automat 2. typu A = [{q0, q1, q2, q3, q4, q5}, {a, b}, {0, 1}, q0, δ, λ], který rozpoznává tento jazyk, je definován mooreovskou tabulkou δ a b μ q0 q1 q2 0 q1 q2 q3 0 q2 q2 q2 0 q3 q2 q4 0 q4 q5 q2 0 q5 q5 q5 1 □ 17. příklad
Uvažujme jazyk L obsahující právě všechna slova v abecedě X tvaru an bn, kde n je přirozené číslo7 (tj. L obsahuje slova sudé délky8, jejichž první polovina jsou samá a a druhá polovina samá b). Tento jazyk není rozpoznatelný konečným automatem. Proč? Kdyby automat měl např. 7 vnitřních stavů, potom vezmeme slovo a8 b8. V tomto případě si automat musí nejprve zapamatovat, že slovo končí osmi znaky b, k tomu je potřeba 8 vnitřních stavů. Obecněji – obsahuje-li automat n vnitřních stavů, potom stačí vzít slovo an+1 bn+1.□ Kdybychom místo abecedy X = {a, b} zvolili jinou abecedu, je zřejmé, že úvahy by byly analogické jako v předcházejících příkladech. Jazyky a gramatiky Přepisovací systém9 nad abecedou X je konečná množina P přepisovacích pravidel, kde každé přepisovací pravidlo má tvar A → B, kde A a B jsou slova v abecedě X. Jsou-li T a U slova v abecedě X, (a) řekneme, že přepisovací systém P přímo přepíše T na U (a zapíšeme T => U), jestliže existují slova C a D z abecedy X a přepisovací pravidlo A → B z P tak, že T = CAD a U = CBD, (b) řekneme, že přepisovací systém P přepíše T na U (a zapíšeme T => U), jestliže buď T = U, nebo existují slova T1, T2,…, Tn (kde n ≥ 1) taková, že T => T1 => T2 => …=> Tn = U. 18. příklad Mějme oblíbenou abecedu X = {a, b}. Přepisovací systém P tvoří dvě přepisovací pravidla (1) ab → ba, (2) ba → ab. Potom např. aabba => aaabb, protože aabba =>(2) aabab =>(2) aabab (pro větší přehlednost skupina symbolů, kterou přepisujeme, je vyznačena tučně a znak pro bezprostřední přepsání je opatřen číslem použitého pravidla). Také je aabba => abbaa, protože aabba =>(1) ababa =>(1) abbaa. Na první pohled je vidět, že tento přepisovací systém může přepsat každé slovo T v abecedě X na libovolné slovo U v této abecedě se stejným počtem výskytů symbolů a a b jako má U. □ Gramatika typu 0 nebo zkráceně gramatika je uspořádaná čtveřice G = [Y, X, s, P], kde Y a X jsou disjunktní10 abecedy, s je symbol abecedy Y a P je přepisovací systém nad abecedou XUY takových, že na levé straně každého přepisovacího pravidla je alespoň jeden symbol z abecedy Y. Y se nazývá abeceda neterminálů11, X je abeceda terminálů12 a s z Y je počáteční symbol. Řekneme, že jazyk L(G) je generován gramatikou G nebo L(G) je jazyk typu 0, jestliže obsahuje právě všechna slova W v abecedě X taková, že s => W. Tedy jazyk generovaný gramatikou je tvořen všemi slovy v terminální abecedě, která lze odvodit z počátečního symbolu. 19. příklad 7
Znovu upozorňujeme, že 0 považujeme za přirozené číslo, proto jazyk L obsahuje i slovo a0 b0 = Λ. 0 považujeme za sudé číslo. 9 Někdy se také nazývá produkční systém. 10 Tzn. X ∩ Y = Ø. 11 Jinak lze říci i množina proměnných. 12 Jinak lze říci, že jde o množinu konstant. 8
Mějme gramatiku G = [{s}, {a, b}, s, P], kde přepisovací systém P tvoří tři přepisovací pravidla (1) s → asb, (2) s → ε. Je zřejmé, že jazyk L(G) generovaný gramatikou G obsahuje právě všechna slova tvaru an bn, kde n je přirozené číslo. □ V předcházejícím příkladu byla dvě přepisovací pravidla se stejnou levou stranou, pro jednoduchost je budeme zapisovat dohromady s → asb │ ε. Poznámka. Gramatika, kterou jsme definovali, se také nazývá generativní gramatika. Existuje i duální pojem – analytická gramatika. Ta je tvořena stejnou uspořádanou čtveřicí se změnou u přepisovacího systému P je přepisovací systém nad abecedou XUY takových, že na pravé straně každého přepisovacího pravidla je alespoň jeden symbol z abecedy Y. Jazyk L(G) je rozpoznáván gramatikou G, jestliže obsahuje právě všechna slova W v abecedě X taková, že W => s. Je zřejmé, že ke každé generativní gramatice existuje analytická gramatika rozpoznávající tentýž jazyk a naopak ke každé analytické gramatice existuje generativní gramatika generující tentýž jazyk. Analytickou gramatikou nezískáváme nic nového.
Mějme gramatiku G = [Y, X, s, P]. (1) G je gramatika typu 1 nebo kontextová gramatika, jestliže každé přepisovací pravidlo z P je tvaru AyB → ACB, kde A a B jsou slova z abecedy XUY, y je symbol z neterminální abecedy Y a C je neprázdné slovo z abecedy XUY, přičemž jedinou výjimkou může být pravidlo s → ε, jehož výskyt znamená, že se symbol s nemůže vyskytovat na pravé straně žádného přepisovacího pravidla z P. (2) G je gramatika typu 2 nebo bezkontextová gramatika, jestliže P obsahuje pouze pravidla tvaru y → C, kde C je slovo z abecedy XUY, y je symbol z neterminální abecedy Y. (3) G je gramatika typu 3 nebo regulární gramatika, jestliže každé pravidlo z P je buď tvaru y → Wx, nebo y → W, kde W je slovo z abecedy X, y a x jsou symboly z neterminální abecedy Y. (4) Jazyk typu 1 (resp. 2, resp. 3) nebo kontextový (resp. bezkontextový, resp. regulární), jestliže je generován nějakou kontextovou (resp. bezkontextovou, resp. regulární) gramatikou. Poznámka. Použití kontextového pravidla AyB → ACB a bezkontextového pravidla y → C má stejný efekt – neterminál y se přepíše na C, ostatní části slova zůstanou zachovány. V prvním případě dojde k tomu jen tehdy, jestliže y je obklopeno slovy A a B, tj. možnost přepsat y na C je závisí na kontextu, ve kterém se y vyskytuje. Ve druhém případě přepsání y na kontextu nezávisí. Toto pozorování vysvětluje, proč se gramatiky typu 1 nazývají kontextové a gramatiky typu 2 bezkontextové.
Každý regulární jazyk je bezkontextový, každý bezkontextový jazyk je kontextový, každý kontextový jazyk je typu 0. Uvedli jsme jazyky rozpoznatelné automaty. Lze je nějakým způsobem zařadit do výše uvedené hierarchie13 jazyků? Ano, platí: jazyk je rozpoznatelný automatem právě tehdy, jestliže jde o regulární jazyk. Jak sestrojit gramatiku G k Mooreovu automatu 2. typu A = [Q, X, {0, 1}, q0, δ, λ] se značkovací funkcí μ? Gramatika G = [Q, X, q0, P], tzn. množina vnitřních stavů Q je abeceda neterminálů, vstupní abeceda X je abeceda terminálů, počáteční vnitřní stav q0, je počáteční symbol. Přepisovací systém P bude obsahovat pravidla q → aq’, jestliže δ(q, a) = q’ a q → ε, jestliže μ(q) = 1. 20. příklad Uvažujme Mooreův automat 2. typu A = [{q0, q1, q2, q3, q4, q5}, {a, b}, {0, 1}, q0, δ, λ], který definován mooreovskou tabulkou δ a b μ 13
Námi uvedená hierarchie jazyků se nazývá Chomského hierarchie.
q0 q1 q2 0 q1 q2 q3 0 q2 q2 q2 0 q3 q2 q4 0 q4 q5 q2 0 q5 q5 q5 1 Ze 16. příkladu víme, že rozpoznává jazyk L obsahující právě všechna slova v abecedě {a, b}, která končí podslovem abba. Gramatika G bude mít neterminální abecedu {q0, q1, q2, q3, q4, q5}, terminální abecedu {a, b}, počáteční symbol je q0 a přepisovací systém P obsahuje pravidla (1) q0 → aq1 │ bq2, (2) q1 → aq2 │ bq3, (3) q2 → aq2 │ bq2, (4) q3 → aq2 │ bq4, (5) q4 → aq5 │ bq2, (6) q5 → aq5 │ bq5 │ ε. □ Bezkontextové gramatiky jsou vhodné i ke konstrukci programovacích jazyků. Uvedeme dva příklady některých konstrukcí. 21. příklad Uvedeme definici čísel v nějakém programovacím jazyku. Počáteční symbol bude neterminál [číslo], neterminály budou všechna slova či sousloví uvedená v hranatých závorkách a terminální abeceda bude {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, – , ., 10}. Přepisovací systém gramatiky obsahuje pravidla (1) [číslo] → [číslo bez znaménka], (2) [číslo] → + [číslo bez znaménka], (3) [číslo] → – [číslo bez znaménka], (4) [číslo bez znaménka] → [desetinné číslo], (5) [číslo bez znaménka] → [exponentová část], (6) [číslo bez znaménka] → [desetinné číslo] [exponentová část], (7) [desetinné číslo] → [celé číslo bez znaménka], (8) [desetinné číslo] → [desetinná část], (9) [desetinné číslo] → [celé číslo bez znaménka] [desetinná část], (10)[exponentová část] → 10[celé číslo], (11)[desetinná část] → .[celé číslo], (12)[celé číslo] → [celé číslo bez znaménka], (13)[celé číslo] → + [celé číslo bez znaménka], (14)[celé číslo] → – [celé číslo bez znaménka], (15)[celé číslo bez znaménka] → [číslice], (16)[celé číslo bez znaménka] → [celé číslo bez znaménka] [číslice], (17)[číslice] → 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9. Je zřejmé, že lze tím způsobem vygenerovat slova představující čísla. Cvičení (1) Sestrojte automat A se vstupní abecedou X = {a, b, c}, výstupní abecedou Y = {0, 1} a počátečním vnitřním stavem q0 takový, že
(a) vydá 1 při prvním výskytu podslova abbab ve vstupním slovu, jinak vydává 0; (b) vydá 1 při každém výskytu podslova abbab ve vstupním slovu, jinak vydává 0; (c) vydává 1 po prvním výskytu podslova abbab ve vstupním slovu, jinak vydává 0. (2) Sestrojte automat A se vstupní abecedou X = {a, b}, výstupní abecedou Y = {0, 1} a počátečním vnitřním stavem q0 takový, že (a) první symbol výstupního slova je 1, jestliže vstupní slovo končí podslovem ababba, a první symbol výstupního slova je 0, jestliže vstupní slovo končí podslovem ababba, jinak vydává jakýkoli výstupní symbol; (b) první symbol výstupního slova je 1, jestliže vstupní slovo začíná podslovem ababba, a první symbol výstupního slova je 0, jestliže vstupní slovo začíná podslovem ababba, jinak vydává jakýkoli výstupní symbol. (3) Podle výsledků cvičení (1) a (2) rozhodněte, které automaty jsou Mooreovy automaty 1. typu a které Mooreovy automaty 2. typu. Výsledky cvičení (1) (a) δ, λ q0 q1 q2 q3 q4 q5
a q0, 0 q2, 0 q0, 0 q2, 0 q5, 1 q5, 0
b q1, 0 q1, 0 q3, 0 q4, 0 q1, 0 q5, 0
c q0, 0 q0, 0 q0, 0 q0, 0 q0, 0 q5, 0
δ, λ q0 q1 q2 q3 q4
a q0, 0 q2, 0 q0, 0 q2, 0 q2, 1
b q1, 0 q1, 0 q3, 0 q4, 0 q1, 0
c q0, 0 q0, 0 q0, 0 q0, 0 q0, 0
δ, λ q0 q1 q2 q3 q4 q5
a q0, 0 q2, 0 q0, 0 q2, 0 q5, 1 q5, 1
b q1, 0 q1, 0 q3, 0 q4, 0 q1, 0 q5, 1
c q0, 0 q0, 0 q0, 0 q0, 0 q0, 0 q5, 1
(b)
(c)
(2) (a) δ, λ q0
a q2, 0
b q1, 0
q1 q2 q3 q4 q5 q6 q7
q1, 0 q1, 0 q1, 0 q5, 0 q6, 0 q7, 1 q7, 1
q1, 0 q3, 0 q4, 0 q1, 0 q1, 0 q1, 0 q7, 1
(b) δ, λ a b q0 q1, 0 q0, 0 q1 q1, 0 q2, 0 q2 q1, 0 q3, 0 q3 q4, 0 q0, 0 q4 q1, 0 q5, 0 q5 q6, 1 q3, 0 q6 q1, 0 q2, 0 (3) Automaty z výsledků cvičení (1) (c), (2) (a) a (b) jsou Mooreovy 2. typu, žádný není Mooreův 1. typu.
