Slezská univerzita v Opavě fllozoficko-přírodovědecká fakulta ústav informatiky Teorie jazyků a automatů STUDIJNÍ TEXTY Poslední změny: 24. června 2007 ■v Mgr. Šárka Vavrečková sarka.vavreckova@fpf.slu.cz http://fpf.slu.cz/~vavlOui Opava 2007 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 1 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 Úvod Tento dokument je zatím v první fázi vývoje, tedy zatím jsou doplňovány kapitoly. Text není ve stavu vhodném pro plné samostudium, vyžaduje komentář vyučujícího a odpovídá přibližně obsahu prezentací z přednášek. Je určen pro studenty prezenčního a kombinovaného studia Slezské univerzity navštěvující kurz Teorie jazyků a automatů. 1 - 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 —► [6egm]a[end] P: P —► [výpis]T T —► [písmenko] T —► [pismenÄ;o]T 5 =>• [6egm]a[end] =>- [6egm]P; [end] =>- [6egm]P; P; [end] =>- [öegm] [ví/pis]T; P; [end] =>- [begin][vypis][pismenko]T; P; [end] ... =>- [öegm] [výpis] [pismen/co] [písmenko] [písmenko]: [výpis][pismen/co][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 =>■ 64 =>■ 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 ô{qha) = q j (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,abcd) h (q3,bcd) h (qucď) h (q3,ď) h (q3,e) kde všechny přechody mezi konfiguracemi jsou určeny funkcí ô : ô(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,Y,,ô,q0,F) rozpoznáva (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 E), tedy KS*, 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 Lj, pokud přijímá právě slova jazyka Lj (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}, Ô, q0, {gi}) Diagram: 5 funkce CY ^—T^ S(q0ia) = ^) (TÍŽiH 8(q0,b) = = qo = Qi S(qi,b) = qo Jeden z možných výpočtů v automatu: {q0,aab) h (q0,ab) h (q0,b) h (qi,e) Jazyk automatu: L(A) = {a*b} ■ {(ba*bY | i > 0} {{a*bb)*a*b} Tabulka: stav\vstup a b ->■ Qo Qo Qi <- Qi - Qo {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 ô : QxE^ 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) = {w E E* I (q0,w) K (qf,e),qf E 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. Věta 2.1 Nechť A je nedeterministický KA. Potom existuje deterministický KA A' takový, že L (A) = L (A1) (tj. rozpoznávají stejný jazyk). Důkaz: A= (Q, E, ô, q0, F) nedeterministický (ten máme) A' = {Q'i ^> 190) F') deterministický (ten chceme vytvořit) Stavy nového automatu budou odpovídat množinám stavů původního. Pro každou rovnost 5(q,na) = {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^0 - koncové stavy jsou všechny, které (coby množiny) obsahují alespoň jeden původní koncový stav, • ó'(M,a) = {q | q E ó(p,a),p E M} - všechny prvky množiny zpracujeme podle původního automatu, pak shrneme výsledky do množiny. □ Pokud pracujeme s reprezentací 5-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 {gi; g,-,...}, pak do buňky sepíšeme obsah buněk na řádcích {g^}, {qj}, ... 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} Nedeterministický: A = {9o,gi,92},{a,6},5,go,{92}) A a b A' = (Q>,Ľ,ô>,q>0,F>) ->■ Qo - <- q2 - - Deterministický: Odstraníme nepotřebné stavy: A a b A a b -{?o} {Qo} {qo,qi} Í9o} Í9o, 9i} M 0 M {io,qi} {9o} {90,91,92} 0 0 ^- {90,91,92} {9o} {90,91,92} {qo,qi} tio} {Qo,Qi,Q2} <- {Qo,Qi,Q2} M {Qo,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 5 je totální: \/q g Q,\/a g S 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álni automat A' 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ý: Zúplnění: A 0 1 -»■ A A B B C - — C - C 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 qi takový, že neexistuje posloupnost přechodů (q0,w) h* {qi,w') tedy nelze se do tohoto stavu dostat z počátečního stavu. Definice 2.14 (Nadbytečný stav) Nadbytečný stav je stav qi 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 Qi - Qi <- Q2 - - Q3 <- g4 - ■n a 50 = {■ Qo Qi - Qi <- Q2 - - •n % ) a *(21] a »(( Q2 Kapitola 2 Konečné automaty 17 Postup: • vytvoříme množinu So, do ní dáme počáteční stav automatu, So = {90}, • vytvoříme množinu Si 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 Sj_i, • končíme, když už se do množiny nic nedá přidat, tedy Si = Sj_i, výsledkem je nová množina stavů. Vzorec: 50 = {qo} 51 = Si-x u {q I ô(p,a) 3 q,p g Si-^a g S} 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 qi 93 94 92,95 92 - qs 94 - 94 95 94 95 95 - E0 = {q±, ŕfe}, hledáme prvky Ei_i v buňkách řádků, přidáme označení řádků Ei = {qi, 92, 9o} (z 9o se dá dostat do gi) -^2 = {91, 92, 9o} = Ei ... nová množina stavů Po úpravě: ->■ 9o 9i 93 <- 9i 92 <- 92 92 - Kapitola 2 Konečné automaty 18 Postup: • odstraníme nedosažitelné stavy, • vytvoříme množinu E0, do které zařadíme všechny koncové stavy automatu, tj. E0 = 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 E;t 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_lr • končíme, když už se do množiny nic nedá přidat, tedy Ei = E^i, výsledkem je nová množina stavů. Vzorec: E0 = F Ei = Eí-x u {q I ô(q,a) 3 p,p g E^x,a g S} 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 g 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 g M je také slovem tohoto jazyka, tedy xykz g 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^1^) ■ s (tedy x = a2, y = a2(l_1), z = a° = e) Použijeme číslo k > 0: k = 0 : xy°z = a2 e L...............................OK k = 1 : xy1z = a2i g L...............................OK k = p:xypz = a2+p*2(i-l) = a2^-^1) g 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í. OK 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 E 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éslovow; E 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} A = ({po,Pi,P2>, 5i,Po, {Pi,P2» L2 = {aV | i > 0, j > 0} A2 = ({q0,qi,q2}, {a,c}, 52,q0, {qi,q2}) L = Li U L2 = {(JV | i > 0, j > 0} U {aV | i > 0,j > 0} ■A = ({s0,Po,Pi,P2, 90,91,92}, {a,&,c}, 5, s0, {Pi,P2, 9i, 92}) Původní: Po sjednocení: a Kapitola 3 Regulární jazyky 24 A1 b c ^Po Pl Pl P2 P2 A2 b c -> Qo <- Qi Q2 Q2 A a b C so Pi,Qi Po Pi Pi P2 P2 Qi <- 9i Q2 <- Q2 Q2 3.3.2 Zřetězení Veta 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 Li a L2 jsou rozpoznávány automaty Ä! = (Qi, Si, 5i, ql, Lľ = L(Ä!) a A2 = (Q2, S2, 52, g02, F2), L2 = L(A2), Q1nQ2 = 0. Vytváříme jazyk L = Lľ ■ L2 a automat .4 = (Q, S, 5, g0, F), L = L (A). • 9o = ql, • q = QiUQ2, • E = E1UE2, • pokud e L2, pak F = F2, jinak F = F1 U F2 ÍSi(p,a) \ p e Qi - F1, 52(p,a) \ peQ2, □ 6i(p,a) U52(ql,a) \peF1 Příklad 3.4 _ Li = {a%b \ i>0} Ai = ({p0,Pi}, {a,b}, 5i,p0, {pi}) L2 = {(abayc^ \ i > o} A2 = ({q0,q3}, {a, b, c}, ô2, q0, {q0, qľ}) A = ({po,Pi, qo,qi,q2, qs}, {a,b,c}, ô,p0, {pi,qo,qi}) Kapitola 3 Regulární jazyky 25 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 Li je rozpoznáván automatem Á! = (Qi, Si, 5i, ql Li = H-Á!). Vytváříme jazyk L = L\ a automat A = (Q, S, 5, q0, F), L = L(A). • Qo = ql, • Q = Qi, • s = sx, • F = F1U{q0}, [ 5i(p,a) U 5i(g^,a) | p G Fi Příklad 3.5 _ Li = {albb \ i>0} Ai = ({p0,Pi,P2}, {a,b}, 5upo, {p2}) A = ({po,Pi,P2>, 5,po, ÍPo,P2}) Původní: Po iteraci: Kapitola 3 Regulární jazyky 26 3.3.4 Pozitivní iterace Věta 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 L\ je rozpoznáván automatem Ai = (Qi, Ei A, qo, -Fi), Lx = L(Ai). Vytváříme jazyk L = L\ a automat A = (Q, E, 5, q0, F), L = L(A). • Qo = ql, • Q = Qi, • S = Ei, • F = Fi, [ 5i(p,a) U ô^q^a); p G F1 □ Příklad 3.6 _ Li = {ďbb | i > 0} .Ai = ({p0,Pi,P2}, {«,&}, či,p0, {M) ■A = ({po,Pi,P2>, {M}, 5,po, M) Původní: Po pozitivní iteraci: 3.3.5 Zrcadlový obraz Věta 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 Ai = (Qi, Ei A, Fi), Li = L(^i). Vytváříme jazyk L = Lf a automat ^4 = (Q, E, 5, 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. qo 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 = QiU qo, £ = E1, F = {ql) 5{p,a) {p I 5i(p,a) 3 p} PÝQo {P I 5i(p, a) = P] U {p I 5i(p, a) = p 3 9/, 9/ G F} P = Qo □ Příklad 3.7 _ Lx = jaĎ^1-2} | i > OJ U {a6ťc | i > 0} = {ab* \ i > 0} o {a, aa, c} ■Ai = ({90,91,92,93}, K&,c}, 5i,g0, {92,93}) ■A = ({90,9i, 92, 93, s0}, {a,&,c}, 5, s0, {90}) L = Lf = {a, aa, c} o {tfa \ i > 0} Původní: Po zrcadlení: Ol' qo ))-*^—( qi )-* 92 H- so c \ /-—^ /a qs 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 L\ a L2 jsou rozpoznávány automaty Kapitola 3 Regulární jazyky 28 Ä! = (Qi, Si, Ô!, ql, Fi), Li = L(^li) a A = (Q2, S2, ô2, ql F2), L2 = L(A2), Qif]Q2 = 0. Vytváříme jazyk L = Lľ n L2 a automat ^4 = (Q, S, ô, 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}, • F = {\quqj] I qt G Fuqj G F2}, • S = Si U S2 (nebo S = Sx fl S2, vyjde to nastejno), • $([ 0} L2 = {abn I n > 0} Dva původní automaty: Pracujeme zároveň v obou automatech: Výsledný automat: Kapitola 3 Regulární jazyky 29 3.3.7 Homomorfísmus Definice 3.4 (Homomorfísmus) použitý na řetězce znaků s operací zřetězení je jednoznačné zobrazení, které zachováva neutrální prvek (v našem případě prázdny ř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 L\ je rozpoznáván automatem A\ = (Qi, S1; 6i, r/o, Fi), Li = L(Ai), a dále že existuje homomorfísmus h definovaný pro všechny symboly jazyka Ex. Vytváříme jazyk L = h(Li) a automat A = (Q, S, ô, q0, F), L = L (A). Postup si ukážeme na příkladu. Příklad 3.9 _ Lx = {ab* | i > 0} h(a) = ccc, h(b) = cd hfa) = {c3(cdY | i > 0} Původní automat: Po aplikaci homomorfismu: 0} Ri = a*c(ab)* L2 = {l2iw | i > 0,w E {0,1}*} R2 = (11)(11)*(0 + 1)* L3 = {ďb | i > 0} U {b*a \ i > 0} R3 = aa*b + b*a L4 = {£} U ({a&V | i > 0} U {62a2i+1 | i > 0}) o {c^ | i > 0} i?4 = £ + (abbbba* + bba(aa)*)ca* 4.3 Vztah ke konečným automatům Veta 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 S 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 f3 dokážeme sestrojit konečné automaty (včetně těch v bázi), • 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 + (3, a ■ (3 a (a)*. □ 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: Rij = {w<=Ľ*\(i,w) \~X (j,e)} 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 U Rik keF (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ů). □ Pro postupnou konstrukci množin R^ použijeme: R^j = {w £ Ríj | pokud existuje m : (i,w) K^. (m,u) K^. (j,e), (4.1) w ý u ý ei 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: pfc+l _ rafc i / pfc i nk \* ryk To je rekurzivní vzorec pro výpočet množin - 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 (^T).. 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: (QO^+i,fe+i . ",./•• • I "ŕ • I,; . ?j.. první případ použijeme, když ve stavu i existuje smyčka přes tento stav: F^i = a + e druhý případ použijeme pro stav, ve kterém neexistuje smyčka (máme pouze „prázdný přechod"): R% = e třetí případ použijeme pro dva různé stavy i a j, mezi kterými vede přímý přechod: R®, a • pokud mezi stavy i a j nevede přímý přechod, bude = 0. Postup: • vytvoříme pomocí definice automatu (z tabulky nebo diagramu), • podle rekurzívního vzorce vypočteme další množiny R^ až ke k = n, • platí Rlj = Ríj, dostaneme pro i = 1 a j E 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 UjeF 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 a & c ->■ 1 2 1 3 ^2 2 3 — ^3 1 — — R12 R13 R21 raO -fx22 ^23 #31 #32 #33 #11 #12 #13 #21 r>2 -fx22 #23 #31 #32 #33 #12 #13 Rl2 — R(A) b-a c #íi R) 12 13 {b + e) + ((b + e)(b + e)*(b + e)) a+ ((b + e)(b + e)*a) = b*a c+ ((b + e)(b + e)*c) = b*c b* i4 = 0 ral -"-22 ral -"-23 #31 #32 #33 {a + e) + V) = a + e & + 0 = b a+ (a(b + e)*(b + e)) = ab* 0 + (a(b + e)*a) = ab*a e + (a(b + e)* c) = e + ab*c b* + {b*a(a + e)*%) = b* b*a + (b*a(a + e)* (a + e) = b*aa* b* c + (b*a(a + e)* b) = b* c + b*aa*b 0 + ((a + £)(a + £)*0) = 0 (a + e) + ((a + e) (a + e)*(a + e)) = a* b+ ((a + e){a + e)*b) = a*b ab* + (ab*a(a + e)*0) = ab* ab*a + (ab*a(a + e)* (a + e)) = ab*aa* (e + a&*c) + (ab*a(a + = £ + a&*c + ab*aa*b b*aa* + ((6* c + b*aa*b)(e + a&*c + ab* aa*b)* ab* aa*) = b*aa* + ((6* c + b*aa*b)(ab*c + ab* aa*b)* ab* aa*) (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) + ((b* c + 6*aa*6)(+a6*c + ab*aa*b)*(e + a&*c + ab*aa*b)) R12, Ri3 = R\2 + R #13 13 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 a je určena tak, že pro každý prvek abecedy Ei, a e Ei, máme regulární výraz a(a) nad abecedou Aa. Po uplatnění substituce vznikne jazyk cr(Li) nad abecedou U a. 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). □ Kapitola 4 Regulární výrazy 37 Příklad 4.3 _ L = a*b+(b*a)* • o-i(L) = m* (p* q + p) + {{p* q + p)m*)* a2(a) = c, o-2(6) = c* (72 (L) = C* C* + (C* C)* = C* (73(0) = ď, (73(6) = (Í a3(L) = ďd+ (ďď)* = ď (74(a) = e*, (74(6) = /* (74(L) = ď f* + (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 = ({90,91,92}, {a,b}, 6, q0, {qi}) Původní automat: a b ->■ 9o 92 9i <- 9i 9i 92 92 9i L(q0) = ba* + aa*b, nejmenší slova jsou b, ab, ba, aab,... L(qi) = a*, nejmenší slova jsou e, a, aa,... L(g2) = a*b, nejmenší slova jsou b, ab, aab,... Jak vidíme, nejkratší slovo obsahuje jazyk L(q1), 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(A\) = 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ů. Věta 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,T>,ô,q0,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 VgeQ: Aq = (Q,E,ó,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é =>- 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,T,,ô,qo,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 I p e Q,p ~ q) Podílový automat A^ podle ekvivalence ~ je A^ = {Q~, S, ô~, [qo],F^), kde • Q~ = {[q] \qeQ}, • M = [S (q, a)], • F„ = {\f\ \feF} 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, S, ô, 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 R°j, rekurzívně vypočteme další množiny až ke k = 8, • zjistíme jazyky m = u K 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,Ľ,Ô,1,F) ných stavů ({1,2,... ,8}, {a,b}, ô, 1,{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 (i) ■o ■n -»> 6 Jazyky L{ vytvoříme postupem popsaným výše: U - R18 = bba*bb* + aba*bb* + babďbb* L2 — P?8 — -"-28 = ba*bb* L3 — P?8 -"-38 = a*bb* U — F?8 -"-48 = ba*bb* - f- abďbb* L5 = ^58 = bďbb* = L2 L6 — F?8 — -"-68 = a*bb* = L3 L7 — F?8 — _n.7g = a*bb* = U L8 — F?8 — -f^ss = b* Původní automat: a b ->■ 1 2 4 2 0 6 3 3 8 4 5 3 5 0 7 6 6 8 7 7 8 ^8 0 8 (1) 'D -n -> 6 zpracujeme stavy 5, 6, 7. .(TV? Kapitola 4 Regulární výrazy 42 Po odstranění stavu 5: a b ->■ 1 2 4 2 0 6 3 3 8 4 2 3 6 6 8 7 7 8 ^8 0 8 Po odstranění a b ->■ 1 2 4 2 0 3 3 3 8 4 2 3 7 7 8 ^8 0 8 Po odstranění a b ->■ 1 2 4 2 0 3 3 3 8 4 2 3 ^8 0 8 •n •n -> 6 t b\ a n 3 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: Lx = R8l8 = bbďbb* + abďbb* + babďbb* L2 = R828 = bďbb* Kapitola 4 Regulární výrazy 43 U U U R R. R% 38 48 a*bb* ba*bb* + abďbb* b* Z těchto jazyků vybereme nejkratší slova a ta porovnáme: Stav i Nejkratší slovo jazyka Lí 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í: n a 0- A 5 b A © S - > cB © A - > c © B - > bB © B - > c Generujeme slovo cbbc: S=> cB^- cbB^r- cbbB^r- cbbc 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 ©,©,© A -»■ c © B ^bB\c ©,© Definice 5.2 (Formální gramatika) Formální gramatika je uspořádaná čtveřice (posloupnost) G = (N, T, P, S), kde • iV /e 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í N n T = 0, • P/e neprázdná konečná množina pravidel, P C ((iV U T)* N (N U T)*) x (iV U T)* jinak: aA/3 -»■ 7, fafe A G iV, a, /?, 7 G (iV U T)* • S je 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 wi =^G w2, obvykle stačí jestliže existuje pravidlo (a —► f3) G P, wi = xiax2, w2 = xi/3x2 (podřetězec a nahradíme řetězcem f3). Symbol je reflexivním tranzitivním uzávěrem relace =>, tj. například zápis wi => w2 =>- w3 =>- W4 =>• W5 lze zkrátit na w\ w5. Kapitola 5 Formální gramatiky 46 Definice 5.4 (Jazyk) Jazyk generovaný gramatikou G = (N, T, P, S) je množina L (G) = {w e T* | S ^*Gw} Definice 5.5 (Vetná forma, věta) Větná forma gramatiky G = (N, T, P, S) je kterékoliv slovo a takové, že S =^G 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á větná forma w, která se skládá pouze z terminálních symbolů, tedy S =^G w, w g T*. Můžeme říci, že jazyk generovaný gramatikou je množina všech vět této gramatiky. Definice 5.6 (Ekvivalence gramatik) Gramatiky G\ 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 cti, cí2, ... an taková, že • «1 = S, • dn d, • cti =^g Cíi+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 nebo A aB, kde A, B e N, a e T, pokud se S nevyskytuje na pravé straně žádného pravidla, může existovat i pravidlo S —► e. Veta 5.1 Jazyky generované regulárními gramatikami jsou právě regulární 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^bA\cS\d Kapitola 5 Formální gramatiky 47 Vytvořený konečný automat: 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 L = e + b + ab*b(ab*b)*b Důkaz: = (N,T,P,S) A = (Q,T,,ô,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) G P, pak F = {X, 5}, - jinak F = {X}, • ô funkce: - pro každé pravidlo (U —► a V) G P je ô(U, a) 3 V, - pro každé pravidlo (U —► a) G P je a) 9 X. □ Kapitola 5 Formální gramatiky 48 Příklad 5.4 _ ■A = ({qo, 9i, 92, gs}, {a, b}, ô, g0, {q2, g3}) a b ->■ go 9i 9i 9o,92 <- 92 92 93 <- 93 93 Automat upravíme, abychom mohli použít postup přesně opačný postupu převodu gramatiky na automat: a b -> 9o 9i 9i 9o, q2,x 92 g2,X gs,x 93 gs,x Výsledná gramatika a její úprava (jen nahradíme neterminály velkými písmeny): q0 aq1 gi bq0 | bq2 \b g2 —► aq2 | bq3 \ a \ b q2 | c C —► aC | c L = e + (ab*b)*ab*(b + aa*c) Důkaz: „<=" (A=(Q,i:,5,qo,F) G = (N,T, P, S)) • upravíme automat - upravený je A' = (Q', S, ô', q'0, F') - F' = {X}, - duplikujeme přímé přechody vedoucí do původních koncových stavů, vytvořené přesměrujeme do X, - pokud q0 E F, vytvoříme nový počáteční stav S, F' = {X, S}, q'0 = S, Va G E : ô'(S, a) = ô(qo, a), • T = E, N = Q' -{X}, startovací symbol je q'0, • pravidla P: - pro všechny přechody ô(qi,a) 3 qj (qi —► aqj) E P, pokud qj £ F', - jinak (qi —► a) E P, - jestliže S E F', pak (S -»■ e) E P. □ Kapitola 5 Formální gramatiky 50 5.3 Chomského hierarchie gramatik Po jazykovědci Noamu Chomském je pojmenována hierarchie základních typů formálních gramatik. Gramatiky v této hierarchii mají jedno společné - sekvenční způsob generování slova. To znamená, že v každém kroku odvození je použito právě jedno pravidlo na právě jednom místě v přepisovaném slově. V hierarchii najdeme čtyři typy gramatik označených čísly 0,1, 2, 3. Třídy (tedy množiny) jazyků generované těmito gramatikami označujeme £(0),£(1),£(2),£(3). Mimo hierarchii, ale v těsné vazbě na ni, existují další typy gramatik, na které se také podíváme. 5.3.1 Gramatiky v Chomského hierarchii Chomského hierarchie zahrnuje tedy čtyři typy gramatik. U každého typu si uvedeme případný slovní název a dále označení, které se kromě Ĺ(číslo) používá pro označení související třídy jazyků, tvar pravidel a ekvivalentní stroj, který rozpoznává stejnou třídu jazyků. Definice 5.9 (Gramatiky Chomského hierarchie) 1. Gramatiky typu 0 (rekurzívně vyčíslitelné, RE - Recursively Enumerable) • žádné zvláštní podmínky na tvar pravidel (jen na levé straně musí být alespoň jeden neterminál): (N U T)*N(N U T)* x (N U T)* jiný zápis: o.\ i -»7, A e N, a, (3,7 e (N U T)* • ekvivalentní stroj: Turingův stroj (TS) 2. Gramatiky typu 1 (nezkracující, monotónni) • pro pravidla musí navíc kromě podmínek gramatik typu 0 platit: a->/3, \a\<\/3\, a,(3e(NUT)* • může existovat pravidlo S —► e, pokud se S nenachází na pravé straně žádného pravidla Kapitola 5 Formální gramatiky 51 • gramatiky se nazývají nezkracující, protože generované slovo se po jednotlivých krocích bud'prodlužuje, nebo sejeho délka nemení, ale nezkracuje se • ekvivalentní stroj: lineárně ohraničený automat (LOA, LBA - Linearly Bounded Automaton) 3. Gramatiky typu 2 (bezkontextové, C F - Context-free) • pravidla ve tvaru A^a, A e N, a e (N U T)* • ekvivalentní stroj: zásobníkový automat (ZA) 4. Gramatiky typu 3 (regulární, REG - Regular) • pravidla ve tvaru A —► aB, A ^ a, A, B e N,a e T • může existovat pravidlo S —► e, pokud se S nenachází na pravé straně žádného pravidla • ekvivalentní stroj: konečný automat (KA) Veta 5.2 Mezi třídami jazyků generovaných gramatikami v Chomského hierarchii jsou tyto vztahy: £(3) C £(2) c £(1) C £(0) Pro korektní důkaz tohoto tvrzení ještě nemáme dostatek znalostí, proto si jen uvedeme jazyky, které lze použít v důkazu prvních dvou inkluzí: LCF = {anbn | n > 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 aAB^a-f/3, 7 + e, A g N, a, £,7 g {N u T)* 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 (LLN - Linear) • pravidla ve tvaru A ->■ aB/3, A ->■ a, A, B G N, a, /3 G T* • speciální případy lineárních gramatik: - pravolineární (RLLN) A —► (3B, A —► stejně definované jako regulární - levolineární (LLLN) A^ Bfi, A^ $ • LJA^ je speciální případ C F (bezkontextových) gramatik, dá se dokázat, že LLN C LLN L = {anbn | n > 1}+ G (OF - LJiV) • RLLN = LLLN = REG, dá se dokázat, že REG C LLN L = {anbn | n > 1} G (LJiV - AEG) 3. Gramatiky generující konečné jazyky (FLN - Finite languages) • konečné jazyky lze generovat regulárními gramatikami: S —► první slovo | druhé slovo | třetí slovo | ... • platí FLN c REG L = a* G (REG - FLN) 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 wi a w2 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 = bľb2... bm. Jejich zřetězením je slovo w = wi ■ w2 = a±a2 ... anbib2 .. .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ů L\ a L2 je jazyk L = Li • L2 = {w1 ■ w2 | w1 g L1,w2 g L2} Definice 5.11 (Operace sjednocení jazyků) Sjednocením jazyků Lľ a L2 je jazyk L = Li u L2 = {w g E* I w g Lľ v w g L2) Definice 5.12 (Operace průniku jazyků) Průnikem jazyků L\ a L2 je jazyk L = Li h L2 = {w g S* I w g Lľkw g L2} Definice 5.13 (Operace komplementu (doplňku) jazyka) Komplementem jazyka L1 v abecedě E je jazyk L = T[ = {w g E* | w i Li} Definice 5.14 (Operace uzávěru jazyka) (iterace, nekonečné sjednocení) uzávěrem jazyka Li je jazyk oc L = L{= [J L\, kde L\ = Lx ■ Lx ■ ... ■ Lx celkem ix Definice 5.15 (Operace bez e-nového uzávěru jazyka) Je definována podobně: oc L = L\ = (J L\, kde L\ = Lx ■ Lx ■ ... ■ Lx 1 ^ 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 = a\a2.. .an. Jeho zrcadlovým obrazem je slovo w = = anan_i... a2ax. Operace zrcadlového obrazu jazyka je definována následovně: Zrcadlovým obrazem jazyka L\ je jazyk L = L[l = {wR\ w g Li} • 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 Kapitola 6 Bezkontextové jazyky 55 Příklad 6.3 _ L3 = {0nlm | 1 < n < m} G3 = ({A}, {0,1}, P, A), kde množina P obsahuje pravidla A —► 0A1 | Al | 01 Derivace: A =>■ 0A1 =>■ 0A11 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 + (íí) * íi 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ý graf), 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íf a2, ... an, pak v množině pravidel P gramatiky existuje pravidlo A —► a^a2... 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 G T U {e}, ostatní symboly G 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: E E E E E E + E E + E E + E E + E 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 —► f30Af3iA... A/3n, kde je A na pravé straně pravidla, simulujeme použití pravidla A —► £ na různých místech - přidáme pravidla B^ /?0 p1Ap2...pn_1Apn B^ faA^Afo...^ i5n • odstraníme pravidlo A —► e □ Veta 6.2 Nechť G je bezkontextová gramatika. Pak existuje gramatika G' bez s-pravidel nezkracující taková, ze 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 U {S'}, T, P', S'), kde P' = P1 U {S' e \ S} □ 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 AbbA | aBc \ e B -»■ | aS Po prvním kroku: S Aa5 | a5 A | | Abb \ bb \ aBc B -> | | a5 | a Výsledek: G' = {{S',S,A,B}, {a,b,c}, P', S') S' ^ S\e S -> Aa5 | a£ A -»■ | 66A | A66 | bb | a5c £ -» bAB \bB\aS\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 eT*. Definice 6.5 (Nedostupný symbol) Symbol X G (N U T) je nedostupný, jestliže se nemůže objevit v žádné větné formě, tj. neexistuje derivace S aX(3, a, (3 G (N U 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 = iVť_i U {A G N | (A -»■ a) G P, a G iV;_J 3. N ý Ni-i => inc(i), přechod na bod 2 4. Ni = iVť_i konec algoritmu, iV' = iV* n N Příklad 6.7 _ Odstranění nadbytečných symbolů: S - -> aA&C | c A - ^ | Cc B - ->■ cB\dD C - ^ cB \aA\b D - ->■ Pd No = T iVi = {5, C} U T 7V2 = {5, C, A} U T N3 = N2 ^ N' = N3DN = {S, A, C} P' = {S ->■ aA&C | c, A ->■ aA | Cc, C | 6} Algoritmus odstranění nedosažitelných symbolů 1. v0 = {5} 2. Vť = VU U {X G (iV U T) | (A G P, A G V^} 3. Ví ý Vi-i inc{i), přechod na bod 2 4. Ví = Vi-i =>- konec algoritmu, N = Ví n ív, T' = VjílT Příklad 6.8 _ P:S^aA\bB\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 - ■> aA \bS - A - * cS aA B - ->■ bB cAB C - ■> aA b P": N0 = T aA I bB I c JVi = {5, C} U T N2 = {S, C, A} U T N3 = N2 jv' = ív3 niv = {5, a, c} Greduk = (N", T", P", S) V0 = {S} V\ = {S, A, a, c} v2 = vx N" = v2 n N' = {S, A} =>• T" = ľ2 n T = {a, c} Důkaz: 1. sestrojíme množiny N£ = {A E N \ A e} (podle postupu pro nadbytečné symboly, iVo = {e}) 2. sestrojíme novou množinu pravidel P': (a) pro každé pravidlo ve tvaru A —► a0B1a1B2 ... Bkak G P, k > 0, Bi G N£ Vi, 1 < i < k, Maj G a{ : aj N£ do P' přidáme všechna pravidla ve tvaru A —► a0X1a1X2 ... Xkak, kde Xi G {Bi, e}, pokud vznikne A —► e, nepřidáme ho, (b) S E Ne ^(S' ^e\S) eP', N' = NU {S'} (c) 5 £ iV£ =>■ N' = N, S' = S 3. G" = {N', T, P1, S') □ 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é straně 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 =E N sestrojíme množinu Na'. (a) NA,0 = {A}, (b) NA,t = NA,t-! u {X g N | (B -+ X) g P, B g NA/í-i] (c) Na,í ý Na,í-i => inc(i), přesun na b), Na,í = Na,í-i =>- konec algoritmu, Na = Na,í 2. sestrojíme P': \/(B —► a) g P, které není jednoduché, V A g N takové, že B e NA> dáme do P' pravidlo A —► a □ Příklad 6.9 _ E ->■ F + T | T T ->■ T*F | F F —► (F) | i A^,o = {F} 7VEil = {F,T} 7VE,2 = {F,T,F} = iVií iVF,o = {F} = iVF A^o = {T} NT:1 = {T, F} = NT E T F 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 13Aa, kde /3 ^* 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 —► Aai | Aa2 \ ... \ Aan \ f3i \ f32 | ... | (3m nahradíme sadou pravidel A - * frA' | fcA' | .. • | l3mA Pi ÄI • ■ | (3 m A1 - ^ aiÄ | a2A' | . ■ ■ \anA a2 . .. \an Proč: původní sada pravidel generuje sekvenci řetězců air rekurze je ukončena tak, že před všechny řetězce on je vygenerován jeden z řetězců (3j, tedy vlastně vygenerujeme totéž, jen jinými pravidly. A =>• Aa% =>• Aaia% =>• Aa^a^a^ =>• f32a7aias □ Kapitola 6 Bezkontextové jazyky 63 Příklad 6.10 _ Odstranění levé rekurze: A - » BC\a B - + BaC | Ab | ba C - * CC b CbA -»■ BC B - + BaC | Ab | ba C - + CC\b\Cb A - * BC\a B - ■» AbB' | baB' \ab\ba B' - ->■ aCE' | aC C - ^ bC 1 6 C - -»■ CC" 1 bC | C | 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 e N, • A a, A e N, a e T, • S —► e, jestliže S není na pravé straně žádného pravidla. Věta 6.6 Ke každé bezkontextové gramatice G existuje gramatika C v CNF taková, že L (G) = L(G'). 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 YXY2 .. .Yn, n > 3, A,Yi G N : A —► Y\Zi, Z\ —► Y2Z2, . . . Zn-3 —► Yn-2Zn-2, Zn-2 —► Yn-{Yn (rozkouskujeme dlouhá pravidla) □ Příklad 6.11 _ Původní gramatika G = {{S, A, B}, {0,1}, P, S) S A | OSA | e A^1A\1\B1 B ->■ 0B | 0 | OSBA Úprava 1: Nezkracující gramatika G' = {{S', S, A, B}, {0,1}, P', S') S A | OSA | 0A A^1A\1\B1 B ->■ 05 | 0 | 0s5a | 05,4 S' ^ S\e Úprava 2: Odstranění jednoduchých pravidel G" = ({S', S, A, B}, {0,1}, P", S') S ->■ 1A | 1 | BI | 0s7l | 04 a ->■ 14 | 1 | BI B ->■ 05 | 0 | 0s5a | 054 5' ->■ 1A 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'" 5, A, B,JV0,Wi}, {0,1}, P'", S" S - *■ N±A 1 | BN± | iVo^A | iV0A A - * N±A 1 | BN± B - + N0B 0 | N0SBA | ÍVqPA S' - ->■ NľA 1 | BNx | ÍYqSA | iY"0A | e N0 ->■ 0 N ->■ 1 Úprava 4: Rozkouskování pravidel G"" = ({S', S, A, B, N0, NX,ZX, Z2, Z3}, {0,1}, P"", S') S ->■ NľA | 1 | BNx | iVo^i | N0A Zx SA A ->■ iVxA | 1 | BN B ->■ iV0P | 0 | iVoZ^ | iVoZg Z2 —> sz3 Z3 ->■ P A 5' ->■ iVxA I 1 I BN± I NQZ1 I iV0A | e TVq^O N -»■ 1 6.3.2 Greibachova normálni forma Definice 6.13 (Greibachova normálni 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 ->■ aPiP2 ... Bn, n > 0, A, Bu B2,... Bn e N, a e 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. □ Příklad 6.12 _ Původní gramatika G=({E,F},{(,),+,i},P,E) E ->■ E + F I F F —► (E) | i Úprava 1: Odstranění levé rekurze G> = ({E,E',F},{(,),+,i},pi,E) E —► F E' | F E1 ->■ +FE' | + F F ^ (E)\i Úprava 2: Odstranění jednoduchých pravidel G" = ({F, F', F}, {(,),+,*}, F", F) E —► F E' | (F) | í F' ->■ +FF' | + F F —► (E) | i Úprava 3: Rekurzivní nahrazování G"' = ({E,E',F},{(,),+,i},P'",E) E ->■ (F)F' | iF'| (F) | i E' ->■ +FF' | + F F —► (F) | i Kapitola 6 Bezkontextové jazyky 67 Úprava 4: Terminály G"" = ({E,E',F,N)}, {(,),+,i},P"",E) E ->■ (EN)E' | iE'\ (EN) \ i E' ->■ +FE' | + F F ->■ (FiV) | í