Obsah Úvod 1 1 Teoretická informatika 2 1.1 Vznik a vývoj teoretické informatiky................... 2 1.1.1 Matematika............................. 2 1.1.2 Jazykověda............................. 5 1.1.3 Biologie ............................... 6 1.2 Možnosti použití teoretické informatiky................. 8 2 Konečné automaty 9 2.1 Konečný automat.............................. 9 2.2 Nedeterminismus.............................. 12 2.3 Totálni automat............................... 15 2.4 Odstranění nepotřebných stavů automatu................ 16 2.4.1 Nedosažitelné stavy........................ 16 2.4.2 Nadbytečné stavy.......................... 17 3 Regulární jazyky 19 3.1 Konečné jazyky............................... 19 3.2 Pumping Lemma pro regulární jazyky a nekonečné jazyky...... 20 3.3 Uzáverové vlastnosti třídy regulárních jazyků ............. 22 3.3.1 Sjednocení.............................. 23 3.3.2 Zřetězení............................... 24 3.3.3 Iterace................................ 25 I OBSAH II 3.3.4 Pozitivní iterace........................... 26 3.3.5 Zrcadlový obraz .......................... 26 3.3.6 Průnik................................ 27 3.3.7 Homomorfismus.......................... 29 4 Regulární výrazy 30 4.1 Možnosti využití regulárních výrazů................... 30 4.2 Definice.................................... 31 4.3 Vztah ke konečným automatům ..................... 32 4.4 Využití vztahu regulárních výrazů k reg. jazykům........... 36 4.4.1 Důkazy uzáverových vlastností regulárních jazyků...... 36 4.4.2 Normovaný automat........................ 37 4.4.3 Minimalizace konečného automatu ............... 38 5 Formální gramatiky 44 5.1 Generování slov jazyka........................... 44 5.2 Regulární gramatiky............................ 46 5.3 Chomského hierarchie gramatik ..................... 50 5.3.1 Gramatiky v Chomského hierarchii............... 50 5.3.2 Související typy gramatik..................... 51 5.4 Operace nad slovy a jazyky........................ 52 6 Bezkontextové jazyky 54 6.1 Bezkontextové gramatiky......................... 54 6.2 Vlastnosti bezkontextových gramatik .................. 56 6.2.1 Bezkontextové gramatika nezkracující.............. 56 6.2.2 Redukovaná gramatika ...................... 58 6.2.3 Gramatika bez jednoduchých pravidel ............. 61 6.2.4 Další typy bezkontextových gramatik.............. 62 6.3 Normální formy pro bezkontextové gramatiky............. 63 6.3.1 Chomského normální forma ................... 63 6.3.2 Greibachova normální forma................... 65 Kapitola 1 Teoretická informatika Tato kapitola je především motivační - dovíme se zde, jaký má teoretická informatika význam, jak vznikla a také jaké jsou možnosti jejího praktického použití. 1.1 Vznik a vývoj teoretické informatiky Vznik teoretické informatiky - tři kořeny: 1. matematika, 2. jazykověda, 3. biologie. 1.1.1 Matematika Počátek 20. století: rozvoj logiky. Roku 1936 - zjištění: „Nelze cokoliv jednoznačně určit a vypočítat." Otázka: „Co lze vypočítat?" =>- Turingův stroj a další výpočetní modely Alan Turing (1912-1954) Vytvořil Turingův stroj jako matematický model „Na tomto stroji lze vypočítat právě to, co je vypočitatelné." 2 Kapitola 1 Teoretická informatika 3 U 0 x A U u (jednostranně) nekonečná páska čtecí a zápisová hlava, pohyb oběma směry Konečná řídicí jednotka □ stav (proměnná, vnitřní paměť) Obrázek 1.1: Turingův stroj Vlastnosti Turingova stroje: • řídicí jednotka se vždy nachází v některém z předem určených stavů, • čtecí a zápisová hlava je vždy na některém políčku pásky, • v každém kroku se stroj řídí podle stavu jednotky a podle obsahu políčka, na které ukazuje hlava, • podle těchto dvou údajů se rozhodne o akci, která spočívá - ve změně stavu jednotky (například ze stavu „načítání" do stavu „načteno" nebo ze stavu „pracuji" do stavu „vypínám"), - přepsání obsahu políčka na pásce něčím jiným (nebo může políčko zůstat beze změny), a - posun na pásce vpravo, vlevo, a nebo může hlava zůstat na stejném políčku. Výsledkem činnosti stroje obvykle bývá obsah pásky, důležitou informací může být stav, ve kterém stroj skončil výpočet (je množina koncových stavů). Další modely: Turingův stroj byl moc složitý pro některé jednodušší výpočty, proto vznikly jednodušší modely - konečný automat a zásobníkový automat. Vlastnosti konečného automatu: • řídicí jednotka se vždy nachází v některém z předem určených stavů, • čtecí hlava je vždy na některém políčku pásky, Kapitola 1 Teoretická informatika 4 a 0 a 8 / w jednostranné nekonečná páska čtecí hlava, pohyb doprava Konečná řídicí jednotka □ stav (proměnná, vnitřní paměť) Obrázek 1.2: Konečný automat • v každém kroku se stroj řídí podle stavu jednotky a podle obsahu políčka, na které ukazuje hlava, • podle těchto dvou údajů se rozhodne o akci, která spočívá - ve změně stavu jednotky (například ze stavu „načítání" do stavu „načteno" nebo ze stavu „pracuji" do stavu „vypínám"), - posunem na pásce o políčko vpravo. Narozdíl od Turingova stroje se čtecí hlava posouvá v každém kroku o políčko doprava a nemá možnost zapisovat. Výsledkem činnosti automatu je pouze informace o tom, ve kterém stavu stroj skončil, a zda přečetl celý obsah pásky (když nepřečetl a „zasekl se" - pro daný obsah pole na pásce a momentální stav třeba není definována žádná akce). a 0 a 8 / w jednostranně nekonečná páska čtecí hlava, pohyb doprava stav (proměnná, vnitřní paměť) 5_ a Z zásobník Obrázek 1.3: Zásobníkový automat Kapitola 1 Teoretická informatika 5 Vlastnosti zásobníkového automatu: • řídicí jednotka se vždy nachází v některém z předem určených stavů, • čtecí hlava je vždy na některém políčku pásky, • automat má k dispozici zásobník, kde přidává shora a také shora vybírá, • v každém kroku automat vyjme jeden prvek ze zásobníku, a řídí se podle tohoto vyjmutého symbolu, stavu jednotky a také se může (nemusí) řídit podle obsahu políčka, na které ukazuje hlava, • podle těchto tří (nebo dvou) údajů se rozhodne o akci, která spočívá - ve změně stavu jednotky (například ze stavu „načítání" do stavu „načteno" nebo ze stavu „pracuji" do stavu „vypínám"), - posunem na pásce o políčko vpravo, pokud v tomto kroku četl symbol ze vstupní pásky (tj. když čte ze vstupu, zároveň se posune dál), - může uložit do zásobníku jakýkoliv počet prvků (i žádný), a to postupně po jednom, ten, který vložil jako poslední, bude hned v dalším kroku vyjmut. Narozdíl od konečného automatu čtecí hlava nemusí pracovat v každém kroku (buď čte a zároveň se posune, nebo nepracuje vůbec), nemá možnost zapisovat a pohybuje se jen směrem doprava. Výsledkem činnosti je informace o stavu, ve kterém stroj skončil, zda přečetl celý obsah pásky, a případně může být důležité, zda do konce výpočtu stačil vyprázdnit celý zásobník. 1.1.2 Jazykověda Formální gramatika řeší, jak se slova utvářejí (u matematických kořenů byl řešen problém rozpoznávání již utvořených slov či sekvencí signálů). Noam Chomskij Zkoumal syntaxi jazyka a schopnost lidí mluvit. „Všechny jazyky jsou utvořeny přibližně stejným způsobem, mají stejný základ." Definice 1.1 (Formální gramatika) Formální gramatika je soubor obecných pravidel, generujeme větu na základě její struktury (syntaxe). Kapitola 1 Teoretická informatika 6 Příklad 1.1 _______________________________________ S —► [&egm]A[en- [&egm]A[en- [begin]P; [end\ =>- [begin]P; P; [end\ => =>- [begin] [vypis]T; P; [end] => =>- [begin][vypis][pismenko]T; P; [end] => ... =>- [begin] [výpis] [písmenko] [písmenko] [písmenko]: [výpis][písmenko][písmenko][písmenko][písmenko]; [end] Základní princip: Věta se skládá ze slov, při skládání částí potřebujeme také pomocná slova („obecné termíny"), za která můžeme dosadit posloupnost skládající se ze slov a pomocných slov - rekurze. Pomocná slova = neterminální symboly, skutečná slova = terminálni symboly Typy formálních gramatik: • Gramatika odpovídající Turingovu stroji: pravidla a —► ß • Bezkontextová gramatika: pravidla A —► ß • atd. 1.1.3 Biologie Aristid Lindenmayer. Lindenmayerovy systémy (L-Systémy) - zjistil, že když upraví formální gramatiku a pozmění její chování, dokáže například simulovat růst a vývoj rostliny nebo dělení buněk. Pravidlo: b —► bb Výpočet: b =>- bb =>- b4 =>- b8 =>- ... Kapitola 1 Teoretická informatika 7 Jeho žáci pak přišli na možnost grafické interpretace L-Systémů =>- různé typy fraktálu. U fraktálu generovaných L-Systémy jde o to, jak poměrně složitý nákres vygenerovat co nejjednodušším řetězcem „obyčejných" symbolů, které mají význam určité instrukce (vykresli čáru, popojdi bez vykreslení, otoč se doprava, doleva, ulož písmeno do zásobníku, vyjmi písmeno ze zásobníku, apod.). Uplatňuje se rekurze, tedy totéž pravidlo (nebo tatáž pravidla) se používá pořád dokola tak dlouho, dokud nevznikne dostatečně dlouhá a „složitá" posloupnost instrukcí. (a) (b) (c) (d) Obrázek 1.4: Několik fraktálu vygenerovaných pomocí L-Systémů Kapitola 1 Teoretická informatika 8 Například obrázek 1.4c na straně 7 vznikl z řetězce F+F+F+F+F+F tak, že jsme rekurzívně všechny symboly F (i ty nově přidávané) zpracovali pravidlem F —► F [ + F+F] F. 1.2 Možnosti použití teoretické informatiky • stavové programování, překladače • modelování matematických výpočtů • analýza přirozeného jazyka (kontrola pravopisu, překlady, atd.) • L-Systémy: biologie, fraktály (malířství, filmy, apod.), fyzika (teorie chaosu, modelování turbulence, studium tornád, atd.) • porovnávání složitosti různých algoritmů dělajících totéž • DNA-výpočty • fyzika - kvantové počítače Konečné automaty Nejdřív se budeme zabývat nejjednodušším typem modelů, které byly zmíněny v kapitole 1.1.1 o matematických kořenech teoretické informatiky, konečnými automaty, a také se podíváme na základy práce s jednoduchými gramatikami, se kterými jsme se už trochu seznámili v kapitole 1.1.2. 2.1 Konečný automat Konečný automat je vždy v některém (vnitřním) stavu, který si můžeme představit jako proměnnou nabývající předem stanovených hodnot. Pracuje jednoduše tak, že na základě informace o svém momentálním stavu a dále podle signálu, který dostal (symbolu na vstupu) se přesune do některého jiného stavu a zároveň se posune na vstupu, tedy očekává další signál (je připraven načíst další symbol z pásky). Na obrázcích 2.1, 2.2 a 2.3 vidíme několik jednoduchých diagramů (orientovaných grafů) konečných automatů. Diagram přehledně (u jednodušších automatů) zobrazuje přechody mezi stavy (šipky) a signály (symboly), které jsou při tomto přechodu načítány a zpracovávány (ohodnocení šipek). Popis: V..........vypnuto Z..........zapnuto Obrázek 2.1: Elektrický spotřebič jako konečný automat 9 Kapitola 2 Konečné automaty 10 Popis: V..................vypnuto Č, Z.........červená, zelená OČ — oranžová od červené OZ.....oranžová od zelené Obrázek 2.2: Semafor jako konečný automat Obrázek 2.3: Automat na jízdenky Definice 2.1 (Konečný automat) Konečný automat je uspořádaná pětice A= (Q,Tl,8,q0,F),kdeje Q... neprázdná konečná množina stavů E... neprázdná konečná abeceda (množina signálů) 8... přechodová funkce, definovaná níže g0- • • počáteční stav, q0 G Q F... množina koncových stavů, F C Q, F ^ 0 Definice 2.2 (Přechodová funkce) Přechodová funkce ó konečného automatu (dále KA) A = (Q, £, ö, q0, F) je zobrazení ó : Q x E —► Q 8(stav, signál) = stav Například: 8(vypnuto, zapni) = zapnuto Kapitola 2 Konečné automaty 11 Potřebujeme vědět: • ve kterém jsme stavu, • co ještě zbývá přečíst (zpracovat). Tyto informace jsou uloženy v konfiguraci automatu, která se postupně mění. Definice 2.3 (Konfigurace konečného automatu) Označme E* množinu všech slov, která lze utvořit ze symbolů abecedy E. Konfigurace KA je uspořádaná dvojice (q, w), kde q G Q,w G E* (nepřečtená část vstupní pásky). • Počáteční konfigurace: (g0, wo) (jsme v počátečním stavu a w0 je celé zpracovávané slovo) • Koncová konfigurace: (qf,e), q f G F (e je prázdné slovo, tj. řetězec s délkou 0, neboli celé slovo již bylo zpracováno) Definice 2.4 (Přechod mezi konfiguracemi) Relace přechodu mezi konfiguracemi je definována jako \—. (Q,E*) x (Q, Ľ*), kde platí: (qi}aw) h (qj,w) <* 6(qi,a) = q3 (relace přechodu mezi konfiguracemi je tedy závislá na funkci přechodu ó). Definice 2.5 (Výpočet slova v konečném automatu) Výpočet slova v konečném automatu je posloupnost konfigurací spojených relací přechodu, začínající počáteční konfigurací s daným slovem a končící některou koncovou konfigurací. Příklad 2.1 ____________________________________________________________ Výpočet slova v konečném automatu - semaforu na obrázku 2.2 na straně 10 může být například takový: (V,zttttttv) h (Č,ttttttv) h (itshapeOČ,tttttv) h (Z,ttttv) h (OZ,tttv) h (Č,ttv) h (OČ, tv) h (Z, v) h (V, e) Jiný konečný automat: (q0,abcď) \- (q3,bcd) h (qi,cd) h (q3,d) h (q3,e) kde všechny přechody mezi konfiguracemi jsou určeny funkcí 5 : 5(q0, a) = q3, atd., a q3 patří do množiny koncových stavů. Kapitola 2 Konečné automaty 12 Definice 2.6 (Rozpoznání (přijímání) slova konečným automatem) Konečný automat A = (Q, S, ó, q0, F) rozpoznává (přijímá) slovo w, pokud existuje posloupnost výpočtu tohoto slova v automatu, tedy pokud se lze z počáteční konfigurace (qo,w0) postupným uplatňováním relací přechodu dostat do některé koncové konfigurace. Definice 2.7 (Jazyk) Jazyk L je množina slov nad danou abecedou E (některá podmnožina množiny všech slov utvořených z písmen abecedy £), tedy KE*, Jazyk může obsahovat také prázdné slovo e. Definice 2.8 (Jazyk konečného automatu) Jazyk konečného automatu A je množina všech slov, která automat přijímá, značíme L (A). Definice 2.9 (Rozpoznání jazyka automatem) Automat A rozpoznává jazyk Ljf pokud přijímá právě slova jazyka L j (tj. přijímá všechna slova jazyka, ale nepřijímá žádné slovo do jazyka nepatřící). Značíme L j = L (A) (jazyk L j je rozpoznáván automatem A, je jeho jazykem). Příklad 2.2 ________________________ A=({q0,qi}, {a,b}, o, q0, fa}) Diagram: 5 funkce: CY^-r^ %),«) = -*•(*) (Q) ö(q0,b) = ^^L^W Sfa,b) = Jeden z možných výpočtů v automatu: {q0,aab) h (q0,ab) h (qQ,b) h fa,e) qo 9o Jazyk automatu: L(A) = {a*b} ■ {(bďbf \i > 0} Tabulka: stav\vstup a b ^9o 9o 9i «-91 - 9o {(a*bb)*a*b} {a*(bba*)*b} 2.2 Nedeterminismus V základní definici konečného automatu existuje pro každé slovo přijímané automatem právě jedna cesta v diagramu automatu, a tedy výpočet je vždy jednoznačný. Kapitola 2 Konečné automaty 13 Výhodou tohoto postupu je, že takto vytvořený konečný automat se snadněji programuje, protože v klasickém programování je jednoznačnost nutnou podmínkou. Někdy je však jednodušší vytvořit automat, který tuto vlastnost nemá, tedy pro některá přijímaná slova může existovat více různých cest v diagramu. Zde si takový automat definujeme a ukážeme si také způsob převedení na původní formu. Definice 2.10 (Nedeterministický konečný automat) Nedeterministický konečný automat (NKA) je takový konečný automat A = (Q, E, ö, q0, F), kde 5 : Q x E —► V (Q). Poznámka: V (Q) je potenční množina množiny Q, je to množina všech jejích podmnožin (včetně prázdné množiny a také samotné množiny Q). V některých stavech na určitý signál může existovat více než jedna možnost jak reagovat, dokonce pro některá slova může v grafu automatu existovat více různých cest od počátečního stavu do některého koncového. V deterministickém automatu (DKA) pro jedno slovo existuje právě jedna cesta v grafu (je automatem rozpoznáváno) nebo žádná cesta. Definice 2.11 (Jazyk rozpoznávaný NKA) Jazyk rozpoznávaný NKA je L(A) = {wEZ*\ (q0,w) h* (qf,e),qf G F}. Poznámka: Jazyk rozpoznávaný nedeterministiským konečným automatem je tedy množina všech slov nad abecedou E, pro která existuje alespoň jeden výpočet (cesta v grafu automatu) od počátečního do některého (kteréhokoliv) koncového stavu. Veta 2.1 Nechť A je nedeterministický KA. Potom existuje deterministický KA A' takový, že L (A) = L (A') (tj. rozpoznávají stejný jazyk). Důkaz: A = (Q,T,,8,qo,F) nedeterministický (ten máme) A' = (Q', E, ö', q'Q, F') deterministický (ten chceme vytvořit) Stavy nového automatu budou odpovídat množinám stavů původního. Pro každou rovnost S(qi}a) = {qj,qk} stavy (množiny) {<&},{<£,•,<&} budou patřit ke stavům nového automatu. Postup: • Q' = {M \ M C Q} = V (Q) - nová množina stavů bude množinou všech podmnožin původní množiny stavů, Kapitola 2 Konečné automaty 14 • q'0 = {q0} - počáteční stav je jednoprvková množina obsahující původní počáteční stav, • M e F' <^> MnF^I- koncové stavy jsou všechny, které (coby množiny) obsahují alespoň jeden původní koncový stav, • ô'(M,a) = {q \ q E 5(p,a),p G M} - všechny prvky množiny zpracujeme podle původního automatu, pak shrneme výsledky do množiny. D Pokud pracujeme s reprezentací í-funkce ve tvaru tabulky, můžeme jednoduše postupovat tak, že v tabulce původního automatu „uzávorkujeme" ohodnocení řádků a buňky do množinových závorek a pak pro každou množinu z buněk, kterou není ohodnocen žádný řádek, přidáme řádek tabulky a doplníme obsah buněk na daném řádku. Jak určit obsah nové buňky: pokud je řádek ohodnocen množinou {qi} qj}...}, pak do buňky sepíšeme obsah buněk na řádcích {^j, {(£,}, ... v daném sloupci, tedy vlastně sjednocujeme řádky jednotlivých prvků množiny. Příklad 2.3 __________________ L = {a, b}*bb = {{a, b}nbb \n>0} A = {q0, gi,g2}, {a, b},6, qQ, {q2}) A> = (Q>,Z,ó>,q>0,F>) Deterministický: A a b -{<*>} {*} ÍQo,qi} M 0 fe} <-{92> 0 0 ÍQo,Qi} {*} {Qo,Qi,Q2} <^{qo,qi,q2} {*} {Qo,Qi,Q2} Nedeterministický: A a b ~^qo qo Qo,Qi q\ - 92 ^q2 - - Odstraníme nepotřebné stavy: A a b -{<*>} {*} {Qq,Qi} {Qq,Qi} {*} {Qq,Qi,Q2} ^{Qq,Qi,Q2} {*} {Qq,Qi,Q2} Kapitola 2 Konečné automaty 15 2.3 Totálni automat Obvykle není nutné, aby automat dokázal v každém stavu reagovat na jakýkoliv signál, ale za určitých okolností se tato vlastnost může hodit. Můžeme si představit třeba situaci, kdy programátor chce napsat program dostatečně robustní, který by dokázal reagovat na jakýkoliv vstup, v případě chybného vstupu třeba chybovým hlášením (tedy přechodem do chybového stavu s patřičným ošetřením). Definice 2.12 (Totální automat) Totální (úplný) konečný automat je deterministický konečný automat, ve kterém lze ve všech stavech reagovat na kterýkoliv symbol abecedy, tj. přechodová funkce 6 je totální: \/q G Q, Va G E 3p g Q : ö(q, a) = p (ke každému stavu a symbolu abecedy existuje stav, do kterého přejdeme z daného stavu na daný symbol). Veta 2.2 Ke kadému (deterministickému) konečnému automatu A existuje totální automat Ä takový, že L (A) = L(A). Náznak důkazu - konstrukce: • převedeme automat na deterministický, • vytvoříme nový stav 0, který bude fungovat jako „odpadkový koš", • do tohoto stavu nasměrujeme chybějící přechody, • přidáme smyčku (přechod začínající a končící ve stejném stavu) u stavu 0 pro každý symbol abecedy. Příklad 2.4 ____________________________________________________________ Deterministický: A 0 1 -^A A B B C - ^C - C Zúplnění: A 0 1 -^A A B B C 0 ^C 0 C 0 0 0 Kapitola 2 Konečné automaty 16 2.4 Odstranění nepotřebných stavů automatu Definice 2.13 (Nedosažitelný stav) Nedosažitelný stav je stav qí takový, že neexistuje posloupnost přechodů {q0,w) h* (qí,wr) tedy nelze se do tohoto stavu dostat z počátečního stavu. Definice 2.14 (Nadbytečný stav) Nadbytečný stav je stav qí takový, že neexistuje žádná posloupnost přechodů {qi,w') h* (qf,e) kde qf G F (koncový stav), tedy z tohoto stavu se nelze dostat do žádného koncového stavu. 2.4.1 Nedosažitelné stavy Vytvoříme množinu stavů, ke kterým se dá dostat z počátečního stavu - postupujeme od startovacího symbolu. Příklad 2.5 ___________________________________________________________ Původní automat: a b ->qo q\ - q\ 92 q\ ^92 - - qa 94 q\ ^q4 q\ - \qv a ^qi A a /T~% a a /r\ So = Í9o}/ hledáme prvky S^i na označeních řádků, přidáme obsah buněk řádku Si = {qo, qi) (z qo se dá dostat do q{) 52 = {qo, qi, 92} (z qo a q\ se dá dostat taky do q2) 53 = {qo, q\, 92} = S2 ... nová množina stavů Po úpravě: a b ~^qo q\ - q\ 92 9i ^92 - - -*■( 11 Kapitola 2 Konečné automaty 17 Postup: • vytvoříme množinu 5*0, do ní dáme počáteční stav automatu, 5*0 = {qo}, • vytvoříme množinu 5*1 tak, že do ní dáme prvky množiny So a dále všechny stavy, do kterých vede přechod ze stavů množiny S0 (tj. zde přidáme všechny stavy, do kterých se dá dostat přímo z q0), • postupně vytváříme množiny Si tak, že do Si zařadíme nejdřív obsah množiny Si-i a pak přidáme všechny stavy, do kterých vede přechod z některého stavu z množiny Sí_i, • končíme, když už se do množiny nic nedá přidat, tedy Si = Sí_i, výsledkem je nová množina stavů. Vzorec: So = {qo} Si = Si-i U {q I 8(p,a) 3 q,p G Si_i,a G £} 2.4.2 Nadbytečné stavy Příklad 2.6 ____________________________________________ Předpokládáme zde, že nedosažitelné stavy jsou již odstraněny. Původní automat: a b ~^qo q\ qs <-?i qi 92,95 ^92 92 - qs qi - qi q$ qi q$ q$ - Eo = {qi, 92}/ hledáme prvky Ei_x v buňkách řádků, přidáme označení řádků E\ = {qi,q2, qo} (z q0 se dá dostat do qx) £-2 = {qi, 92, qo} = E\ ... nová množina stavů Po úpravě: a b ^9o q\ 93 <-?i 92 ^92 92 - Kapitola 2 Konečné automaty 18 Postup: • odstraníme nedosažitelné stavy, • vytvoříme množinu Eq, do které zařadíme všechny koncové stavy automatu, t)- Eq = F, • vytvoříme množinu E\ tak, že do ní dáme prvky množiny E0 a dále všechny stavy, ze kterých vede přechod do stavů množiny E0, • postupně vytváříme množiny Ei tak, že do Ei zařadíme nejdřív obsah množiny Ei-i a pak přidáme všechny stavy, ze kterých vede přechod do některého stavu z množiny Ei-\, • končíme, když už se do množiny nic nedá přidat, tedy Ei = Ei_\, výsledkem je nová množina stavů. Vzorec: Eq = F Eí = Ei_i U {q I ó(q,a) 3 p, p G Ei_ua G E} Regulární jazyky Definice 3.1 (Regulární jazyk) Regulárními jazyky označujeme všechny jazyky, které jsou rozpoznávané konečnými automaty. jazyk je tedy regulární, pokud lze sestrojit konečný automat, který tento jazyk rozpoznává. Ve všech dosud uvedených příkladech byly použity jazyky nekonečné, ale k regulárním jazykům patří také konečné jazyky. Dále se stručně podíváme na možnosti konečných jazyků a potom na nekonečné jazyky a jednu z možností, jak zjistit, zda nekonečný jazyk je či není regulární. 3.1 Konečné jazyky Definice 3.2 (Konečný jazyk) Konečný jazyk je jazyk, který obsahuje konečně mnoho slov. Veta 3.1 Všechny konečné jazyky jsou regulární. Důkaz: Pro konečný jazyk sestrojíme konečný automat jednoduše tak, že pro každé slovo jazyka vytvoříme jednu „větev" výpočtu (nedeterministický automat). Délka větví automatu bude odpovídat délce jednotlivých slov jazyka. D Poznámka: Můžeme mít buď jeden koncový stav společný pro všechna rozpoznávaná slova, a nebo každé slovo bude mít svůj vlastní koncový stav. Toho se využívá například u překladačů, kdy při rozpoznávání konečného množství slov H 19 Kapitola 3 Regulární jazyky 20 (klíčových slov) pro každé slovo máme zvláštni koncový stav, a podle toho, ve kterém skončí výpočet, určíme, o jaké slovo šlo. Příklad 3.1 ____________________________________________________________ L = {if, then, this} Nedeterministický („otrocký" postup): Deterministický: Reprezentace přechodové funkce tabulkou (chceme, aby byl automat deterministický): A i f t h e n s -^S Al A2 A1 Kx A2 A3 A3 A5 A, A, K2 A5 Ks <-Kx ^K2 ^K3 3.2 Pumping Lemma pro regulární j azyky a nekonečné jazyky Motivace. Pumping lemma (pumpovací věta) určuje, že nekonečné regulární jazyky mají jednu konkrétní vlastnost. Proto pokud dokážeme, že daný jazyk tuto vlastnost nemá, můžeme o něm říci, že není regulární. Kapitola 3 Regulární jazyky 21 Abeceda je vždy konečná množina a počet stavů automatu je vždy konečný => abychom mohli pracovat s dostatečně dlouhými slovy (nekonečného jazyka) s délkou větší než počet stavů automatu, musí být někde smyčka, která způsobí, že se část slova opakuje. Obrázek 3.1: Ukázky grafů konečných automatů nekonečných jazyků Veta 3.2 Nechť L je regulární jazyk. Pak existuje celé číslo p, p > 0 tak, že každé slovo w e L, \w\ > p, lze rozdělit na tři části w = xyz tak, že y ^ e (\y\ > 0) a každé slovo ve tvaru xykz, \/k E M je také slovem tohoto jazyka, tedy xykz E L. Poznámka: Za číslo p můžeme dosadit počet stavů automatu, pokud máme sestrojený konečný automat. Příklad 3.2 ____________________________________________________________ L = {a2n \n>0} Zvolíme p = 2. Pro nějaké i > p může být třeba a2% = (a2) ■ (a2^~^) ■ e (tedy x = a2, y = a2^-1), z = a° = e) Použijeme číslo k > 0: k = 0 : xy°z = a2 E L...............................OK k = l:xy1z = a2i E L...............................OK k = 2 : xy2z = a2 fa2^"1))2 = a2^"1) EL............OK k=p:xypz = a2+p*2(i-l) = a2^-^1) e L.....OK Poznámka: Pumping lemma se obvykle nepoužívá v základním tvaru, ale spíše pro důkaz, že daný jazyk není regulární - větu obrátíme: Původní: Když je jazyk regulární, pak existuje p ... Obrátíme: Když neexistuje p ..., pak jazyka není regulární. Kapitola 3 Regulární jazyky 22 Postup: Hledáme dostatečně dlouhé slovo daného jazyka, pro které neexistuje žádné rozdělení w = xyz takové, že xykz G L. 1. zvolíme w E L dostatečně dlouhé, 2. zvolíme rozdělení naw = xyz, 3. zvolíme k, 4. vyrobíme Wk = xykz, 5. pokud wk E L =>- návrat k bodu 3, pokud to ještě jde, 6. když to není možné (pro všechna k slovo xykz patří do jazyka), návrat k bodu 2, 7. když to není možné (všechna rozdělení jsme otestovali a fungují), návrat k bodu 1, 8. jinak: našli jsme slovo w, pro které neexistuje žádné rozdělení xyz splňující uvedené podmínky, a tedy jsme dokázali, že L není regulární jazyk. Předposlední bod se u regulárního jazyka a také některých jazyků neregulárních provádí do nekonečna, což vyplývá z faktu, že Pumping Lemma je pouze implikace, ne ekvivalence. Tedy věta říká, že každý regulární jazyk má danou vlastnost, ale neříká, že tuto vlastnost nemá žádný neregulární jazyk. Poznámka: Pumping lemma lze ve skutečnosti použít i v případě, že jazyk je konečný-ve větě stojí „... každé slovo w G L, \w\ > p,lze... ", ovšem když zvolíme p opravdu dostatečně dlouhé (delší než kterékoliv slovo jazyka), pak vlastně není co testovat a vlastnosti jazyka větě odpovídají. 3.3 Uzáverové vlastnosti třídy regulárních jazyků Definice 3.3 (Uzavřenost třídy jazyků vzhledem k operaci (p) Daná třída jazyků je uzavřená vzhledem k operaci 0,j > 0} Ai = i{po,pi,P2}, {a,b}, Sx,pQ, {pi,p2}) L2 = {oV I i > 0, j > 0} A = ({50,91,92}, {a,c}, S2,q0, {gi,g2}) L = Li U L2 = {aV I i > 0, j > 0} U {oV | i > 0, j > 0} A= i{so,Po,PuP2,qo,quQ2}, {a,b,c}, S,s0, {pi,P2, qi, q2}) Původní: Po sjednocení: Kapitola 3 Regulární jazyky 24 Ai a b C ~^Po Pi <-j?l Pi P2 ^P2 P2 A fl b C -^ s0 Pi,Qi Po Pi <-j?l Pi P2 ^P2 P2 90 Qi <-?l Qi Q2 ^^2 Q2 A2 a b c ~^qo Qi <-?i Qi Q2 ^q_2 Q2 3.3.2 Zřetězení Věta 3.4 Třída regulárních jazyků je uzavřena vzhledem k operaci zřetězení. Důkaz: Budeme předpokládat, že některé dva regulární jazyky L\ a L2 jsou rozpoznávány automaty Ai = (Qi,Ľi,ói,q0í,Fi), Li=L(Ai)a A2 = iQ2,Z2,S2,q20,F2), L2 = L{A2),Qi n Q2 = 0. Vytváříme jazyk L = Lx ■ L2 a automat A = (Q, £, o, qo, F), L = L (A). • Qo = ql, • Q = QiUQ2, • E = E!UE2, • pokud e <£ L2, pak F = F2, jinak F = Fi U F2 {5i{p, a) \ p e Qi - Fi, S2Íp,a)\peQ2, U Slip,a) US2iql,a) \peFx Příklad 3.4 ____________________________________________________________ Li = {ďb | i > 0} Ai = i{po,Pi}, {a,b}, Sx,po, {pi}) L2 = {iabayc{0'1} \ i > Oj A2 = ({q0,..., q3}, {a,b,c}, S2,q0, {qo,qi}) A=i{po,Pi,qo,qi,q2,qa}, {a,b,c}, S,p0, {pi,q0,qi}) Kapitola 3 Regulární jazyky 25 Původní: Po zřetězení: 3.3.3 Iterace Věta 3.5 Třída regulárních jazyků je uzavřena vzhledem k operaci iterace. Důkaz: Budeme předpokládat, že některý regulární jazyk L\ je rozpoznáván automatem A = (Qi,£iA,9o,rU U = L(AX). Vytváříme jazyk L = L\ a automat A = (Q, £, o, q0, F), L = L (A). • Qo = qh • Q = Qi, • S = Si, • F = F, U {q0}, hip, a) \p& Fi, 5(p, a) 5i(p,a) l)ói(q^,a) | p G Fj D Příklad 3.5 Li = {ďbb I i > 0} Ai = ({po,Pi,P2}, {a,b}, ói,p0, {p2}) A=({po,Pi,P2}, {a,b}, ö,po, {po,P2}) Původní: Po iteraci: PO )----------*(Pl)----------►(( P2 Kapitola 3 Regulární jazyky 26 3.3.4 Pozitivní iterace Veta 3.6 Třída regulárních jazyků je uzavřena vzhledem k operaci pozitivní iterace. Důkaz: Budeme předpokládat, že některý regulární jazyk Li je rozpoznáván automatem Ai = (Qi,Y:i,öi,q^,Fi), Li = L(Ai). Vytváříme jazyk L = Lf a automat A = (Q, £, ö, qo, F), L = L (A). • Qo = ql, • Q = Qu • S = Ei, • F = Fi, 5(p, a) 5i(p,a) l)ói(q^,a); p e Fi D Příklad 3.6 Li = {ďbb \i>0} Ai = ({po,Pi,P2}, W,b}, öi,Po, {P2}) A=({po,PuP2}, {a,b}, ö,po, {p2}) Původní: Po pozitivní iteraci: Po )-------*-Ípi)-------K( V2 3.3.5 Zrcadlový obraz Veta 3.7 Třída regulárních jazyků je uzavřena vzhledem k operaci zrcadlového obrazu {reverze). Důkaz: Budeme předpokládat, že některý regulární jazyk Li je rozpoznáván automatem A\ = (Qi,5]i,5i,^,Fi), Li = L(Ai). Vytváříme jazyk L = Lf a automat A = (Q, £, o, q0, F), L = L (A). Kapitola 3 Regulární jazyky 27 Princip: obrátíme všechny „cesty" tak, aby začínaly tam, kde původně končily a naopak. g0 je nově přidán (nelze všechny původní koncové stavy prohlásit za počáteční), nasměrujeme ho tam, odkud původně vedly šipky ke koncovým stavům, Q = Qi U qQ, S = Si, 5(p, a) {p | 5i(p,á) 3p} p^q0 {p | 8i{p, o) = p} U {p I Slip, a) =p3 qf, qf G Fi} P = Qo D Příklad 3.7 ___________________________________________ Li = {ab'aW I i > O} U {atic I i > 0} = {aft* | i > 0} o {a, aa, c] Ai = i{qo,qi,q2,qa}, {a,b,c}, Si,q0, fe,^}) A=i{q0,qi,q2,q3,s0}, {a, b, c}, S,s0, {q0}) L = Lf = {a, aa, c} o {bla \ i > 0} Původní: Po zrcadlení: (jioj)*^—( qi )< 3.3.6 Průnik Průnikem dvou jazyků je jazyk obsahující právě ta slova, která jsou v obou zpracovávaných jazycích. Veta 3.8 Třída regulárních jazyků je uzavřena vzhledem k operaci průniku. Důkaz: Budeme předpokládat, že některé dva regulární jazyky Li a L2 jsou rozpoznávány automaty Kapitola 3 Regulární jazyky 28 Ai = {Qi,^i,öl,ql,Fl), Ll=L(Al)a A2 = (Q2,Z2,62,q20,F2), L2 = L{A2),Ql n Q2 = 0. Vytváříme jazyk L = Lx n L2 a automat A = (Q, E, ó, q0, F), L = L (A). Do průniku dvou množin (jazyk není nic jiného než množina slov) řadíme právě ty prvky (slova), které jsou v obou množinách zároveň. Když použijeme konečné automaty, spustíme výpočet daného slova na obou automatech zároveň. Protože podle definice musí automat v každém kroku zpracovat jeden symbol slova, v obou automatech musí být výpočet téhož slova stejně dlouhý (na cestě v grafu je stejný počet stavů), a tyto stavy si tedy mohou vzájemně odpovídat. Proto ve výsledném - simulujícím - automatu budou stavy reprezentovány uspořádanými dvojicemi, kde první prvek dvojice je stav prvního automatu, druhý prvek je stav druhého automatu. • Q = {[Qí, Qj] I Qi e QuQj e Q2}, • Qo = ÍQo,Qol • F = {[qt,q3] I qleFl,q3 G F2}, • E = Ei U E2 (nebo E = Ei n E2, vyjde to nastejno), • ô([qi,Qj],a) = [Si(qi,a),ô2(qj,a)], a G E D Příklad 3.8 ____________________________________________________________ Li = {anbb \n>0} L2 = {abn \n>0} Dva původní automaty: Pracujeme zároveň v obou automatech: Výsledný automat: Kapitola 3 Regulární jazyky 29 3.3.7 Homomorfismus Definice 3.4 (Homomorfismus) použitý na řetězce znaků s operací zřetězení je jednoznačné zobrazení, které zachovává neutrální prvek (v našem případě prázdný řetězec e) a také samotnou operaci zřetězení, tedy: h(e) = e h(a o w) = h(a) o h(w) Zde si pouze ukážeme postup na příkladu, důkaz bude proveden později v jiné kapitole. Veta 3.9 Třída regulárních jazyků je uzavřena vzhledem k operaci homomorfismu. Naznačení postupu důkazu: Budeme předpokládat, že některý regulární jazyk Li je rozpoznáván automatem Ai = (Qi,Y,i,5i,ql,Fi), Li = L(A\), a dále že existuje homomorfismus h definovaný pro všechny symboly jazyka Ei. Vytváříme jazyk L = h(Li) a automat A = (Q, T,,ö,qo,F), L = L (A). Postup si ukážeme na příkladu. Příklad 3.9 ____________________________________________________________ Li = {aô* I i > 0} h(a) = ccc. h(b) = cd ^(Li) = {c3(cdY \i > 0} Původní automat: Po aplikaci homomorfismu: Kapitola Regulární výrazy 4.1 Možnosti využití regulárních výrazů Regulární výrazy se v různých podobách využívají v praxi, zejména při vyhledávání (na internetu nebo třeba hledání souboru v počítači), a nebo tehdy, když chceme něco provést s množinou objektů (souborů, textu v souborech, v databázích, apod.) a potřebujeme tuto množinu nějak specifikovat. Vyhledávání na internetu (například Google): faktoriál pascal OR C++ - chceme program pro výpočet faktoriálu v Pascalu nebo C++ mravenec -Ferda - chceme stránky o mravencích, ale ne s Ferdou mravencem Vyhledávání na počítači (Windows, DOS, Unixy): * .txt - všechny soubory s příponou .txt ?psa*.* - znamená třeba opsané . doc, upsanec . exe, xpsa. xl s, atd. Vyhledávání na počítači (Unixy): [a-z]*[0-~9T - všechny řetězce začínající malým písmenem a končící číslicí 30 4 Kapitola 4 Regulární výrazy 31 a[!0-9] *.? - vše, co začíná malým a, přímo za ním může být jakýkoliv řetězec, který nezačíná číslicí, pak je tečka a za ní ještě jeden znak Možnosti použití: • vyhledávání na internetu, • vyhledávání souborů nebo čehokoliv dalšího textového na počítači, • prohledávání souborů na počítači (hledáme řetězec) - ve Windows například find str, v Unixech například grep, • databáze, • elektronické slovníky (cizojazyčné i výkladové), • podpora v programovacích jazycích, • atd. 4.2 Definice Definice 4.1 (Regulární výraz) Definujemepomocnoumnožinu í> = {0, e, +, o, *, (,)}. Množina RV(T,) všech regulárních výrazů nad abecedou E je nejmenší množina slov taková, že • slova se skládají ze symbolů abecedy E U $, E a $ jsou disjunktní, • 0 G RV(Y), e G KV (T,), a G i?V(£) pro každé ae^l, • jestliže a,ß G KV (T,), pak taky (a + ß)e RV(Ľ), {a- ß)e RV{Y), (a)* G i?V(£). Symbol pro zřetězení se obvykle nemusí psát. Regulární výraz označuje množinu řetězců s danou vlastností, jazyk je také množina řetězců (slov) s danou vlastností => každý regulární výraz určuje některý jazyk. Kapitola 4 Regulární výrazy 32 Operace nad jazyky: prázdný jazyk a, a G E CÜ + /3 a ■ ß (a)* {e} (jazyk obsahující jen slovo s nulovou délkou) {a} (jazyk obsahující jen slovo a s délkou 1) {a} U {ß} (sjednocení) {a} o {ß} (zřetězení) {a}* (iterace) Sjednocení, zřetězení a iteraci označujeme jako regulární operace. Příklad 4.1 Ukážeme si několik regulárních jazyků a ekvivalentních regulárních výrazů. Li = {ďc{ab)j \i,j> 0} Ri = a*c(ab)* L2 = {l2iw\i >0,we {0,1}*} JR2 = (11)(11)*(0 + 1)* L3 = {ďb | i > 0} U {6*a I i > 0} i?3 = aa*6 + b*a L4 = {e} U ({a&V | i > 0} U {62a2í+1 i > 0}) o {ca^ | i > 0} i?4 £ (abbbba* + bba(aa)*)ca* 4.3 Vztah ke konečným automatům Věta 4.1 Jazyky určené regulárními výrazy jsou právě regulární jazyky, tedy právě jazyky rozpoznávané konečnými automaty. Důkaz: „=>" (podle reg. výrazu sestrojíme konečný automat) Regulární jazyk je konstruován z množin pomocí operátorů sjednocení, zřetězení a iterace. Všechny tyto operátory mají svůj ekvivalent u regulárních výrazů. Důkaz lze provést matematickou indukcí: • báze: pro regulární výrazy 0, {e}, {a}, a G E dokážeme jednoduše zkonstruovat konečný automat, Kapitola 4 Regulární výrazy 33 • indukční krok: předpokládejme, že pro regulární výrazy a a ß dokážeme sestrojit konečné automaty (včetně těch v bází), • již dříve jsme dokázali (pomocí automatů), že třída regulárních jazyků je uzavřena vzhledem k operacím sjednocení, zřetězení a iterace, tedy použijeme postupy popsané v důkazech těchto operací pro sestrojení konečných automatů reprezentujících reg. výrazy a + ß, a ■ ß a (a)*. D Důkaz: „<=" (podle automatu sestrojíme reg. výraz) Musíme popsat regulárním výrazem všechny cesty vedoucí z počátečního stavu do některého koncového stavu automatu. Definujeme: Rl3 = {weZ*\(i,w)hX(j,s)} Je to množina všech slov takových, která lze v automatu zpracovat tak, že počáteční stav je i a skončíme ve stavu j. Jestliže je množina stavů {1,2,..., n}, pak jazykem automatu je množina [J R\k k&F (sjednotíme všechny cesty začínající v počátečním stavu a končící v některém z koncových stavů). D Pro postupnou konstrukci množin R^ použijeme: Ríj = {w G Ríj | pokud existuje m : (i,w) \r\. (m,u) \r\. (j,e), (4.1) w ^ u ^ e, pak m < k} (4.2) Je to podmnožina množiny R^ taková, že na cestě v automatu, která je zpracováním slova z této množiny, se nacházejí pouze stavy s indexem menším nebo rovným číslu k (neplatí pro „krajní stavy" i a j, ty mohou být i vyšší než k). Kapitola 4 Regulární výrazy 34 Postupujeme dle následujícího vzorce: riý- — riý- -t- ^-n-í;fc+i • ^-"-fc+l.fc+l/ ' -"-fc+lj To je rekurzivní vzorec pro výpočet množin R^ - nejdřív vezmeme všechna slova, která lze rozpoznat cestou přes stavy < k, a pak přidáme slova, která jsou zpracovávána cestou obsahující nejméně jednou stav k+1 (tedy nejdřív cesta z i do stavu k + 1, pak případně smyčka přes tento stav a stavy < k, a potom zpátky ze stavu k + 1 do j). Bází rekurze jsou jednoduché automaty, kde zachycujeme přímý přechod ze stavu i do j: R°.: D<+c) r}{e) (k+. Y.....)Rlk+i,k- T)k ■ T>k '■-.."fc+lj r>k J7) první případ použijeme, když ve stavu i existuje smyčka přes tento stav: R°ü = a + e druhý případ použijeme pro stav, ve kterém neexistuje smyčka (máme pouze „prázdný přechod"): R% = s třetí případ použijeme pro dva různé stavy i a j, mezi kterými vede přímý přechod: i?° v a • pokud mezi stavy i a j nevede přímý přechod, bude i?°- = 0. Postup: • vytvoříme i?°- pomocí definice automatu (z tabulky nebo diagramu), • podle rekurzívního vzorce vypočteme další množiny R^ až ke k = n, • platí R™j = Rij, dostaneme pro i = 1 a j G F všechny cesty v automatu vedoucí od počátečního stavu (i = 1) do koncových stavů, • výsledný regulární výraz pro celý automat je Uj€f Rij- Příklad 4.2 ____________________________________________________________ Uvedený postup si ukážeme na automatu se třemi stavy. Upozorňujeme, že složitost postupu narůstá s množstvím stavů geometrickou řadou. Kapitola 4 Regulární výrazy 35 #li = (b + e) + ((b + e)(b + e)* (b + e)) = b* R\2 = a+ ((b + e)(b + e)* a) = b* a R\3 = c+ ((b + e)(b + e)* c) = b* c R\x = 0 + 0 = 0 R\2 = {a + é) + $ = a + e i4 = b + 0 = b R\l = a+ (a(b + e)* (b + e)) = ab* R\2 = $ + (a(b + e)*a) = ab*a Rl3 = e + (a(b + e)* c) = e + ab*c R\l = b* + (b*a(a + e)*$) =b* R\2 = b*a + (b*a(a + e)* (a + e) = b*aa* Rj3 = b* c + (b*a(a + e)*b) = b* c + b*aa*b i?21 = 0 + ((a + e)(a + e)*0) = 0 R\2 = (a + e) + ((a + e) (a + e)* (a + e)) = a* Rj3 = b+ ((a + e){a + e)*6) = a*6 i4 = a6* + (ab*a(a + e)*0) = ab* Rl2 = ab* a + (ab*a(a + e)* (a + e)) = ab*aa* i?33 = (e + ab*c) + (ab*a(a + e)*6) = e + a6*c + ab*aa*b R\2 = b*aa* + ((6*c + b*aa*b){e + a6*c + ab* aa*b)* ab* aa*) = = b*aa* + ((b* c + b*aa*b)(ab*c + ab*aa*b)*ab*aa*) R313 = {b*c + b*aa*b) + {{b*c + b*aa*b){e + ab*c + ab*aa*b)*{e + ab*c + ab*aa*b)) = = (b* c + b*aa*b) + ((6*c + b*aa*b){+ab*c + ab*aa*b)*{e + a6*c + ab*aa*b)) R\2 = R\2, Ri3 = -R13 #(.4) = #12 + #13 fl & c -►1 2 1 3 ^2 2 3 — ^3 1 — — -^ľi = b + e #12 = a #13 = c #21 = 0 rL22 = a + e •"-23 = 6 #31 = a rL32 = 0 pO -"-33 = e Kapitola 4 Regulární výrazy 36 4.4 Využití vztahu regulárních výrazů k reg. jazykům 4.4.1 Důkazy uzáverových vlastností regulárních jazyků Dokážeme uzavřenost třídy regulárních jazyků vzhledem k substituci, a protože homomorfismus je vlastně speciálním případem substituce, tak i uzavřenost třídy regulárních jazyků vzhledem k homomorfismu (zatím jsme si tuto operaci ukázali jen na příkladu). Definice 4.2 (Substituce) použitá na řetězce znaků s operací zřetězení je zobrazení, které zachovává neutrální prvek (v našem případě prázdný řetězec e) a také samotnou operaci zřetězení, tedy: s(e) = e s (a o w) = s (a) o s(w) Rozdíl oproti homomorfismu: • homomorfismus přiřazuje každému znaku původní abecedy právě jeden řetězec, • substituce přiřazuje každému znaku původní abecedy množinu řetětců, v případě regulární substituce jde o množinu, která je reprezentovaná regulárním jazykem, • homomorfismus je tedy speciální případ substituce. Veta 4.2 Třída regulárních jazyků je uzavřena vzhledem k operaci substituce. Důkaz: Máme jazyk L\ nad abecedou Ei reprezentovaný regulárním výrazem. Substituce o je určena tak, že pro každý prvek abecedy Ei, a G Ei, máme regulární výraz a (a) nad abecedou Aa. Po uplatnění substituce vznikne jazyk a (Li) nad abecedou U Aa tak, že v regulárním výrazu původního jazyka nahradíme všechny symboly abecedy Ei příslušnými regulárními výrazy a (a). D Kapitola 4 Regulární výrazy 37 Příklad 4.3 ____________________________ L = a*b+(b*a)* a-! (a) = m*, (Ti (6) = p* q + p =>- <7i(L) = m*(p*q+p) + ((p*q+p)m*Y cr2(a) = c,a2(b) = c* => a?XL) = ďd+(ďď)* = ď (74(a) = e*, cr4(6) = /* ^ a4(L) = e*/* + (e*/*)* = (e*/*)* = (e + /)* 4.4.2 Normovaný automat Definice 4.3 (Normovaný automat) Normovaný automat je deterministický automat bez nedosažitelných stavů, jehož stavy jsou označeny jednoznačně (jednoznačným postupem). Účel: O dvou ekvivalentních automatech, které nejsou normované, můžeme říci, že jsou stejné až na označení stavů. Normováním si zjednodušíme porovnávání automatů, protože dva ekvivalentní normované automaty jsou shodné i včetně označení stavů (nemusíme prověřovat různé kombinace uspořádaných dvojic stavů). Postup: Stavy i automatu uspořádáme podle nejkratších slov z jazyků Li (budeme indexovat sestupně, „největší" slovo dostane nejmenší index). Porovnáváme podle délky, stejně dlouhá slova podle abecedy. • u každého stavu i automatu zjistíme nejkratší slovo příslušného jazyka Lir je možné, že budeme potřebovat více takových slov, • seřadíme podle délky sestupně, • pokud vyjdou dvě stejně dlouhá slova u více stavů, porovnáme je podle abecedy, Kapitola 4 Regulární výrazy 38 • pokud vyjdou stejná slova u více stavů, použijeme u každého druhé nejkratší slovo (atd. dokud nenajdeme rozdíl, ten najdeme určitě -jsou to různé jazyky), • seřazené stavy oindexujeme (pojmenujeme) od 1. Příklad 4.4 ____________________________________________________________ Znormujeme automat A = ({qo,Qi,Q2}, {a,b}, 5, q0, {qi}) a b ^go g2 q\ <-?i q\ g2 92 q\ Původní automat: <- 9i li 9i I * «' L(q0) = ba* + aa*b, nejmenší slova jsou b, ab, ba, aab,... L(qi) = a*, nejmenší slova jsou e, a, aa,... L(q2) = erb, nejmenší slova jsou b, ab, aab,... Jak vidíme, nejkratší slovo obsahuje jazyk L(qi), proto tomuto jazyku přiřadíme nejvyšší index (3). Zbývající dva jazyky mají první dvě nejmenší slova stejná, až v třetím slově se liší -ba < aab a proto jazyku L (q0) přiřadíme druhý nejvyšší index (2). b Po znormování: a b -^2 1 3 ^3 3 2 1 3 Jak si můžeme všimnout na příkladu 4.4 a jak můžeme také zjistit úvahou, koncové stavy většinou mívají přiřazeny nejvyšší indexy a proti směru výpočtu (tedy směrem od koncových k počátečnímu stavu) se indexy obvykle snižují. To však není tak úplně pravidlem - třeba v příkladu 4.4 nemá počáteční stav nejnižší index. 4.4.3 Minimalizace konečného automatu Minimalizací budeme rozumět především snížení počtu stavů automatu. Tento postup může být užitečný při porovnávání jazyků rozpoznávaných dvěma (napo- Kapitola 4 Regulární výrazy 39 hled) různými automaty, ale také při optimalizaci programů vytvořených stavovým programováním podle konečného automatu. Definice 4.4 (Ekvivalentní automaty) Dva konečné automaty A\ a A2 jsou ekvivalentní, pokud rozpoznávají tentýž jazyk, tj. L(Ai) = L(A2)- Definice 4.5 (Minimální automat) Konečný automat je minimální, jestliže neexistuje žádný s ním ekvivalentní automat, který má menší počet stavů. Veta 4.3 Ke každému konečnému automatu lze sestrojit ekvivalentní minimální konečný automat. Postup: • vytvoříme ekvivalentní deterministický automat, • odstraníme nedosažitelné stavy, • vytvoříme ekvivalentní redukovaný automat, • vhodně přeznačíme stavy - znormujeme automat. Využijeme konstrukci podílového automatu (viz podílová grupa apod.). Redukce stavů automatu Redukce stavů automatu A= (Q, £, ö, qo, F): • pro všechny stavy q automatu vytvoříme „pomocné" automaty Aq tak, že vezmeme původní automat A a stav q použijeme jako počáteční, tedy VqeQ: Aq = (Q,Z,6,q,F): označíme Lq = L(Aq), • zavedeme relaci ekvivalence ~ na množině stavů automatu Q, definujeme ji takto: pro jakékoliv dva stavy p, q E Q platí: p ~ q -<=>- Lp = Lq (dva stavy jsou ekvivalentní, pokud se rovnají jazyky příslušných pomocných automatů), • když při postupu ze dvou různých stavů dostáváme totéž, pak jsou tyto stavy zaměnitelné =3- můžeme je „shrnout" do jediného stavu, tedy všechny cesty mířící do q přesměrujeme do p a stav q odstraníme, Kapitola 4 Regulární výrazy 40 • toto odstraňování provádíme tak dlouho, dokud v automatu existují ekvivalentní stavy. Definice 4.6 (Podílový automat) Nechť A = (Q, £, ö, q0, F) je konečný automat bez nedosažitelných stavů. Vytvoříme třídy ekvivalence ~ obsahující některý stav q G Q: [q] = {p | p G Q,p ~ q} Podílový automat A^ podle ekvivalence ~;e A~ = {Q~, £, (L, [q0],F^), kde • Q~ = {[q]\qeQ}, • 5„([q],á) = [5(q,á)], • F. = {[/] I f e F} Konstrukci podílového automatu použijeme pro redukci stavů původního automatu, proto o takto vytvořeném automatu budeme hovořit také jako o redukovaném. Je poměrně snadné dokázat, že podílový automat je ekvivalentní s původním automatem („shrnujeme" cesty, které jsou shodné). Na příkladu si ukážeme vytvoření podílového automatu včetně hledání ekvivalentních stavů. Postup: Vytvoříme automaty Ai = (Q,T,,8,i,F) (jako počáteční stav použijeme i G Q), zajímají nás jazyky Li = L(Ai). Ty pak porovnáme a zpracujeme ekvivalentní. Budeme postupovat následovně: • vytvoříme množiny i?9 rekurzívně vypočteme další množiny R*- až ke k = 8, • zjistíme jazyky m = u R% a porovnáme je, pokud některé dva stavy rozpoznávají stejný jazyk, jeden z nich odstraníme s přesměrováním všech přímých cest vedoucích do tohoto stavu, • automat převedeme do normálního tvaru (znormujeme). Kapitola 4 Regulární výrazy 41 Příklad 4.5 ____ A=(Q,Z,Ó,1,F) ných stavů ({1,2,... ,8},{a,b},ö,l,{8}) deterministický bez nedosažitel- a 6 -►1 2 4 2 0 6 3 3 8 4 5 3 5 0 7 6 6 8 7 7 8 ^8 0 8 Jazyky L» vytvoříme postupem popsaným výše: Li = i??« = bbďbb* + abďbb* + babďbb* #18 L2 — ± (-28 ^3 = #38 L4 = it48 L58 Lr = Í?r ^5 ^6 L7 L8 #68 08 n78 08 •"-88 ba*bb* a*bb* ba*bb* ba*bb* a*bb* a*bb* b* abďbb* = L2 = L3 = L» Původní automat: a 6 -►1 2 4 2 0 6 3 3 8 4 5 3 5 0 7 6 6 8 7 7 8 ^8 0 8 © 7'>-1, zpracujeme stavy 5, 6, 7. ■©? Kapitola 4 Regulární výrazy 42 Po odstranění stavu 5: a 6 -►1 2 4 2 0 6 3 3 8 4 2 3 6 6 8 7 7 8 ^8 0 8 Po odstranění stavu 6: a 6 -►1 2 4 2 0 3 3 3 8 4 2 3 7 7 8 ^8 0 8 Po odstranění stavu 7: a b -►1 2 4 2 0 3 3 3 8 4 2 3 ^8 0 8 (D- 2 a 6\ a -> 6 0, Takto vytvořený automat je už sice redukovaný, ale ještě ne minimální. Abychom mohli splnit podmínku snadného porovnávání automatů, musíme náš automat ještě normovat. Využijeme jazyky dílčích automatů, které jsme zjistili dříve: Li = R818 = bbďbb* + abďbb* + babďbb* L2 = i4 = ba* bb* Kapitola 4 Regulární výrazy 43 3 = -Rgg = a* bb* 4 = -R48 = ba*bb* s = -R88 = b* abďbb* Z těchto jazyků vybereme nejkratší slova a ta porovnáme: Stav i Nejkratší slovo jazyka Li Nové označení stavu 1 abb 1 2 bb, bab,... 2 3 b 4 4 bb, abb,... 3 8 e 5 Výsledný automat po znormování: a 6 -►1 2 3 2 0 4 3 2 4 4 4 5 ^5 0 5 Kapitola w/____________________________________________ Formální gramatiky Až dosud jsme se zabývali možnostmi zjišťování, zda zadané slovo nebo posloupnost signálů vyhovuje daným podmínkám, tedy zda patří do určitého jazyka. V této kapitole se budeme zabývat možnostmi generování slov vyhovujících daným podmínkám, tedy patřících do určitého jazyka. 5.1 Generování slov jazyka Definice 5.1 (Základní pojmy formálních gramatik) • Abeceda je neprázdná konečná množina, jejíž prvky nazýváme znaky, symboly, signály. • Slovo nad abecedou E je konečná posloupnost symbolů abecedy E, tj.weT,*. • Jazyk na abecedou E je množina slov L nad abecedou E, tj. KE*, • Automat rozpoznává slovo, tj. dostane již existující slovo na vstup a rozhodne, zda patří do daného jazyka. • Gramatika vytváří (generuje) slova daného jazyka, popisuje strukturu jazyka. Použití gramatik při generování slov si nejdřív ukážeme na příkladu. 44 Kapitola 5 Formální gramatiky 45 Příl dad 5.1 L = a*(bc + cb*c) S - >aS © S - >bA © S - >cB © A- »c © B - ^6P © B - + c © Generujeme slovo ebbe: S=> cB^ cbB^ cbbB^ ebbe Není co přepisovat => konec Úspornější a přehlednější způsob zápisu (shrneme pravidla se stejnou levou stranou na jeden řádek): S -»• aS | bA | cB ®,©,@ B->bB\c (5),© Definice 5.2 (Formální gramatika) Formální gramatika je uspořádaná čtveřice (posloupnost) G = (N, T, P, S), kde • N je neprázdná konečná množina neterminálních symbolu (neterminální abeceda), • T je neprázdná konečná množina terminálních symbolu (terminálni abeceda), platí NC\T = $, • P je neprázdná konečná množina pravidel, P C ((N U T)*N(N U T)*) x (N U T)* jinak: aAß ->■ 7, Me A e N, a, ß, 7 G (AT U T)* • S* ;g startovací symbol gramatiky, S e N. Definice 5.3 (Relace kroku odvození =>) Nechť wi,w2 G (N U T)* pro gramatiku G= (N,T,P,S). Slovo w2 lze přímo (v jednom kroku) odvodit ze slova w\ (píšeme w\ =^g w2, obvykle stačí =>), jestliže existuje pravidlo (a —► ß) G P, wi = xicüx2, W2 = ^i/3x2 (podřetězec a nahradíme řetězcem ß). Symbol =^* je reflexivním tranzitivním uzávěrem relace =>, tj. například zápis w\ =>- W2 =>- w3 =>- W4 =>- W5 lze zkrátit na wi =^* w5. Kapitola 5 Formální gramatiky 46 Definice 5.4 (Jazyk) Jazyk generovaný gramatikou G = (N, T, P, S) je množina L(G) = {weT*\S^*Gw} Definice 5.5 (Vetná forma, věta) Vetná forma gramatiky G = (N, T, P, S) jekterékoliv slovo a takové, že S =^ a, tedy je to kterékoliv slovo, které lze odvodit ze startovacího symbolu pomocí pravidel gramatiky. Věta gramatiky G = (N, T, P, S) je taková vetná forma w, která se skládá pouze z terminálních symbolů, tedy S =^ w, w e T*. Můžeme říci, že jazyk generovaný gramatikou je množina všech vét této gramatiky. Definice 5.6 (Ekvivalence gramatik) Gramatiky Gx a G2 jsou ekvivalentní, pokud generují tentýž jazyk, tedy L(Gi) = L(G2). Definice 5.7 (Derivace) Derivace slova a délky n v gramatice G = (N, T, P, S) je posloupnost slov a,\, a2, ■ ■ ■ an taková, že • cüi = S, • cuí =^g Cüj+i Vi : 1 < i < n — 1. 5.2 Regulárni gramatiky Definice 5.8 (Regulární gramatika) Regulární gramatika je taková formálni gramatika G = (N, T, P, S), kde P je množina pravidel ve tvaru A^ a nebo A ->■ aB, kde A, B e N, a e T, pokud se S nevyskytuje na pravé strane žádného pravidla, může existovat i pravidlo S —► e. Věta 5.1 Jazyky generované regulárními gramatikami jsou pravé regulárni jazyky. Postup a princip důkazu si nejdřív ukážeme na příkladech. Příklad 5.2 ____________________________________________________________ G=({S,A}, {a,b,c,d}, P, S), kde v P jsou pravidla S —► aS | aA \ c A^bAlcS \d J3 Kapitola 5 Formální gramatiky 47 Vytvořený konečný automat: a b c d -^S S, A X A A S x ^X L = a* {ab* ca*)* {c + ab*d) = a* ab* (ca* ab*)* d + a*(ab*ca*)*c Příklad 5.3 _________________________________ G=({S,A,B}, {a,b}, P, S), kde v P jsou pravidla S -»■ aA | b | e A^bA\bB B ->■ aA\b Vytvořený konečný automat: a b ^S A X A A, B B A X ^X s)^-0< b a] t y—-v L = e + b + ab*b(ab*b)*b Důkaz: ,,^"(G=(N,T,P,S) -^ A= (Q,Z,ó,q0,F)) • abeceda E = T, počáteční stav q0 = S, • stavy Q = N U {X}, musí být X £ N {X je nově přidaný), • koncové stavy: - pokud (S -»■ e) e P, pak F = {X, S}, - jinak F = {X}, 5 funkce: - pro každé pravidlo (U —► aV) G P je Č(Č7, a) 3 V, - pro každé pravidlo (U —► a) G P je Č(Č7, a) 9 X. D Kapitola 5 Formální gramatiky 48 Příklad 5.4 ________________________ A = ({go, gi, g2, 9s}, {a, b}, Ö, g0, {q2, q3}) a b ~^qo q\ q\ qo,q2 ^92 92 qa ^93 93 9o ) iqi)--------*((<320)--------HI 93 Automat upravíme, abychom mohli použít postup přesně opačný postupu převodu gramatiky na automat: a b ^9o q\ q\ qo,q2,X 92 92, X 93, X qs 93, X ^x Výsledná gramatika a její úprava (jen nahradíme neterminály velkými písmeny): g0 -► aqi q\ -^ bq0 | bq2 \b q2 ^ aq2\bq3\ a\b q3 -► aq3\a S —► aA A^bS\bB\b B^aB\bC\a\b C —► aC I a L = (ab)*aba* + (ab)*aba*ba* = (ab)*aba* (e + ba*) Příklad 5.5 _______________________ A = ({9o, 9i, 92, 93}, {a, b, c}, 6, g0, {q0, q3}) a b c ^9o 9i 9i 92 9o,9i 92 92 93 ^93 1} G (£(2) - £(3)) Lmon = {anbncn | n > 1} G (£(1) - £(2)) 5.3.2 Související typy gramatik Dále v textu budeme také pracovat s těmito typy gramatik: 1. Kontextové gramatiky (CS - Context Sensitive) • pravidla ve tvaru aAß^a-fß, -f^e,AeN,a,ß,-fe(Nl)Ty Kapitola 5 Formální gramatiky 52 • může existovat pravidlo S —► e, pokud se S nenachází na pravé straně žádného pravidla • tato třída jazyků je ekvivalentní třídě jazyků typu 1 (nezkracujícím) - CS *á C(l) 2. Lineární gramatiky (LIN - Linear) • pravidla ve tvaru A ->■ aBß, A ->■ a, A, B G N,a,ßeT* • speciální případy lineárních gramatik: - pravolineární (RLIN) A —► ßB, A —► ß, stejně definované jako regulární - levolineární (LLIN) A^ Bß, A^ ß • LIN je speciální případ C F (bezkontextových) gramatik, dá se dokázat, že LIN C LIN L = {anbn | n > 1}+ G (CF - LIN) • RLIN = LLIN = REG, dá se dokázat, že REG C LIN L = {anbn | n > 1} G (LiW - REG) 3. Gramatiky generující konečné jazyky (FIN - Finite languages) • konečné jazyky lze generovat regulárními gramatikami: S —► první slovo | druhé slovo | třetí slovo | ... • platí FIN C REG L = a* G (REG - FIN) 5.4 Operace nad slovy a jazyky Následující definice se budou týkat jazyků Lx a L2 nad abecedou E, případně slov w\ a u>2 nad touto abecedou. Definice 5.10 (Operace zřetězení) Operace zřetězení slov je definována následovně: nechť wi = a\a2.. .an,w2 = &1&2 • • • bm. Jejich zřetězením je slovo w = w\ ■ w2 = a\a2... anb\b2.. .bmo délce n + m. Kapitola 5 Formální gramatiky 53 Operace zřetězení jazyků je definována následovně: Zřetězením jazyků Lx a L2 je jazyk L = Li ■ L2 = {wi ■ w2 | wi G Li,w2 G L2} Definice 5.11 (Operace sjednocení jazyků) Sjednocením jazyků Li a L2 je jazyk L = Li U L2 = {w G E* I w G Lx V w G L2} Definice 5.12 (Operace průniku jazyků) Průnikem jazyků Li a L2 je jazyk L = Li n L2 = {w G E* I w G Li&w G L2} Definice 5.13 (Operace komplementu (doplňku) jazyka) Komplementem jazyka Lx v abecedě E je jazyk L = L~i = {we^*\wÍLi) Definice 5.14 (Operace uzávěru jazyka) (iterace, nekonečné sjednocení) uzávěrem jazyka Li je jazyk oc L = L* = U L\, kde L\=Li-Li- ...-Li Definice 5.15 (Operace bez e-nového uzávěru jazyka) Je definována podobně: DC L = L+ = U Li, kde L\ = Li • Li • ... • Li •__^ ^---------------s/---------------/ celkem ix (rozdíl je v indexu pod sumou, zde je i > 0) Definice 5.16 (Operace zrcadlového obrazu) Operace zrcadlového obrazu slova je definována následovně: nechť wi = axa2 ...an. Jeho zrcadlovým obrazem je slovo w = Wi = anan-i... a2ai. Operace zrcadlového obrazu jazyka je definována následovně: Zrcadlovým obrazem jazyka Li je jazyk L = L? = {wR\ w G Li} Kapitola Bezkontextová jazyky V této kapitole se budeme zabývat jazyky odpovídajícími třídě jazyků Ĺ(2) (resp. C F) v Chomského hierarchii, tedy bezkontextovým gramatikám. 6.1 Bezkontextová gramatiky Definice 6.1 (Bezkontextová gramatika) Bezkontextová gramatika je gramatika, jejíž pravidla jsou ve tvaru A —► a, kde A e N, a e (N U T)* Příklad 6.1 ____________________________________________________________ Li = {wwR | w e {a, b}*} Gi = ({S}, {a, b}, P, S), kde množina P obsahuje pravidla S —► aSa \ bSb \ e Derivace: S =>- aSa =>- abSba =>- abbSbba =>- abbbba Příklad 6.2 L2 = (anbmcn \m,n> 0} G2 = ({S, A}, {a, b, c}, P, S), kde množina P obsahuje pravidla S —► aSc I aAc A^bA\b Derivace: S =>- aSc =>- aaAcc =>- aabAcc =>- aabbAcc =>- aabbbcc 54 6 Kapitola 6 Bezkontextové jazyky 55 Příklad 6.3 ______________________________________ L3 = {0ralm | 1 < n < m} G3 = ({A}, {0,1}, P, A), kde množina P obsahuje pravidla A^OAl | Al | 01 Derivace: A^OAl ^(L411 => 00111 Příklad 6.4 ____________________________________________ L4 = jazyk matematických výrazů obsahujících • celá čísla • operátory +, * (bez ohledu na prioritu) • závorky G4 = ({E}, {n, +,*,),(}, P, E), kde množina P obsahuje pravidla E ^ E + E\E*E\(E)\n Derivace: E^E*E^E + E*E^n + E*E^n+(E)*E^ =/- n + (E) * n => n + (n) * n Definice 6.2 (Derivační strom) Derivační strom některé derivace v bezkontextové gramatice G = (N, T, P, S) je uspořádaný kořenový strom (tj. souvislý acyklický graft, jehož uzly jsou ohodnoceny symboly z množiny N U T U {e} a platí: • všechny uzly kromě kořene mají jednoho předchůdce, kořen nemá žádného, • pokud je některý uzel ohodnocen symbolem A, jeho následníci po řadě symboly a\, a2, ... an, pak v množině pravidel P gramatiky existuje pravidlo A —► axa2... an, • jestliže uzel ohodnocený symbolem A má jediného následníka ohodnoceného symbolem e, pak v P existuje pravidlo A —► e, • kořen stromu je ohodnocen S, listy jsou ohodnoceny symboly e T U {e}, ostatní symboly e N. V každém kroku vytváření derivačního stromu tvoří listy větnou formu v gramatice. Kapitola 6 Bezkontextové jazyky 56 Příklad 6.5 ___________________________________________ Pravidla: E ^ E + E\E*E\(E)\n Derivace: E=>E*E=>E + E*E=>n + E*E=>n + n*E=>n + n*n Budeme postupně vytvářet derivační strom této derivace: n n n n n Obrázek 6.1: Postupné vytvoření derivačního stromu 6.2 Vlastnosti bezkontextových gramatik Zde se podíváme především na některé speciální tvary bezkontextových gramatik (u každého tvaru si uvedeme i vztah k obecné definici). Tyto speciální tvary mají smysl především tehdy, když navrhneme gramatiku pro určitý účel a potřebujeme, aby měla určité vlastnosti - převedeme do některého speciálního tvaru, který tyto vlastnosti má (například z důvodu snadnější programovatelnosti, třeba u syntaktické analýzy překladače). 6.2.1 Bezkontextová gramatika nezkracující Definice 6.3 (Nezkracující bezkontextová gramatika) Nezkracující bezkontextovou gramatikou (nevypouštějící) nazýváme takovou gramatiku, kde množina pravidel P buď neobsahuje žádné e-pravidlo, a nebo existuje jediné e-pravidlo S —► e a zároveň S není na pravé straně žádného pravidla. Veta 6.1 Nechť G je bezkontextová gramatika. Pak existuje gramatika G' bez e-pravidel taková, že L(G') = L{G) - {e}. Kapitola 6 Bezkontextové jazyky 57 Důkaz: Pro každý symbol A e N, který lze přepsat na e: • pro každé pravidlo B —► ß0Aß\A... Aßn, kde je A na pravé straně pravidla, simulujeme použití pravidla A —► e na různých místech - přidáme pravidla B^ ß0 ß1Aß2...ßn-lAßn B^ ßQAßl ß2...ßn.1Aßn B^ ß0AßxAß2.. A-i A> B^ ßo ßi ß2..-ßn-iAßn B —► A A /?2- • -Ai-i Ai • odstraníme pravidlo A —► e D Veta 6.2 Nechť G je bezkontextová gramatika. Pak existuje gramatika G' bez e-pravidel nezkracující taková, že L (G') = L (G). Důkaz: Postup závisí na tom, zda e ^ L(G). • Pokud e £ L (G), postupujeme dle předchozího důkazu. • Pokud e E L (G), postupujeme dle následujícího schématu (v G' bude jediné e-ové pravidlo S' —► e): G = (N, T, P, S) G1 = (N,T,P1,S) (vytvoříme podle postupu v předchozím důkazu) G' = (N\J {S'}, T, P', S'), kde P' = Pľ U {S' -»• e | S} D Převod obecné bezkontextové gramatiky na nezkracující si ukážeme na gramatice v příkladu 6.6. Kapitola 6 Bezkontextové jazyky 58 Příklad 6.6 ___________________________ Zadání: G = ({S, A, B}, {a, b, c}, P, S) S -»■ AaB | e A -► Abb A | aBc | e ß -»■ 6AS | aS Po prvním kroku: S ->■ AaS | aß A -► A66A | 66A | A66 | 66 | aBc B -»■ 6AS | 6S | aS | a Výsledek: G' = ({S',S, A,B}, {a,b,c}, P', S') S' ^ S\e S ->■ AaS | aß A -► A66A | bbA | A66 | 66 | aBc B -»■ 6AS I 6S I aS I a 6.2.2 Redukovaná gramatika Definice 6.4 (Nadbytečný neterminál) (zbytečný)X je nadbytečný neterminál, pokud neexistuje žádné terminálni slovo, které lze z tohoto symbolu vygenerovat, tj. neexistuje derivace X =^* w, w e T*. Definice 6.5 (Nedostupný symbol) Symbol X e (N U T) je nedostupný, jestliže se nemůže objevit v žádné vétné formé, tj. neexistuje derivace S =^* aXß, a, ß e (Ni) T)*. Definice 6.6 (Redukovaná gramatika) Bezkontextová gramatika je redukovaná, pokud neobsahuje žádné nadbytečné a nedostupné symboly. Postup: • odstraníme nadbytečné symboly, • potom odstraníme nedostupné symboly. Veta 6.3 Ke každé bezkontextové gramatice G existuje redukovaná gramatika G' taková, že L(G) = L(G'). Kapitola 6 Bezkontextové jazyky 59 Algoritmus odstranění nadbytečných symbolů 1. N0 = T 2. Ni = W,_iU {A G N I (A -»• a) G P, a G iV^J 3. N ^ Ni_i =>- inc(i), přechod na bod 2 4. JVi = iVi_i => konec algoritmu, N' = N n N Příklad 6.7 _________________________________________________________ Odstranění nadbytečných symbolů: S —► aAbC | c A -► aA | Cc ß ->■ cB | dL> C -»■ cB | aA | 6 D -^Bd No=T N = {S, C} U T N2 = {S, C, A} U T N3 = N2 =>N' = N3nN= {S, A, C} P' = {S -»■ aAbC \ c, A->aA\Cc, C aA | b} Algoritmus odstranění nedosažitelných symbolů 1. V0 = {S} 2. Vi = Vi-ľ U{Ie(JVUT)|(i^ aXß) e P, A e V*_x} 3. V, ^ Vi-\ => inc(i), přechod na bod 2 4. Ví = V-i =>- konec algoritmu, N = Vi n x, V = vr\T Příklad 6.8 _______________________________________ P: S -»■ aA | 6S | c A —► cS* | aA B -+bB\ cAB C -^aA\b Kapitola 6 Bezkontextové jazyky 60 P': S -»■ aA | bB \ c A —► cS | aA B -^bB\ cAB C-KiA\bS-KiA\bB\c A —► cS* | a^4 B ^bB\ cAB C -^aA\b P": N0 = T Ni = {S, C} U T N2 = {S, C, A} U T N3 = N2 =>N' = N3nN = {S,A,C} Greduk = (N", T", P", S) Důkaz: 1. sestrojíme množiny Ne = {A e N \ A ^* e} (podle postupu pro nadbytečné symboly, N0 = {e}) 2. sestrojíme novou množinu pravidel P': (a) pro každé pravidlo ve tvaru A —► a0BiaiB2 ... Bkak G P, k > 0, Bi G Ne Vi, 1 < i < k,\/a,j G cti ■ % $. Ne do P' přidáme všechna pravidla ve tvaru A —► cü0XiO!iX2 ... Xkoik, kde -X"i £ {Bi, e}, pokud vznikne A —► e, nepřidáme ho, (b) SeiV£ => (S" -»• e | S) G P', iV' = N U {S7} (c) S i Ne ^ N' = N, S' = S 3. G' = (N', T, P', S') D ^o = {S} Vi = {S, A, a, c} V2 = Vi => ív" = v2 n ív' = {5, A} =^T" = V2r\T = {a, c} Kapitola 6 Bezkontextové jazyky 61 6.2.3 Gramatika bez jednoduchých pravidel Definice 6.7 (Jednoduchá pravidla) Jednoduchá pravidla jsou pravidla ve tvaru A —> B, A, B e N (tedy na pravé i levé strane je jediný neterminál). Veta 6.4 Ke každé bezkontextové gramatice G lze sestrojit gramatiku bez jednoduchých pravidel G' takovou, že L (G) = L(G'). Důkaz: 1. \/A =6 N sestrojíme množinu Na' (a) NA,o = {A}, (b) NA,t = NA,t-i U{XeN\(B^X)eP,Be A^-i} (c) NA,i ^ NA,i-\ => inc(i), přesun na b), Na,í = Na,í-i =>- konec algoritmu, Na = Na,í 2. sestrojíme P': y (B —► a) G P, které není jednoduché, \/A e N takové, že B e Na, dáme do P' pravidlo A —► a D Příklad 6.9 ____________________________________________________________ E ^ E + T\ T T -^T*F\F F->(E)\i NE,o = {E} NTfi = {T} NEA = {E,T} NTA = {T,F} = NT NEt2 = {E,T,F} = NE NF,o = {F} = NF E^>E + T\T*F\(E)\i T^>T*F\(E)\i F->(E)\i Kapitola 6 Bezkontextové jazyky 62 6.2.4 Další typy bezkontextových gramatik Definice 6.8 (Gramatika bez cyklu) Gramatika bez cyklu je taková gramatika, ve které neexistuje derivace A =^+ A pro žádné A e N. Poznámka: Nezkracující gramatika bez jednoduchých pravidel je vždy bez cyklu (pozor, pouze implikace, protože mohou existovat gramatiky bez cyklu, které nejsou nezkracující nebo které nejsou bez jednoduchých pravidel). Definice 6.9 (Vlastní gramatika) Vlastní gramatika je gramatika bez cyklu, nezkracující, bez nadbytečných symbolů. Definice 6.10 (Gramatika bez levé rekurze) Gramatika bez levé rekurze je gramatika, ve které pro žádný neterminál A e N neexistuje derivace A =^+ Aa. Přímá levá rekurze znamená existenci pravidla A —► Aa, nepřímá existenci pravidla A ->■ ßAa, kde ß =^* e. Definice 6.11 (Gramatika bez pravé rekurze) Obdobně jako u levé rekurze, vyměníme slovo „levá" za „pravá". Věta 6.5 Ke každé bezkontextové gramatice G existuje gramatika bez levé rekurze G' taková, že L(G) = L(G'). Důkaz: (Odstranění levé rekurze) 1. převedeme gramatiku na vlastní (bez cyklu, nezkracující, bez nadbytečných symbolů), 2. každou sadu pravidel s levou rekurzí A —► Aa>i | Aa2 | • • • | Aan \ ßi\ ß2\ • • • \ßm nahradíme sadou pravidel A -* ßxÄ | ß2A< | ... | ßmA' \ßi\ß2\ ...\ßm A' —► 0L\N | a2A' | ... \anA' \ a\ \ a2 \ ... \ an Proč: původní sada pravidel generuje sekvenci řetězců air rekurze je ukončena tak, že před všechny řetězce c^ je vygenerován jeden z řetězců ßj, tedy vlastně vygenerujeme totéž, jen jinými pravidly. A =3- Aas =^ Aa\as =3- Aa^aia^, =>• ß2a-ja\as D J3 Kapitola 6 Bezkontextové jazyky 63 Příklad 6.10 Odstranění levé rekurze: A -»■ BC I a B -»■ SaC I A6 I ba C -► CC I 6 I CM -»• SC I a ß -»■ SaC I A6 I ba C -^CC\b\Cb A->BC\a B ->■ A6S' | 6aS' | ab | 6a £' -»• aCB' | aC C -»• bC | 6 C" -»■ CC' I 6C I C I b 6.3 Normálni formy pro bezkontextové gramatiky Pro bezkontextové gramatiky můžeme použít tyto normální formy: 1. Chomského normální forma 2. Greibachova normální forma Jejich účel je podobný jako účel dříve uvedených speciálních typů bezkontexto-vých gramatik - jejich vlastnosti se nám za určitých okolností mohou hodit. 6.3.1 Chomského normální forma Definice 6.12 (Chomského normální forma) Bezkontextová gramatika jev Chomského normální formě (CNF), jestliže každé pravidlo z množiny P je v některém z těchto tvarů: • A^BC,A,B,C eN, • A^ a,Ae N, aeT, • S —► e, jestliže S není na pravé straně žádného pravidla. Věta 6.6 Ke každé bezkontextové gramatice G existuje gramatika G' v CNF taková, že L(G) = L(G'). J3 Kapitola 6 Bezkontextové jazyky 64 Důkaz: 1. Převedeme gramatiku do tvaru vlastní gramatiky (nezkracující, odstraníme jednoduchá pravidla). 2. \/A —► a, kde \a\ > 2, nahradíme každý výskyt jakéhokoliv terminálu a neterminálem Na =^> v pravidlech s pravou stranou delší než 1 se vyskytují pouze neterminály 3. Přidáme pravidla Na —► a. 4. pro každé pravidlo A ->■ YľY2 ...Yn, n>3, A,Yi e N : A —► Y\Zi, Z\ —► Y2Z2, ... Zn_?J —► Yn_2Zn_2, Zn_2 —► Yn_{Yn (rozkouskujeme dlouhá pravidla) D Příklad 6.11 ___________________________________________________________ Původní gramatika G= ({S, A, B}, {0,1}, P, S) S -»• A | OSA | e A^ 1A | 1 | BI B ->■ OB | 0 | OSBA Úprava 1: Nezkracující gramatika G' = ({S', S, A, B}, {0,1}, F, S') S ^A\0SA\0A A^1A\1\B1 B ->■ OB | 0 | OSBA | OBA S' ^ S\e Úprava 2: Odstranění jednoduchých pravidel G" = ({S', S, A, B}, {0,1}, P", S') S ^1A\1\B1\ OSA | 0A A^1A\1\B1 B ->■ OB | 0 | OSBA | OBA S" -► L4 I 1 I 51 I OSA \0A\e Kapitola 6 Bezkontextové jazyky 65 Úprava 3: Terminály v pravidlech s pravou stranou delší než 1 G'" = ({S', S, A, B, N0, N,}, {0,1}, P'", S') S ->■ NľA | 1 | BNľ | N0SA | N0A A ->■ NxA | 1 | BJVi B ->■ A^oß | 0 | A^PA | A^PA 5' ->■ iViA | 1 | BJVi | A^SA | A^qA | e iVo^O AT! ->■ 1 Úprava 4: Rozkouskování pravidel G"" = ({S',S,A,B,No,N1,Z1,Z2,Z3},{0,l},P"",S') S ->■ A^A | 1 | BNľ | iV^i | NQA Zi -»SA A ->■ A^A | 1 | BJVj ß ->■ A^oß I 0 I N0Z2 | A^oZg Z2 —> oZ3 Z3 -^ BA S' ->■ A^A I 1 I BJVi I iV0Zi I NqA I e ATq^O AT! ->■ 1 6.3.2 Greibachova normální forma Definice 6.13 (Greibachova normální forma) Bezkontextová gramatika je v Greiba-chového normální formě (GNF), jestliže každé pravidlo z množiny P je v některém z těchto tvarů: • A ->■ aBxB2 ... Bn, n > 0, A, Bu B2, • • • Bn e N, a G T, • S —► e, jestliže S není na pravé straně žádného pravidla. Veta 6.7 Ke každé bezkontextové gramatice G existuje gramatika G' v GNF taková, že L(G) = L(G'). Kapitola 6 Bezkontextové jazyky 66 Důkaz: 1. Převedeme gramatiku do tvaru vlastní gramatiky (nezkracující, odstraníme jednoduchá pravidla), odstraníme levou rekurzi. 2. V každém pravidle za nejlevější neterminál dosazujeme všechna jeho pravidla rekurzívně tak dlouho, dokud řetězec nezačíná terminálem. 3. Terminály a, které nejsou na začátku některého pravidla, nahradíme pomocnými neterminály Na. 4. Přidáme pravidla Na —► a. D Příklad 6.12 ___________________________________________________________ Původní gramatika G=({E,F},{(,),+,i},P,E) E ->■ E + F\ F F->(E)\i Úprava 1: Odstranění levé rekurze G' = ({E,E',F},{(,),+,i},P',E) E ->■ FE' \F E' ->■ +FE' I + F F->(E)\i Úprava 2: Odstranění jednoduchých pravidel G" = ({E,E',F},{(,),+,i},P",E) E ->■ FE' \ (E) | i E' ->■ +FE' | + F F->(E)\i Úprava 3: Rekurzivní nahrazování G'" = ({E,E',F},{(,),+,i},P"',E) E ->■ (E)E' | iE'\ (E) | i E' ->■ +FS' | + F F->(E)\i Kapitola 6 Bezkontextove jazyky 67 Úprava 4: Terminály G"" = ({E,E',F,N)},{(,),+,i},P"",E) E ->■ (EN)E' | iE'\ (EN) \ i E1 ->■ +F£' | + F F ->■ (£ľiV) | z