Šárka Vavrečková Teorie jazyků a automatu Sbírka příkladů pro cvičení Slezská univerzita v Opavě Filozoficko-přírodovědecká fakulta Ústav informatiky Opava, poslední aktualizace 20. května 2009 o Anotace: Tento dokument obsahuje příklady ke cvičením z předmětu Teorie jazyků a automatů I. Studenti zde najdou řešené příklady s podrobně popsaným postupem a neřešené příklady na kterých si mohou sami postupy procvičit. Teorie jazyků a automatů - sbírka příkladů pro cvičení RNDr. Šárka Vavrečková, Ph.D. Dostupné na: http : / / f p f . slu . c z / ~vavlOui/f ormal. html Ustav informatiky Filozoficko-přírodovědecká fakulta Slezská univerzita v Opavě Bezručovo nám. 13, 746 01 Opava Sázeno v systému WT^X Obsah 1 Konečné automaty 1 1.1 Jazyky ........................................ 1 1.2 Nedeterministický konečný automat....................... 5 1.3 Totálni automat................................... 7 1.4 Odstranění nepotřebných stavu.......................... 9 2 Regulární jazyky 12 2.1 Konečné jazyky................................... 12 2.2 Pumping lemma pro regulární jazyky...................... 14 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky............ 18 2.3.1 Sjednocení.................................. 18 2.3.2 Zřetězení................................... 20 2.3.3 Iterace (Kleeneho uzávěr)......................... 22 2.3.4 Pozitivní iterace............................... 23 2.3.5 Zrcadlový obraz (reverze)......................... 25 2.3.6 Průnik.................................... 28 2.3.7 Homomorfismus.............................. 32 3 Regulární výrazy 34 3.1 Úpravy regulárních výrazů............................ 34 3.2 Sestrojení konečného automatu podle regulárního výrazu........... 35 3.3 Vytvoření regulárního výrazu podle konečného automatu .......... 37 3.4 Minimalizace a normování konečného automatu................ 40 3.4.1 Minimální konečný automat ....................... 40 iii iv 3.4.2 Normovaný konečný automat ...................... 45 4 Regulární gramatiky 48 4.1 Konečný automat podle regulární gramatiky.................. 48 4.2 Regulární gramatika podle konečného automatu................ 50 5 Bezkontextové gramatiky 55 5.1 Sestrojení gramatiky a derivační strom...................... 55 5.2 Vlastnosti bezkontextových gramatik ...................... 57 5.2.1 Redukce gramatiky............................. 57 5.2.2 Převod na nezkracující bezkontextovou gramatiku .......... 59 5.2.3 Odstranění jednoduchých pravidel.................... 63 5.2.4 Gramatika bez cyklu a vlastní gramatika................ 65 5.2.5 Levá a pravá rekurze............................ 66 5.3 Normální formy bezkontextových gramatik................... 71 5.3.1 Chomského normální forma ....................... 72 5.3.2 Greibachova normální forma....................... 74 0} je totéž jako a*ba*. Příklad 1.1 - Napíšeme všechna slova následujících jazyků kratší než 5. Postup: nejdřív místo všech „proměnných" indexů * a + dosadíme nejnižší možnou hodnotu, tj. například ve výrazu a*b* vytvoříme slovo a°b° = e, pak postupně dosazujeme vyšší hodnoty v různých možných kombinacích. • {ab*, ba} = {a, ab, ba, abb, abbb,...} • 2 • {0,1}* = { 2,20, 21, 200, 201, 210, 211, 2000, 2001, 2010, 2011, 2100, 2101, 2110, 2111,...} • {(ŕbW | i, j > 1} U {(ab)1 | i > 0} = {abb, aabb, abbb,...} U {e, ab, abab,...} = = {abb, aabb, abbb, e, ab, abab,...} Zde si všimněme odlišných spodních mezí pro proměnné i, j v obou sjednocovaných jazycích - pokud i > 1, pak a1 znamená a+ neboli aa*. Úkol 1.1 - Napište všechna slova následujících jazyků kratší než 5. • (abc)* = • (a*b)* = • (ab)*c = . (a*b)*c = • {(abýbi | i > 0, j > 1} = • 0*(10)*1 = 1.1 Jazyky 3 Konečný automat lze zapsat celkem třemi způsoby: 1. použitím plné specifikace s á-funkcí 2. stavovým diagramem 3. tabulkou přechodů Ukážeme si všechny tři způsoby. Příklad 1.2 - Vytvoříme konečný automat pro jazyk a ■ (a ■ {a, b} ■ a)* ■ b ■ b* ve všech třech reprezentacích. U menších automatů je nejjednodušší vytvořit stavový diagram: 5-funkce včetně plné specifikace: -4 = ({90 , 91,92,93}, {a,b}, 5, q0, {g3}) ô(q0,a) = qi ô(q2,a) = qo ô(qi,a)=q2 ó(q2,b) = q0 S(qi,b)=q3 S(q3,b)=q3 Zatímco u stavového diagramu a tabulky přechodů nemusíme uvádět plnou specifikaci - řetězec A = ({qo, qi, q2, 93}, {a,b}, 5, qo, {93}), při použití č-funkce je plná specifikace nutná. Bez ní bychom nepoznali, který stav je počáteční a které stavy jsou koncové. Tabulka přechodu: a b qo qi qi 92 93 92 90 90 93 93 Úkol 1.2 - 1. Pro následujích šest jazyků sestrojte konečný automat ve všech třech reprezentacích: (a) a*b (d) (abfba (b) {0,1}*11 (e) {ab* \ i > 1} U {ba* \ i > 0} (c) 11{0,1}* (f) a*-{a,bc} 2. Podle zadání vytvořte zbylé dvě reprezentace daného konečného automatu. (a) Podle á-funkce vytvořte stavový diagram a tabulku přechodů: -4i = ({9o,9i,92}, {a,b,c}, 5, q0, {91,92}) 5(90, a) = qi S(q1,c)=q1 5(90,6) =92 %2,c)=gi 4 Kapitola 1 Konečné automaty (b) Podle každé tabulky přechodů vytvořte stavový diagram a á-funkci s plnou reprezentací automatu: 0 1 a 6 -> A B C <-> q0 9i 90 B B C 9i 92 -C D <- 92 93 D Všimněte si, že podle druhé tabulky je počáteční stav zároveň koncový (šipka vede oběma směry). (c) Podle každého stavového diagramu vytvořte tabulku přechodů a á-funkci s plnou reprezentací automatu: Příklad 1.3 - Sestrojíme konečný automat rozpoznávající celá čísla. Používáme číslice 0 ... 9, číslo se musí skládat z alespoň jedné číslice. Víceciferná čísla nesmí začínat nulou. Vytvoříme automat se třemi stavy. Oddělíme zpracování jednociferného čísla „0" od ostatních, která nulou nesmí začínat. Úkol 1.3 - 1. Sestrojte konečný automat (stavový diagram) rozpoznávající reálná čísla. Celá část je podle zadání v předchozím příkladu, následuje desetinná čárka a pak opět sekvence číslic (alespoň jedna, může to být i číslice 0). 2. Podle stavového diagramu pro reálná čísla vytvořte tabulku přechodů. 1.2 Nedeterministický konečný automat 5 1.2 Nedeterministický konečný automat Nedeterministický konečný automat je takový automat, kde v alespoň jednom stavu lze na některý signál reagovat více různými způsoby. Protože se tento typ automatu špatně programuje (je těžké vložit do instrukcí náhodnost - zvolit jednu z nabízených cest, a to pokud možno tak, aby vedla „správným směrem", do koncového stavu), může se hodit postup, jak nedeterministický automat převést na deterministický se zachováním rozpoznávaného jazyka. Příklad 1.4 - Zadaný nedeterministický automat převedeme na deterministický (je dán stavový diagram a tabulka přechodů). <12 Tento převod je nejjednodušší na tabulce přechodů. V některých buňkách je více než jedna položka, proto obsah buněk budeme chápat jako množiny. Vytváříme tedy nový konečný (deterministický) automat takový, že jeho stavy jsou množinami stavů původního automatu. Novou tabulku přechodů tedy vytvoříme z původní tabulky tak, že nejdřív jak obsah buněk, tak i stavy v označení řádků uzavřeme do množinových závorek. Tím ale v některých buňkách (zde v jedné) dostaneme stav, který není v označení žádného řádku. To napravíme jednoduše tak, že přidáme nový řádek tabulky s tímto označením a obsah buněk zjistíme sjednocením řádků původní tabulky označených prvky množiny, se kterou právě pracujeme: {A} {B,C} {D,E} {G} {C} {F} {H,I} {A} ÍC} Může se stát, že sjednocením množin v buňkách opět vznikne množina, která se nenachází v označení žádného řádku. Pak opět vytvoříme nový řádek a pro buňky použijeme operaci sjednocení množin. Postup je tedy rekurzivní. 6 Kapitola 1 Konečné automaty Takže k příkladu: 0 1 0 1 ^ {qo} {qi} ^ {qo} {91} 0 {qi} {90,92} {qo} {91} {90,92} {90} - fe} 0 0 <- {90,^2} {9i}U0 = {gi} 0U0 = 0 Vlastnost „být koncovým stavem" se také dědí v rámci sjednocení - pokud alespoň jeden z prvků množiny stavů je v původním automatu koncovým stavem, stává se koncovým stavem i celá tato množina. Uvedený postup je vlastně zkrácený. Ve skutečnosti bychom měli postupovat tak, že bychom jako stavy použili všechny možné kombinace stavů a opět operaci sjednocení množin: Ve stavovém diagramu můžeme vidět, že stavy, které jsou oproti předchozímu postupu navíc, jsou nedosažitelné z počátečního stavu a tedy se nenacházejí na žádné cestě při zpracování slov jazyka. Proto je vlastně můžeme bez újmy na obecnosti z automatu odstranit. Úkol 1.4 - Uvedené nedeterministické konečné automaty reprezentované tabulkami převeďte na ekvivalentní deterministické. Ke každému vytvořte stavový diagram původního nedeterministického automatu i vytvořeného deterministického a porovnejte. a b 0 1 a b c X Y 9o 9o,9i 9o,9i 9o 91,92 91 Y Z <- 9i 91,92 91 92 91,92 Z X X,Z q2 <- 92 90 92 1.3 Totální automat 7 1.3 Totální automat V totálním (úplném) automatu lze v každém stavu reagovat na jakýkoliv symbol. Při převodu (netotálního) automatu na totální vytvoříme nový stav („odpadkový koš", chybový stav), do kterého přesměrujeme všechny chybějící přechody. Nesmíme zapomenout, že požadavek možnosti reakce na kterýkoliv symbol se vztahuje také na tento nově přidaný stav. Postup převodu na totální automat lze použít pouze na deterministický konečný automat, proto u nedeterministického automatu je prvním krokem vždy převod na deterministický. Příklad 1.5 - K zadanému deterministickému konečnému automatu vytvoříme ekvivalentní totální automat: Tento automat určitě není totální - například ve stavu qo nelze reagovat hned na dva signály. Vytvoříme nový stav, označíme jej symbolem 0 a přesměrujeme do tohoto stavu všechny chybějící přechody: a b c ^ 90 qi 0 0 qi 92 91 0 <- 92 0 0 92 0 0 0 0 a, b, Příklad 1.6 - V příkladu 1.4 jsme k nedeterministickému automatu vytvořili ekvivalentní deterministický. Tento deterministický automat nyní zúplníme (převedeme na totální). Stav {f^} není dosažitelný z počátečního stavu, proto jej také vypustíme. Abychom trochu zjednodušili značení, budeme místo množin {...} používat velká písmena, provedeme přeznačení: 8 Kapitola 1 Konečné automaty Původní: Přeznačený: 0 i ^ tio} til} 0 til} tio, Q2} tio} <- {qo,q2} tii} 0 0 1 0 B c <- C 0 Stavové diagramy přeznačeného a zúplněného automatu: Totálni: 0 1 0 B C A <- C 0 0 0 0 (b) 1 ^ K. 0 Ukol 1.5 1. Všechny konečné automaty, které jste v úkolu č. 1.4 na straně 6 převedli na deterministické, zúplňte (převeďte na totálni). 2. Následující konečný automat převeďte na totální a nakreslete jeho stavový diagram (signál v záhlaví posledního sloupce je desetinná čárka): 0 1,...,9 / -> A C B B B D -C D D E E <— E E E 0,..., 9 >-^-(d)íž—Mé) 3. Následující (nedeterministický!) konečný automat zúplňte. 0 1 -> A B B B, C A -C A, C 1.4 Odstranění nepotřebných stavů 9 1.4 Odstranění nepotřebných stavů Nepotřebné stavy jsou stavy které nejsou použity při žádném úspěšném výpočtu (tj. končícím v koncovém stavu). Jedná se o stavy • nedosažitelné - neexistuje k nim cesta z počátečního stavu, • nadbytečné - neexistuje cesta z tohoto stavu do jakéhokoliv koncového stavu. S odstraňováním (lépe řečeno ignorováním, neuvedením či vypuštěním) prvního typu nepotřebných stavů - nedosažitelných - jsme se setkali už u zkráceného postupu pro převod nedeterministického automatu na deterministický. Pokud nové řádky tabulky přechodů tvoříme jen pro takové množiny původních stavů, které se již vyskytly v některé buňce, většinu nedosažitelných stavů (ale ne vždy všechny) automaticky odstraňujeme. Když chceme odstranit nepotřebné stavy, vždy začínáme nedosažitelnými stavy a až potom odstraníme nadbytečné. V obou případech postupujeme rekurzívně, a to buď podle stavového diagramu nebo podle tabulky přechodů. • nedosažitelné stavy: jako bázi (základní množinu) zvolíme 5*0 = {qo} (obsahuje pouze počáteční stav), další prvky přidáváme „ve směru šipek" v stavovém diagramu, resp. v tabulce přechodů ve směru označení řádku —> obsah buněk na řádku, postupně vytváříme množinu všech stavů, do kterých vede cesta z počátečního stavu o délce max. 0,1,..., n kroků (toto číslo je dolní index u označení vytvářené množiny Si); • nadbytečné stavy: jako bázi naopak zvolíme množinu koncových stavů -Eq = F, další prvky přidáváme „proti směru šipek" v stavovém diagramu, resp. ve směru obsah některé buňky tabulky přechodů —> označení řádku, vytváříme množinu všech stavů, ze kterých vede cesta do některého koncového stavu o délce max. 0,1,..., n kroků. Příklad 1.7 - V zadaném konečném automatu odstraníme nedosažitelné a nadbytečné stavy. Odstraníme nedosažitelné stavy (do kterých neexistuje cesta z počátečního stavu): 5*0 = {qo} Si = {qo} U {qi, q3} = {q0, qi, q3} (ze stavu q0 vede přechod do q1 a q3) 10 Kapitola 1 Konečné automaty 5*2 = {90, 91,93} U {95,92} = {90,91,93,95,92} S3 = {90, 9i, 93, 95, 92} = S2 (konec, v posledním kroku žádný stav do množiny nepřibyl) V množině S3 není stav 94, je tedy nedosažitelný z počátečního stavu a můžeme ho z automatu odstranit. V každé z množin 5j, které jsme postupně vytvořili, najdeme všechny stavy, které jsou z počátečního stavu dosažitelné po nejvýše i krocích. Dále zjistíme, ze kterých stavů nevede cesta do koncových stavů. Budeme pracovat již s automatem po odstranění stavu 94. E0 = F = {91,95} E\ = {91, 95} U {go} = {91, 95, 9o} (do stavů z Eq vede přechod pouze ze stavu qo) E2 = {91,95,90 , 92} E3 = {91,95,90 , 92} = E2 V množině E3 není stav 93, to znamená, že z tohoto stavu neexistuje žádná cesta do koncového a tedy když tento stav odstraníme, neovlivníme výpočet žádného slova, které automat rozpoznává. Odstraníme tento stav a také všechny přechody s ním přímo související. Po odstranění stavů, které jsme vyřadili s použitím množin Si a Ei, dostáváme následující konečný automat: Ukol 1.6 - 1. Podle zadání následujícího automatu vytvořte tabulku přechodů a stavový diagram. Potom odstraňte nepotřebné stavy. Takto upravený automat pak zúplňte (převeďte na totální automat). A = ({A, B, C, D, E, F}, {0,1,2}, 5, A, {A, C}) s funkcí 5: ó(A,0)=E 5{BA) = D Ó(D,2) = C ô(F, 1) = E ô(AA)=B Ó(B,2) = E 5{EA) = E Ó(F,2) = F 5(A,2)=E ó(C,0) = C Ó(E,2) = E 5(B, 0) = C 6{CA) = C 6{F,0) = C 2. K následujícímu konečnému automatu vytvořte zbývající dvě reprezentace - á-funkci a tabulku přechodů. Potom odstraňte všechny nepotřebné stavy. 1.4 Odstranění nepotřebných stavů 11 3. Podle následujících konečných automatů určených tabulkami přechodů sestrojte stavové diagramy a pak odstraňte všechny nepotřebné stavy. a b c A A A B B C C C B D A E B <— E B C C a b c 90 94 9i <- 9i 94 90 <- 92 93 9i 92 93 94 93 94 93 4. Zamyslete se nad těmito případy: jak by vypadal jazyk upraveného automatu (bez nepotřebných stavů), kdyby do množin Si nebyly zařazeny žádné koncové stavy? Jak by vypadal tento jazyk, kdyby do množin Ei nebyl zařazen počáteční stav? 0 (v prostřední části musí být alespoň jeden znak - signál), • x-(y)k -z G L pro jakékoliv k > 0 (když prostřední část „pumpujeme", výsledné slovo opět patří do jazyka - y buď vyřadíme pro k = 0 a nebo opakujeme 1 x, 2 x, 3 x, atd.) Pumpovací věta je implikace. Říká nám, že když je jazyk regulární, tak má danou vlastnost. Není nikde řečeno, že jazyk, který není regulární, danou vlastnost nemá. Příklad 2.2 - Nejdřív si ukážeme, jak ověřit, že regulární jazyk tuto vlastnost má. Postup si ukážeme na jazyku L = {a1 b* \ i,j > 0} Pro tento jazyk dokážeme sestrojit konečný automat, tedy víme, že se jedná o regulární jazyk. Vlastnost popsanou v Pumping lemma si můžeme představit takto: • použijeme p rovno počtu stavů konečného automatu, tedy p = 2 • vezmeme jakékoliv slovo jazyka delší než 2, například w = a3 b (má délku 4) • w je delší než počet stavů automatu, je tedy zřejmé, že některá část slova bude vyhodnocována v cyklu • při pohledu na stavový diagram automatu vidíme, že tento cyklus jde přes jediný stav, a to qo • vhodné rozdělení může být například w = (a) • (a2) ■ (6), po pumpování dostáváme slova (a) • (a2)k ■ (b) = a1+2kb, pro jakékoliv k > 0 tato slova patří do jazyka L. Platí pumping lemma pro všechny regulární jazyky včetně konečných? Samozřejmě ano. Pro každý konečný jazyk existuje konečný automat, který ho rozpoznává. Jako p si zvolíme opět buď počet stavů tohoto automatu a nebo číslo ještě větší. V Pumping lemma se píše „pro každé slovo w daného jazyka delší než p ...", ale nepíše se tam, že takové slovo opravdu musí existovat. Opravdu žádné takové neexistuje, protože kdyby existovalo slovo delší než počet stavů automatu, musel by být v grafu stavového diagramu cyklus, a cyklus znamená nekonečný jazyk. Takže Pumping lemma platí i pro konečné jazyky. 2.2 Pumping lemma pro regulární jazyky 15 Úkol 2.2 - U následujících regulárních jazyků vytvořte stavový diagram, vyberte „dostatečně dlouhé slovo" - delší než počet stavů automatu, určete některé vhodné rozdělení slova na tři části podle podmínek Pumping lemma a ukažte, že pro jakékoliv číslo (mocninu) k jde opět o slovo z daného jazyka. Pracujte s těmito jazyky: (a) La = {aÚa \ i > 0} (b) Lb = {(abý | i > 0} (c) Lc = {a{bbý | i > 1} (d) Ld = {000(111)* | i > 0} (e) Lc = {disk, data, plat} (f) Ld = M (množina přirozených čísel, zde včetně 0) Obvyklejším způsobem použití Pumping lemma je její obrážená forma: místo tvrzení Regular(L) =>• Vlastnost(L,p) dokazujeme -iVlastnost(L,p) -iRegular(L). tedy „Pokud neexistuje žádné p takové, že pro každé slovo delší než p dokážeme najít dané rozdělení, pak jazyk není regulární.". Abychom mohli dokázat, že pracujeme s opravdu jakkoliv dlouhým slovem, použijeme v určení slova „proměnnou" v exponentu, kterou v případě potřeby můžeme jakkoliv zvyšovat (do nekonečna), například proměnnou i ve slově (aby. Dále u zvoleného slova zkoušíme různé možnosti jeho rozdělení na tři části tak, aby prostřední část nebyla prázdné slovo. Nemusíme hledat absolutně všechny možnosti (to bychom hledali do nekonečna), ale je třeba vystihnout různé možné způsoby umístění hranic mezi potenciálními částmi. Pro každé možné rozdělení pak najdeme alespoň jednu hodnotu k, pro kterou x • yk • z nepatří do jazyka. Končíme tehdy, když se podaří najít slovo takové, že pro jakékoliv jeho rozdělení vždy najdeme alespoň jednu hodnotu k takovou, že x ■ yk ■ z nepatří do daného jazyka. Příklad 2.3 - Ukážeme, že jazyk L = {anb2n | n > 0} není regulární. Vybereme „dostatečně dlouhé" slovo jazyka. Protože nemáme zkonstruován konečný automat pro tento jazyk (samozřejmě, vždyť ve skutečnosti neexistuje), musíme vybrat takové slovo, o kterém si můžeme být jisti, že je opravdu dlouhé. Například w = áLb2'L pro 16 Kapitola 2 Regulární jazyky „nějaké" i, dostatečně velké. Použili jsme proměnnou i, o které víme jen jedinou konkrétní věc - je větší než 0 (protože musí být větší než nějaké číslo p, které je větší než 0). Slovo máme, a to dostatečně reprezentativní, vlastně nám určuje všechna dlouhá slova daného jazyka. Zbývá projít všechna možná rozdělení x • y • z tohoto slova a dokázat, že pro jakékoliv k > 0 slovo x ■ yk ■ z nepatří do jazyka L. U jednotlivých možností budeme volit k = 0 nebo k = 2. Jsou tyto možnosti: 1. hranice mezi x a y je před začátkem slova (tj. x = e): (a) hranice mezi y a z je někde mezi znaky a, v první části slova: x ■ y ■ z = e • am ■ al^mb2\ m > 0, x ■ yk ■ z = afcm+í-m52í/ například pro k = 0 vychází ál^rnb2t; protože m > 0, toto slovo nepatří do jazyka L (b) hranice mezi y a z je na hranici mezi znaky a a 6: x ■ y ■ z = e-a%-b2% ,x-yk-z = aktb2t; opět stačí dosadit k = 0, dostáváme 62í, protože i je velké číslo, určitě větší než 0, toto slovo není z jazyka L (c) hranice mezi y a z je někde mezi znaky 6, v druhé části slova: x ■ y ■ z = e • albm ■ č>2í~m, 0 < m < 2i, x ■ yk ■ z = (albm)kb2l~m, pro k = 0 je taktéž narušen vztah v exponentech - slovo b2l~m ^ L (d) hranice mezi y a z je na konci slova, tj. celé slovo je v prostřední části rozdělení: x • y • z = e • a%b2% • e, x ■ y2 ■ z = a%b2%a%b2%, i > 0 ^ L 2. hranice mezi x a y je v první části slova, někde mezi znaky a: (a) hranice mezi y a z je ve stejné části slova: x • y • z = am • an • ál~m~nb2'\ m,n > 0, x ■ y° ■ z = <ř-nb2i i L (b) hranice mezi y a z je na hranici znaků a a b: x ■ y ■ y = am ■ a*~m • b2\ 0 < m < i, x -y° ■ z = amb2% £ L (c) hranice mezi y a z je někde mezi znaky b: x ■ y ■ z = am • áL~mbn • b2l~r\ m,n > 0, m < i, x ■ y2 ■ z = a%bna%~mb2% £ L (d) hranice mezi y a z je na konci slova: x • y • z = am • a%~mb2% • e, 0 < m < i, x -y° ■ z = am L 3. hranice mezi x a y je na hranici mezi znaky a a b: (a) hranice mezi y a z je někde mezi znaky b: x • y • z = áL • bm • b2l~m, 0 < m < 2i, x-y° -z = tfb2*-"1 i L (b) hranice mezi y a z je na konci slova: x ■ y ■ z = a1 ■ b2t ■ e, x ■ y° ■ z = a1 L A. hranice mezi x a y je v druhé části slova, někde mezi znaky b: (a) hranice mezi y a z je někde mezi znaky b: x-y-z = áLbm-bn •b2l~m~n, 0 < m,n < 2i, x • y° ■ z = aib2i-n i L 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 17 (b) hranice mezi y a z je na konci slova: x • y • z = áLbm - b21 m • e, 0 < m < 2i, x-y0 ■ z = cŕb™ <£ L Jednotlivé varianty rozdělení jsou přehlednější v tabulce: x ■ y ■ z Podmínky x • yk • z k = 0 k = 2 e ■ am ■ ai_m62i 0 < m < i gkm+i—mb2i aí-mb2í £ L e ■ áL ■ b2% akíb2í b2i <£ L £-albm ■ b2i-m 0 0 aí-nb2í £ L am . ai-m . b2i 0 < m < i (jín+fc(í—m) b2i amb2i <£ L am . aí-mbn . fe2í-n m, n > 0, m < i ám{ai-mbn)kb2i-n aíbnaí-mb2í £ L am . aí-mb2í . £ 0 < m < i am{ai-mb2i)k am <£ L ai.bm. b2i-m 0 0} není regulární, přesto splňuje Pumping lemma. Můžeme zvolit například slovo am. Toto slovo patří do jazyka L a existuje dokonce více různých rozdělení x • y • z takových, že x • yk • z G L, například e • (am)k ■ e = akm G L pro jakékoliv k > 0. Co z toho plyne? Když jazyk splňuje Pumping lemma, nemůžeme tvrdit, že je regulární. A naopak - když se nepodaří pomocí Pumping lemma dokázat, že jazyk není regulární, tak to ještě neznamená, že je regulární. Úkol 2.3 - 1. Ukažte, že jazyk L = {ba(ab)n \ n > 0} splňuje Pumping lemma. 2. Pomocí Pumping lemma dokažte, že jazyk L = {anbcn | n > 1} není regulární. 18 Kapitola 2 Regulární jazyky 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky Třída jazyků je množina všech jazyků s danou společnou vlastností. Také regulární jazyky tvoří třídu - třída regulárních jazyků je množina všech jazyků, pro které lze sestrojit konečný automat. Víme, že na řetězce lze použít operaci zřetězení. Jazyk je množina řetězců, a tedy na jazyk můžeme použít různé množinové operace (sjednocení, průnik, doplněk - zrcadlení, substituci), a také operace odvozené z práce s řetězci a znaky (signály) - zřetězení, dále iteraci (operace „hvězdička") a další. Třída jazyků je uzavřena vzhledem k nějaké operaci, pokud po uplatnění operace na jazyky z této třídy opět vznikne jazyk patřící do stejné třídy. Postupně si ukážeme všechny základní operace, a to na konečných automatech. Pokud jde o binární operaci (uplatňuje se na dva jazyky), je nutnou podmínkou disjunktnost průniku množin stavů těchto automatů (žádný stav nesmí existovat v obou automatech zároveň). 2.3.1 Sjednocení V případě sjednocení využijeme celou definici původních automatů. Přidáme nový stav a z tohoto stavu povedeme přechody do všech stavů, do kterých vede přechod z počátečního stavu. Nový stav nám tedy simuluje použití počátečních stavů v původních automatech. Postup si můžeme představit třeba tak, že vezmeme všechny přechody, které vedou z původních počátečních stavů, a zkopírujeme (ne přeneseme, ty původní musejí zůstat) „konce bez šipek" k novému stavu. Pokud některý z původních počátečních stavů patří i do množiny koncových stavů, pak také tuto vlastnost přidáme novému počátečnímu stavu. Příklad 2.5 - Ukážeme si operaci sjednocení na následujících jazycích a automatech: Li = {(baý(aUbb) : i > 0} L2 = {ďbaa1 j i, j > 0} Konečné automaty pro tyto jazyky jsou následující: 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 19 Přidáme nový stav so a všechny přechody z tohoto stavu nasměrujeme a označíme stejně jako přechody z počátečních stavu původních automatů. Postup je nejnázornější na stavovém diagramu, ale je jednoduchý také v tabulce přechodů - stačí obě tabulky shrnout do jedné a přidat nový řádek, jehož buňky budou sjednocením buněk na řádcích původních počátečních stavů a na příslušných sloupcích. Protože jeden z původních počátečních stavů (qo) patří do množiny koncových stavů, také nový počáteční stav sq bude zároveň koncovým. Úkol 2.4 - 1. Použijte operaci sjednocení na následující konečné automaty: 2. Použijte operaci sjednocení na následující konečné automaty (u druhého z nich je stav q3 zároveň koncový): a b a b c 90,92 91 ^ 93 94 96 <- qi 92 94 95 <- 92 92 95 93 <- 96 3. Pro oba konečné automaty ze zadání předchozího příkladu a také pro výsledný automat vytvořte zbylé dva typy reprezentací - stavový diagram a á-funkci včetně plné specifikace automatu. 4. Zamyslete se nad tím, jak by vypadalo sjednocení více než dvou konečných automatů. 20 Kapitola 2 Regulární jazyky 2.3.2 Zřetězení Zřetězení dvou jazyků vytvoříme tak, že ve výsledném jazyce jsou všechny možné řetězce, jejichž první část je kterékoliv slovo z prvního jazyka a druhá část zase kterékoliv slovo z druhého jazyka. Záleží na pořadí, části slova nemůžeme přehodit, řídí se pořadím zřetězovaných jazyků. Příklad 2.6 - Princip zřetězení jazyků si ukážeme na těchto konečných jazycích: L\ = {e, abc, ba} Li = {ddb, dc} Zřetězením těchto dvou jazyků získáme jazyk L = L\ • L2: L = {e ■ ddb, e ■ dc, abc ■ ddb, abc ■ dc, ba ■ ddb, ba ■ dc} = {ddb, dc, abcccb, abcdc, baddb, badc} Při zřetězení není třeba ve výsledném automatu vytvářet nový stav. Opět využijeme všechny stavy a přechody z původních automatů a budeme přidávat nové přechody, které je propojí. Při ukončení výpočtu první části slova (tj. v prvním původním automatu) je třeba „plynule" navázat na výpočet druhého původního automatu. Proto nově přidávané přechody budou vést z koncových stavů prvního automatu, jejich cílový stav (stav, do kterého bude směřovat šipka přechodu) a označení přejmeme (zkopírujeme) od přechodů z počátečního stavu druhého původního automatu. Počátečním stavem výsledného automatu bude samozřejmě počáteční stav prvního původního automatu. Do množiny koncových stavů zařadíme • koncové stavy druhého původního automatu, • pokud počáteční stav druhého automatu byl zároveň koncovým (to znamená, že do druhého jazyka patřilo slovo e), pak do množiny koncových stavů výsledného automatu zařadíme také koncové stavy prvního původního automatu. Příklad 2.7 - Zřetězíme jazyky těchto konečných automatů: 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 21 V automatu Ai (prvním) jsou dva koncové stavy. Z nich budou vést nové přechody ke stavům automatu A2 - ke všem stavům, do kterých vede přechod z počátečního stavu A. a b 90 qi, A 92, B qi A B 92 qo qi A ( A B ) B c -C c Nyní obrátíme pořadí zřetězovaných automatů. Musíme brát v úvahu to, že počáteční stav automatu, který je teď druhý v pořadí, je zároveň koncovým stavem: a b -> A A B B C -C C, 9i 92 qo ( 91 92 ) qi 92 9o 9i Ukol 2.5 1. Proveďte operaci zřetězení jazyků následujících konečných automatů: ■> A i M c 2. Proveďte operaci zřetězení jazyků následujících konečných automatů - nejdřív v pořadí podle zadání (L(Ai) -L(A2)) a potom v opačném pořadí (L(Ä2) -L(Ai)). Sestrojte také stavové diagramy. a 6 A2 a 6 c 90 90,92 91 ^ 93 94 96 <- 9i 92 94 95 <- 92 92 95 93 <- 96 22 Kapitola 2 Regulární jazyky 2.3.3 Iterace (Kleeneho uzávěr) Při iteraci zřetězujeme jazyk sám se sebou, ato0x,lx,2x,...,a pak všechny výsledné jazyky po zřetězení sjednotíme. Příklad 2.8 - Princip iterace jazyka si ukážeme na tomto konečném jazyce: L\ = {abc, ba, cd} Iterací získáme jazyk L = L*: L = {e, ................................................................. Ox abc, ba, cd, ......................................................... lx abcabc, abcba, abccd, baabc, baba, bacd, .............................. 2 x abcabcabc, abcabcba, abcabccd, abcbaabc, abcbaba, abcbacd,...} ....... 3x, ... Výsledkem iterace je vždy nekonečný jazyk obsahující prázdné slovo e, i kdyby původní jazyk L\ byl konečný. Úprava konečného automatu při iteraci spočívá v těchto dvou krocích: • vytvoříme nové přechody umožňující „návrat" z koncových stavů na počátek výpočtu (další slovo z jazyka), • počáteční stav zařadíme do množiny koncových stavů (pokud tam nebyl). Nové přechody tedy povedou z původních koncových stavů, a to do všech stavů, do kterých vede přechod z počátečního stavu. Princip je prakticky stejný jako u dříve probíraných operací, kopírujeme počátky přechodů od počátečního stavu se zachováním jejich cíle i označení (signálu). Příklad 2.9 - Vytvoříme iteraci jazyka následujícího automatu: Koncové stavy jsou dva. Z každého přidáme přechody do všech stavů, do kterých směřují přechody z počátečního stavu, a potom počáteční stav označíme jako koncový (aby automat přijímal také prázdné slovo e). 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 23 0 1 2 A (A B c ) A D, B B, C C D A B C Kdyby stav A už v původním automatu patřil do množiny koncových stavů, tak by samozřejmě koncovým stavem zůstal. Ukol 2.6 - 1. Zkonstruujte konečný automat jazyka, který je iterací jazyka následujícího automatu: a b ^ qo qi q2 <- qi q2 qo qi 2. Zkonstruujte konečný automat jazyka, který je iterací jazyka následujícího automatu: - D ■Mi e 0 1 D E <— E E Pro výsledný automat také vytvořte třetí typ reprezentace - á-funkci s plnou specifikací. 2.3.4 Pozitivní iterace Pozitivní iterace je podobná operace jako předchozí, ale zatímco iterace znamená řetězení Ox, lx, 2 x, při pozitivní iteraci začínáme při řetězení až 1 x, 2 x, .... Matematicky můžeme zapsat: Iterace: L* = \Ji>0 U Pozitivní iterace: L+ = Ui>i ^ 24 Kapitola 2 Regulární jazyky Postup je stejný jako u iterace, ale pokud počáteční stav původního automatu nepatřil do množiny koncových stavů (tj. slovo e nepatřilo do jazyka), nebude koncovým stavem ani po úpravě automatu. Postup si ukážeme na stejném jazyce a automatu jako u iterace. Příklad 2.10 - Vytvoříme pozitivní iteraci jazyka následujícího automatu: Přidáváme pouze nové přechody, počáteční stav nebudeme zařazovat do množiny koncových stavů: Úkol 2.7 - 1. Zkonstruujte konečný automat jazyka, který je pozitivní iterací jazyka následujícího automatu: 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 25 2. Zkonstruujte konečný automat jazyka, který je pozitivní iterací jazyka následujícího automatu: 2.3.5 Zrcadlový obraz (reverze) Reverze je převrácení. Zrcadlový obraz slova sestrojíme tak, že je zrcadlově „převrátíme", tj. ze slova abcd získáme slovo (abcd)R = dcba. Zrcadlový obraz jazyka je jazyk obsahující všechna slova původního jazyka, ale převrácená. Operace zrcadlení je sama k sobě inverzní - když slovo (nebo jazyk) revertujeme dvakrát, dostáváme původní slovo (jazyk). Zrcadlení můžeme zapsat takto: LR = {w | wR £ L} Pokud budeme při reverzi pracovat s konečným automatem, především převrátíme všechny cesty, které v automatu existují (tj. převrátíme všechny přechody) a zaměníme počáteční a koncové stavy. Dále musíme vyřešit jeden problém - počáteční stav musí být vždy jen jeden, ale koncových stavů může být obecně jakýkoliv počet. Proto rozlišíme dva případy - pokud původní automat má jen jediný koncový stav, stačí postup naznačený v předchozím odstavci. Jestliže však má více koncových stavů, musíme zajistit, aby po reverzi existoval jen jediný počáteční stav. Proto vytvoříme nový stav, který v sobě bude shrnovat vlastnosti původních koncových stavů (resp. nových „počátečních" stavů) týkající se přechodů, které z nich po reverzi vycházejí. Pokud počáteční stav původního automatu patřil do množiny koncových stavů, bude koncovým stavem také počáteční stav po reverzi. Příklad 2.11 - Provedeme operaci zrcadlení jazyka tohoto konečného automatu: 26 Kapitola 2 Regulární jazyky Obrátíme všechny přechody. Protože máme jen jediný koncový stav, stačí dále jen zaměnit počáteční a koncový stav. U tabulky se zaměňují označení řádků s obsahem buněk na tomto řádku. a b c <- 90 qi 90 91,92 92 90,93 93 92 Příklad 2.12 - Podíváme se na složitější případ - konečný automat s více koncovými stavy. Postup bude podobný, ale navíc řešíme nutnost existence jediného počátečního stavu. Je dán tento konečný automat: Jsou zde dva koncové stavy. Nejdřív přesměrujeme všechny přechody a označíme nový koncový stav, a až v druhém kroku (automat vpravo) vytvoříme nový počáteční stav podobným postupem, jaký jsme použili například u sjednocení (tam šlo také o „simulaci" - nahrazení dvou počátečních stavů jediným). Poslední případ, na který se podíváme, je konečný automat s více koncovými stavy, kde také počáteční stav patří do množiny koncových stavů. 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 27 Příklad 2.13 - Pro operaci zrcadlení je dán tento konečný automat: Narozdíl od předchozích příkladů budou ve výsledném automatu dva koncové stavy. Stav qo bude koncový protože v původním automatu je počátečním stavem, a stav p bude koncový, protože do jazyka původního automatu patří slovo e, jehož převrácením je opět slovo e pro jeho rozpoznání musí být počáteční stav (tj. p) v množině koncových stavů. Úkol 2.8 - 1. Zkonstruujte konečný automat jazyka, který je reverzí (zrcadlovým obrazem) jazyka následujícího automatu: 2. Vytvořte konečný automat jazyka, který je reverzí jazyka následujícího automatu. Pro oba automaty (uvedený i ten, který vytvoříte) sestrojte tabulku přechodů. 3. Vytvořte konečný automat rozpoznávající jazyk L = {e, tisk, tis, síto} tak, aby jednotlivá slova jazyka byla rozpoznávaná koncovým stavem (tj. pro každé slovo vlastní koncový stav). Potom proveďte reverzi tohoto automatu. 28 Kapitola 2 Regulární jazyky 4. Vytvořte zrcadlový obraz jazyka tohoto konečného automatu (má jediný koncový stav, který je zároveň počátečním stavem): a b ^ 9o qi 92 qi 92 92 92 90 2.3.6 Průnik Když vytváříme konečný automat pro průnik dvou jazyků pomocí automatů, které je rozpoznávají, tak vlastně simulujeme (paralelně) činnost obou těchto automatů. Po přečtení každého signálu ze vstupu provedeme jeden krok v obou automatech zároveň. Ve výsledném automatu jsou proto stavy uspořádanými dvojicemi stavů z prvního a druhého původního automatu. Příklad 2.14 - Sestrojíme konečný automat rozpoznávající průnik jazyků následujících dvou automatů: Nejdřív si vyznačíme průběh „simulace". Není to nutné (a u složitějšího automatu je to prakticky neproveditelné), ale na diagramu lépe pochopíme paralelnost obou zpracování téhož slova (červeně jsou spojeny stavy, ve kterých jsou automaty ve stejném kroku zpracování slova) - obrázek vpravo. Například pro slovo abbabab paralelně procházíme dvojicemi stavů [90,Po]/ pak [90,Pi], [91,Pi], [92,Pi], [93,^2], [92,Po], dále [93,P3] a [q2,M 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 29 Protože by bylo hodně náročné (a také nedeterministické a těžko naprogramovatelné) takto vyhledávat všechny dvojice stavu, ve kterých se nachází výpočet v obou automatech ve stejném kroku, použijeme jinou (trochu „otrockou") metodu: • jako množinu stavů použijeme množinu všech uspořádaných dvojic, kde první prvek je stav prvního automatu a druhý prvek je stav druhého automatu, • vytvoříme á-funkci nebo tabulku přechodů, ve které zachytíme společné přechody na stejný signál v obou automatech, • odstraníme nepotřebné stavy. Počátečním stavem bude uspořádaná dvojice obsahující počáteční stavy obou původních automatů, koncové stavy budou všechny uspořádané dvojice, ve kterých jsou oba původní stavy koncovými. Jednodušší je využití tabulky přechodů. Podle tabulek původních automatů vytvoříme tabulku pro výsledný automat (kombinace řádků ve stejném sloupci). a b a b 90 90 9i Po Pl,P3 qi 91,92 Pl P2 Pi <- 92 93 P2 Po 93 92 P3 P4 Tabulka přechodů výsledného konečného automatu má 4 • 5 = 20 řádků: a b (pokračování) a b [9o, Po] [90,Pi], [90,P3] [92, Po] [93,Pl], [93,P3] [9o, Pi] [9o, P2] [91, Pl] [92, Pl] [93, P2] [9o, P2] [91, Po] [92, P2] [90, P3] [91, P4] [92, P3] [9o, P4] <- [92, P4] [91, Po] [93, Po] [91, Pi] [91, Pl], [92, Pl] [93, Pl] [92, Pi] [91, P2] [91,Po], [92,Po] [93,P2] [92, Po] [91, P3] [91, P4], [92, P4] [93, P3] [92, P4] [91, P4] [93, P4] Nyní odstraníme nepotřebné (tj. nedosažitelné a nadbytečné) stavy tak, jak jsme se učili v předchozích kapitolách, obsah množin je průběžně tříděn pro usnadnění porovnávání. 50 = {[90,Po]} 51 = {[90,Po], [90,Pi], [90,P3]} 30 Kapitola 2 Regulární jazyky s2 = {[qo Po]- [qo pí], [qo P3], [qo P2], [qi pí], [qi P4]} s3 = {[% Po]- [qo pí], [qo P2], [qo P3], [qi pí], [qi P4], [qi Po], [q2 Pl]} 1S4 = {[% Po]- [qo pí], [qo P2], [qo P3], [qi po], [qi pí], [qi P4], [?2 Pl], [q3 P2]} S5 = {[% Po]- [qo pí], [qo P2], [qo P3], [gi po], [qi pí], [qi P4], [?2 pi], P2], [?2 Po]} = {[% Po]- [qo pí], [qo P2], [qo P3], [qi po], [qi pí], [qi P4], [?2 Po], [q2 Pl], [q3 P2], pí] p3]} s7 = {[% Po]- [qo pí], [qo P2], [qo P3], [gi po], [qi pí], [qi P4], [?2 Po], [q2 Pl], pi], P2] P3]- [92 P a\) Ss = {[% Po]- [qo pí], [qo P2], [qo P3], [qi po], [qi pí], [qi P4], [?2 Po], [q2 Pl], P4], pí] [q3 P2]- [qs P3]} = s7 Odstranili jsme stavy [g0,P4], [gi,P2], [gi,P3], fe,P2], [q2,Ps], fe,Po], fe,P4], které jsou nedosažitelné z počátečního stavu. Dále pracujeme s touto tabulkou přechodů: a b [90, Po] [?0,Pl], feo,P3] [90, Pl] [?0,P2] [qi, pí] [90, P2] [91, Po] [qo,ps\ kl, P4] [qi, po] [qi, pí] [91, pí], fe, pi] [91, P4] te, Po] te,pi], te,P3] fe, pí] fe,P2] <- fe, p4] te,pi] fe, pi] te,P2] te, Po] te,P3] [Q2,Pa] Odstraníme nadbytečné symboly (ze kterých neexistuje cesta do koncového stavu): Eo = {[92,P4]} El = {[?2,P4], fe,P3]} E2 = {[?2,P4], fe,P3], fe,Po]} E3 = {[g2,Po], [Q2,Pa], fe,P3], fe,P2]} E4 = {[g2,Po], [?2, Pl], [Q2,Pa], fe,P2], fe,P3]} Eb = {[?2, Po], fe,Pl], [?2,P4], fe,P2], [?3,P3], Pl], [93, Pl]} Eg = {[gi,Pl], [92, Po], [92, Pl], [?2,P4], fe, Pl], [93, P2], [?3,P3], [90, Pl]} £7 = {[go,pi], [91,pí], [92,po], [92,pí], [?2,P4], [93,pi], te,P2], te,P3], [go,po]} ^8 = íbo,Po], [?0, Pl], [qi, Pl], fe,Po], [?2, Pl], [?2, P4], [93, Pl], fe,P2], [?3,P3]} = #7 Po odstranění stavů [<7o,P2], [<7o,P3], [<7i,Po], [<7i,p4] dostáváme tuto tabulku přechodů (s původním označením stavů a po přeznačení na písmena): 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 31 a b a b [qo,Po] [Qo,Pi] -> A B [qo,Pi] [qi,pi] B C [Qi,Pi] [qi,pi], [q2,pi] C C, E [Q2,Po] fe,Pl], [Q3,P3] D G, K [Q2,Pl] [Q3,P2] E H <- [Q2,Pa] <— F fe,Pl] fe,Pl] G E [Q3,P2] [?2, Po] H D [Q3,P3] [92, P4] K F Stavový diagram (stavy jsou přeznačené): Úkol 2.9 1. Vytvořte deterministické konečné automaty pro jazyky Li = {if, then, else} a L2 = {if, iff, elif}, v každém z automatů stačí jediný koncový stav pro všechna slova daného jazyka. Potom pomocí automatů vytvořte průnik těchto jazyků. 2. Sestrojte konečný automat, který je průnikem jazyků následujících automatů (pracujte s tabulkami přechodů). Odstraňte všechny nedosažitelné a nadbytečné stavy a sestrojte stavový diagram. 0 1 0 1 -> A B A -> E F ^B C F F H C D H H D B Pro kontrolu: po odstranění nepotřebných stavů by měl automat mít osm stavů, z toho jeden koncový, jeden cyklus přes jeden stav a jeden cyklus přes tři stavy. 32 Kapitola 2 Regulární jazyky 2.3.7 Homomorfismus Homomorfismus je takové zobrazení, které • zachovává neutrální prvek (tj. u řetězců prázdný řetězec e zobrazí opět na e) • zachovává zobrazení operace, pro kterou je definován (u řetězců jde o zřetězení, tj. h(a ■ b) = h(a) ■ h(b)) • výsledkem zobrazení prvku (signálu, znaku) je vždy řetězec (u substituce, což je zobecnění homomorfismu, je výsledkem zobrazení množina řetězců). Když konstruujeme konečný automat homomorfismu pro některý jazyk, využíváme plně způsobu definice daného homomorfismu - pokud je v předpisu tohoto zobrazení například h(a) = xyz, tj. znak a má být zobrazen na řetězec xyz, vezmeme postupně všechny přechody označené znakem a a nahradíme je cestami rozpoznávajícími slovo xyz. Každá z těch cest musí být samozřejmě samostatná, vždy jeden konkrétní přechod označený signálem a nahradíme jednou samostatnou cestou pro xyz. Příklad 2.15 - Podle následujícího automatu sestrojte konečný automat rozpoznávající jazyk podle zadaného homomorfismu. Jazyk rozpoznávaný původním automatem je L = {e} U {ablacP \ i,j > 0}, po úpravě dostáváme automat rozpoznávající jazyk h(L) = {e} U {df(ffd)ldfd? \ i,j > 0}. 2.3 Uzáverové vlastnosti - operace nad regulárními jazyky 33 Ukol 2.10 - Je dán konečný automat A s jazykem L = L (A) a homomorfismy h\ a h2. hi(a) = 01 h^b) = 110 hi(c) = 1 h2 (a) = dd h2{b) = g h3(c) = dg a b c 9o 9i 92 <- 9i 9i 92 93 9i 93 92 Zjistěte jazyky h\ (L) a h2 (L) a vytvořte také konečné automaty pro tyto jazyky (úpravou automatu A). Jazyk automatu A]e L(A) = {aď | i > 0} U {b(ab)lcc^ \ i,j > 0}. Dále pro výsledné automaty sestrojte jejich á-funkci včetně plné specifikace, nezapomeňte na změnu abecedy. 1 1 2 ^2 1 3 ^3 3 Nejdřív vytvoříme množiny R°, - regulární výrazy pro nejkratší cesty bez mezistavů. 38 Kapitola 3 Regulární výrazy Horní index znamená maximální číslo stavu, přes který může vést cesta mezi stavy uvedenými v dolním indexu (omezení z horního indexu se netýká okrajových stavů cesty). Například R\3 je regulární výraz odpovídající cestě ze stavu 1 do stavu 3 takové, že vede přes stavy s číslem maximálně 2, tedy přes stavy 1 a 2. Horní index budeme postupně zvyšovat. V prvním kroku se setkáme se vztahem (a + e)* = a* a dále (a + e) • a* = a*. Ri! = (a + e) + (a +e) • (a + • (a + e) = i?22 = £ + a • (a + e)* • 6 = £ + aa*6 = a + £ + a* = a* i?23 = & + a • (a + e)* • 0 = b R{2 = b + (a + e)-(a + e)* -b = b + a*b = a*b R^ = 0 + 0 • (a + e)* • (a + e) = 0 R{3 = 0 + (a + e) • (a + e)* • 0 = 0 i?^ = 0 + 0 • (a + e)* • b = 0 fí^ = a + a- (a + £)* • (a + e) = a + aa* = aa* i?^3 = (b + e) + 0 • (a + e)* • 0 = b + £ V druhém kroku budeme hodně používat vztah (e + acŕb)* = (aa*b)*. R\i = a* + a*6 • (e + aa*b)* ■ aa* = a* + a*b(aa*b)*aa* R22 = a*b + a*6 • (e + aa*6)* • (e + aa*b) = a*b + a*b(aa*b)* = a*b(aa*b)* ^3 = 0 + a*6 • (e + aa*6)* • 6 = a*b(aa*b)*b i?2i = aa* + (e + aa*&) • (e + aa*b)* ■ aa* = (aa*b)*aa* i?22 = £ + aa*^ + (e + aa*&) • (e + aa*b)* ■ (e + aa*6) = (aa*6)* fí23 = 5 + (£ + aa*5) . (£ + aa*5)* . 5 = (aa*b)*b = 0 + 0 • (e + aa*6)* • aa* = 0 fí|2 = 0 + 0 . (£ + aa*6)* . (£ + aa*6) = 0 fí|3 = b + e + 0 . (£ + aa*6)* .b = b + £ Protože máme pouze tři stavy, třetí krok je poslední. Zde není třeba vypočítávat výrazy přes všechny dvojice stavů. Potřebujeme pouze ty cesty, které vedou z počátečního stavu do některého koncového. V automatu jsou dva koncové stavy, dostaneme tedy dva regulární výrazy. Rf2 = a*b(aa*b)* + a*b(aa*b)*b • (6 + e)* • 0 = a*b(aa*b)* Rf3 = a*b(aa*b)*b + a*b(aa*b)*b ■ [b + e)* • (6 + e) = a*b(aa*b)*b + a*b(aa*b)*b ■ b* = = a*b(aa*b)*b ■ (e + b*) = a*b(aa*b)*bb* Výsledkem je regulární výraz odpovídající jazyku rozpoznávanému daným automatem: R = R\2 + R\3 = = a*b(aa*b)* + a*b(aa*b)*bb* = a*b(aa*b)* ■ (e + bb*) = a*b(aa*b)*b* 3.3 Vytvoření regulárního výrazu podle konečného automatu 39 Příklad 3.4 - Zjistíme regulární výraz odpovídající jazyku rozpoznávanému následujícím automatem: a b -> 1 4 2 2 3 ^3 3 ^4 3 Nejdřív vytvoříme množiny R0^: #n #12 #13 #21 n22 #23 i?24 a e b #31 #32 #33 R°34 a + e i?41 /t42 #43 -R44 a e Ve čtyřech krocích (číslo kroku je v horním indexu) zjistíme další množiny: R{ R} e + £ • £ • £ b + e-e* -b R\z = 0 + £.£*.| i?14 a + £ • a R1 R1 R1 R1 21 1 22 1 23 1 24 a + a ■ e = a e+aeb = e+ab b + $ = b 0 + aea = aa R1 R1 R1 R1 31 1 32 1 33 1 34 a+£+0 = a+£ R1 R1 R1 R1 41 42 43 44 a + 0 £ + 0 a £ #11 £ + b(ab)*a = (ba)* b + b(ab)* (e + a&) = b(ab)* 0 + 6(a6)*6 = 6(a6)*6 = a + b(ab)*aa = a + ba(ba)*a #12 #13 L14 #21 =« + (£ + ab)(ab)*a = (ab)*a •"■22 #23 #24 = aa + (£ + ab)(ab)*aa = (ab)*aa (ba) (ab)* b + (e + ab)(ab)*b = (ab)*b #31 #32 #33 #34 #41 /t42 #43 íl44 0 + 0 = 0 0 a+£+0=a+£ a + 0 £ + 0 a £ (ba)* + 0 #11 fíf2 = b(aby + 0 (6a)* : b(ab)* Rf3 = b(ab)*b + b(ab)*ba*(a + e) = b(ab)*ba* RfA = (ba)*a + 0 = (6a)*a fí^ = (a5)*a + 0 = (a6)*a #22 = (abt + 0 = (afe)* fí33 = (afe)*fe + (aft)*fta*(a + e) = (ab)*ba* #24 = (ab)*aa + 0 = (ab)*aa #31 #I2 #I3 #I4 #ll #42 #t3 #44 a + £ + (a + e)a*(a + e) a + aa*(a + e) = aa* £ 40 Kapitola 3 Regulární výrazy Ve čtvrtém kroku nás zajímají pouze cesty vedoucí z počátečního stavu do koncových stavů: Rf3 = b(ab)*ba* + (ba)*a • s* • aa* = b(ab)*ba* + (ba)*aaa* = (ba)*bba* + (ba)*aaa* Rfi = {ba)*a + (ba)*a ■ e* ■ e = (ba)*a Regulární výraz odpovídající jazyku zadaného automatu je R = Rf% + R\4 = = (ba)*bba* + (ba)*aaa* + (ba)* a = (ba)* (bba* + aaa* + a) 3.4 Minimalizace a normování konečného automatu 3.4.1 Minimální konečný automat Minimalizace konečného automatu je snížení počtu stavů při rozpoznávání téhož jazyka, a to na úroveň absolutně nezbytnou vzhledem k rozpoznávanému jazyku. Účelem může být samotné snížení počtu stavů (například z důvodu snadnějšího naprogramování či snížení složitosti automatu) a nebo zajištění porovnatelnosti dvou automatů. Při minimalizaci automatu A s množinou stavů 1, 2,..., n postupujeme takto: • automat A by měl být deterministický; pokud není, převedeme ho do deterministického tvaru, • podle automatu As n stavy vytvoříme n konečných automatů A\, A2, • • •, An, které jsou určeny téměř stejně (včetně přechodové funkce a koncových stavů) jako automat A, liší se pouze koncovým stavem - automat Aí má počáteční stav i (1 < i < n), 3.4 Minimalizace a normování konečného automatu 41 • postupem popsaným v předchozí kapitole zjistíme regulární výrazy odpovídající všem automatům A% vytvořeným v předchozím bodu, zde vlastně zjišťujeme nejdů-ležitější charakteristiku cesty v grafu automatu z uzlu (stavu) i do koncových stavů, • regulární výrazy vhodně upravíme, aby byly snadno porovnatelné, • pokud pro některé dva automaty Ai a Aj (i ^ j) vychází stejný regulární výraz, znamená to, že stavy i a j jsou rovnocenné (ekvivalentní) v základní charakteristice - na cestě z těchto dvou stavů jsou rozpoznávána tatáž slova (a žádná jiná, jde o ekvivalenci), proto jeden z nich vlastně můžeme vyřadit, a to následovně (chceme odstranit stav j a jeho funkci nahradit stavem i): - nejdřív všechny přechody směřující do stavu j přesměrujeme do stavu i, - pak můžeme stav j odstranit včetně všech přechodů, které z něho vycházejí. Příklad 3.5 - Minimalizujeme následující konečný automat: Automat je deterministický, proto můžeme začít se zjišťováním regulárních výrazů. RÍl = £ R11 = £ R\i = £ RÍi = £ = a R12 = a r12 = a RÍ2 = a = 0 r13 = 0 r13 = aa RÍ3 = aa R°u = 0 Ru = 0 r14 = ab R\a = ab i1 = 0 R\i = 0 R21 = 0 Rli = 0 R22 = £ R22 = £ íl22 = £ R%2 = £ R23 = a R23 = a r23 = a R%3 = a n2a = b = b n2a = b n2a = b RÍl = 0 R31 = 0 RÍl = 0 RÍl = 0 R32 = 0 R32 = 0 R32 = 0 R32 = 0 Rh = £ R33 = £ Rh = £ R33 = £ R°34 = 0 R34 = 0 R34 = 0 Rh = 0 = 0 R\i = 0 R\i = 0 Rli = 0 = 0 R42 = 0 /t42 = 0 R42 = 0 Rl3 = a R43 = a R%, = a RÍ3 = a Ru = b + e R44 = b + e ř?2 íl44 = b + e R44 = b + e 42 Kapitola 3 Regulární výrazy Zajímají nás pouze cesty vedoucí z jednotlivých stavu do koncových stavu (což je jen stav 3), proto zjistíme pouze tyto regulární výrazy: Rf3 = aa + abb*a = ab*a i?23 = a + bb*a = b*a r33 = £ i?43 = a + (6 + e)6*a = a + 6* a = 6* a Při porovnání zjistíme, že výrazy a i?|3 se rovnají, proto jeden z nich můžeme odstranit. Je jedno, který zvolíme, jen nesmíme zapomenout všechny přechody vedoucí do rušeného stavu přesměrovat do ekvivalentního stavu. Příklad 3.6 - Minimalizujeme následující konečný automat (počáteční stav je prvkem množiny koncových stavů): a b 1 2 4 2 2 3 ^3 3 2 4 1 5 ^5 3 2 Protože v automatu je více stavů než u předchozího a výpis všech pomocných množin by byl nepřehledný, vypíšeme pouze ty množiny, které nejsou prázdné (nemají hodnotu 0). a b R R°23 R°32 22 — a + e = b = b r33 R44 a + e a /t45 RI2 RI3 F?0 •"-55 R12 r1a a b R r23 R32 22 = a + e = 6 = 6 fí33 a + e a aa i?44 = £ + ab R\h R53 R55 3.4 Minimalizace a normování konečného automatu 43 = £ R22 = a* i?41 = a Rh - b R12 = aa* R23 = a*b /l42 = aaa* Rh = ba* Rl3 = aa*b R32 = ba* -^43 = aaa*b Rh = a + ba*b R\a = b R33 = a + £ + ba*b «44 = £ + ab Rh = e R'li = £ Rll = a R\2 = aa* + aa*(a + ba*b)*ba * /t42 = aaa* + aaa*b(a + ba* b)* ba* Rfs = aa*b(a + ba*b)* ^3 = aaa*b(a + ba*b)* R\a = b -R44 = £ + ab R22 = a* + a*b(a + ba*b)*ba* i?45 = b R323 = a*b(a + ba*b)* #52 = ba* RÍ2 = (a + 6a* 6)* 6a* ^3 = (a + ba*b)(a + ba*b)* Rh = (a + ba*b)* -"55 = £ Rf1=£ + b{ab)*a = (ba)* Rf2 = aa* + aa*(a + ba*b)*ba* + b(ab)*(aaa* + aaa*b(a + ba*b)*ba*) Rf3 = aa*b(a + 6a*6)* + b(ab)*aaa*b(a + 6a*6)* = (e + 6(a6)*a)(aa*6(a + ba*b)*) = = (ba)*aa*b(a + ba*b)* Rf4 = b Rf5 = b(ab)*b = (ba)*bb R\2 = a* + a*b(a + ba*b)*ba* fí|2 = (a + ba*b)*ba* fí|3 = (a + 6a* 6)* i?42 = (a6)*(aaa* + aaa*b(a + ba*b)*ba*) i?43 = (ab)*aaa*b(a + 6a*6)* i& = (a6)* i?|5 = (a6)*6 fif2 = 6a* fí|3 = (a + 6a*6)(a + 6a*6)* #55 = e V posledním kroku se zaměříme pouze na cesty končící v některém koncovém stavu (to jsou stavy 1,3 a 5), vypíšeme i prázdné množiny. fifi = (6a)* i4 = 0 #13 = (ba)*aa*b(a + 6a*6)*+ i?|3 = a*6(a + 6a*6)* +(6a)*66(a + 6a*6)(a + 6a*6)* #25 = 0 R\s = (bafbb 44 Kapitola 3 Regulární výrazy r31 R33 R5 (a + ba* b)* R\z = (ab)*aaa*b(a + ba*b)* + 35 (ab)*a [ab)*aa +(ab)*b(a + ba*b)(a + ba*b)* (ab)*b Rl •"■55 53 _ (a + ba*b)(a + ba*b)* = e Zbývá zjistit jazyky jednotlivých automatů A\, A2,..., A$ (odlišujících se pouze svým počátečním stavem -1,2,...,5): L(A2) L(A3) L(Ai) L(A)=Rl1+Rl3 + Rlb = (ba)* + (ba)* (aa*b(a + ba*b)* + bb(a + ba*b)(a + ba*b)* + bb (ba)* + (ba)* (aa*b(a + ba*b)* + bb(a + ba*b)* (ba)* + (6a)*(aa*6 + bb)(a + 6a*6)* #21 + r23 + #25 = a*ka + ba*bt Rl1+Rl3 + Rl5 = (a + ba*b)* R\i + R43 + R\b = (ab)*a + (ab)* aaa*b(a + ba*b)* + (ab)*b(a + ba*b)* (ab)*a + (ab)*(aaa*b + b)(a + ba*b)* L(A5 R5I + -RRS + i?. 53 l55 (a + 6a*6)* Jazyky £(.4.3) a £(.4.5) jsou stejné, proto jeden z těchto stavů můžeme odstranit. a 6 1 2 4 2 2 3 ^3 3 2 4 1 3 Ukol 3.4 1. Minimalizujte následující konečný automat: a b -> 1 2 4 2 3 2 ^3 4 2 2 5 3 5 3.4 Minimalizace a normování konečného automatu 45 2. Následující (nedeterministický) konečný automat • převeďte na deterministický (po převodu a odstranění nepotřebných stavů by měl mít čtyři stavy), • vhodně přeznačte stavy (čísla od 1) a určete jazyk tohoto konečného automatu, • minimalizujte ho. Při úpravách regulárních výrazů lze využít například těchto vztahů: • b(ab)* = (ba)*b • e + b(ab)*a = e + (ba)*ba = (ba)* • (ab)*a = a(ba)* . e + (ba)*aa*b ((ba)*aa*b)* = • b(ab)*a = (ba)*ba = ((ba)*aa*b)* Pozor, sice platí rovnost e + b*a = b*, ale například regulární výrazy e + b*ac* a b*c* nejsou ekvivalentní! 3.4.2 Normovaný konečný automat Účelem normování (čehokoliv) je uvést daný objekt (prvek, automat, atd.) do stavu s určitými žádanými vlastnostmi, a to za účelem snadnějšího provádění dalších operací s tímto objektem (například porovnávání nebo programování). Když normujeme konečný automat, chceme, aby měl vhodně označené stavy (tedy normujeme označení stavů) - stavy by měly být pojmenovány čísly od 1 a navíc by jejich označení mělo být seřazeno. Kromě vlastního označení mají stavy jen jedinou další charakteristiku - regulární výraz odpovídající cestě z daného stavu do koncových stavů. Tuto charakteristiku použijeme pro vytvoření metriky při řazení označení stavů. Postupujeme takto: • minimalizujeme konečný automat, • pro každý stav určíme regulární výraz cesty z tohoto stavu do koncových stavů, • v regulárních výrazech najdeme nejmenší slova, 46 Kapitola 3 Regulární výrazy • stavy porovnáváme takto: 1. stav, jehož regulární výraz má kratší nejmenší slovo, dostane vyšší index než stav s delším nejmenším slovem, například stav s nejmenším slovem ab bude mít vyšší číslo v označení než stav s nejmenším slovem bba, 2. pokud dva stavy mají nejmenší slova stejně dlouhá, pak zvolíme navíc další metriku - abecedu, například stav s nejmenším slovem ab bude mít vyšší číslo v označení než stav s nejmenším slovem bb, 3. pokud se nejmenší slova dvou stavů shodují (tj. předchozí metriky selhávají), pak v regulárních výrazech těchto stavů hledáme druhé nejkratší slovo a to porovnáváme, pokud se opět shodují, hledáme třetí, atd., dokud nenajdeme rozdíl. Přestože poslední uvedený způsob porovnání může trvat hodně dlouho, u minimalizovaného automat je vždy konečný, protože regulární výrazy pro žádné dva stavy nejsou ekvivalentní (kdyby byly ekvivalentní, jeden z nich bychom vyřadili při minimalizaci). Příklad 3.7 - Seřadíme následující regulární výrazy podle výše uvedených kritérií. Reg. výraz Nejkratší slova Zjištěné pořadí Přidělený index ba(ba)* ba, baba,bababa,... 8 3 aabb* aab, aabb, aabbb,... 1 ab(ab)* ab, abab, ababab,... 5 aaba* aab, aaba, aabaa,... 2 ab(ba)* ab, abba,abbaba,... 7 4 b*aa*b ab, aab, bab, aaab, baab, bbab,... 5 6 b*(aa)*b b, bb, aab, bbb, baab, aaaab,... 3 8 a*b + b*a b, a, ab, ba, aab, aab, bba,... 9 ab + ba ab, ba 7 (ab + ba)* e, ab, ba, abab, abba, baab, baba,... 1 10 Příklad 3.8 Znormujeme automat, který jsme získali minimalizací v příkladu 3.6 na straně 42. a b 1 2 4 2 2 3 ^3 3 2 4 1 3 3.4 Minimalizace a normování konečného automatu 47 Využijeme také regulární výrazy pro jednotlivé stavy: L(Ai) = L(A) = i?fx + i?f3 + Rf5 = (ba)* + (ba)*(aa*b + bb)(a + ba*b)* L(A2) = R^ + i?l3 + i?|5 = a*b(a + ba*b)* L(A3) = R531 + i?|3 + i?355 = (a + 6a*6)* ^3 fi41 + iž^q + i?. ■43 l45 (ab)*a + (ab)*(aaa*b + b)(a + ba*b)* Z těchto regulárních výrazů vybereme nejkratší slova: Stav Nejkratší slova Nové označení stavu 1 ab, bb, ba, aba,... 1 2 b, ba, ab,... 2 3 e, a, bb,... 4 4 a,b,... 3 Stavy přeznačíme a vše ostatní zachováme. Po přeznačení dostaneme tento konečný automat: a 6 1 2 3 2 2 4 ^4 4 2 3 1 4 Úkol 3.5 - 1. Setřiďte podle výše zadaných kritérií následujících 16 regulárních výrazů: • a(a + b)a • a*(a + b)a* • (a*b + a)* • a(a + 6)*a • a*b + a • (a*6 + 6)* • a(a + b)*b • a*6 • (6*a + b)* • a*(a + b)a • b*a • (6*a + 6)* Pozor, může se stát, že některé dva regulární výrazy jsou ekvivalentní. 2. Podle konečného automatu v zadání příkladu 3.4 na straně 39 dopočtěte zbývající množiny Rfj, minimalizujte tento automat a normujte ho. 3. Podle konečného automatu v zadání příkladu 2.12 na straně 26 vytvořte všechny potřebné množiny R\minimalizujte (pokud není minimální) a normujte ho. aA |aB \ a B -^bB\b V gramatice není žádné e-pravidlo (tj. pravidlo, na jehož pravé straně je řetězec e), proto počáteční stav nebude patřit do množiny koncových stavů (tato množina bude jed- 48 4.1 Konečný automat podle regulární gramatiky 49 noprvková). Jako abecedu použijeme množinu terminálů, stavy vytvoříme z neterminálů a přidáme jeden koncový stav X. Přechody tvoříme podle pravidel gramatiky - například podle pravidla A —> aB přidáme do á-funkce ô (A, a) 3 B. Postup je dobře vidět na á-funkci: Á = ({S,A,B,X}, {a,b}, 6, S, {X}) 5(S, a) = {S} podle S aS 5(S, b) = {A} podle S bA ô (A, a) = {A,B,X} podle A -> aA \ aB \ a 5(B, b) = {B, X} podle B -> bB | b Podobně sestrojíme stavový diagram a tabulku přechodů: aO aO bO b a b -> s S A A A, B, X B B,X <- X Jazyk generovaný gramatikou a rozpoznávaný automatem je L (G) = L (A) = a*ba*a(e + b*b) Příklad 4.2 - Narozdíl od předchozího příkladu zde máme gramatiku s e-pravidlem: G = ({S, A, B}, {a, b}, P, S), v množině P jsou pravidla S bA | e A —> aB | a B -^bA\b V jazyce generovaném gramatikou je také prázdné slovo e a toto slovo musí přijímat i konečný automat, který vytvoříme. To lze zajistit pouze tak, že počáteční stav automatu přidáme do množiny koncových stavů. A = ({S,A,B,X}, {a,b}, S, S, {S,X}) S(S,b) : ô (A, a) 5(B,b) {A} -{B,X} :{A,X} a b s A A B,X B A,X <- X 50 Kapitola 4 Regulární gramatiky Jazyk generovaný gramatikou a rozpoznávaný automatem je L(G) = L(A) =e + b(ab)*a + b(ab)*ab = e + b(ab)*a(e + b) Úkol 4.1 - Podle následujících gramatik sestrojte ekvivalentní konečný automat (tj. rozpoznávající jazyk generovaný touto gramatikou). = ({S,A,B}, {a. b, c}. P, S) G2 = ({A,B,C}, {0,1}, P, A) S - -> aS \ bS \ cA A - -> 0B j 1C 1 e A - -> aA cB a B - -> oc 11C B - ->bB\cA\b C - -> 15 1 0 G3 = ({R,Y,Z, W}, {a,b. c}, P, R) G4 = ({5, A, 5, C}, {0,1,2}, P, 5) R- -> aR bR cZ S - -> 0A 1 15 j 2C 1 e Y - -> cR\aY \b A - -> 05 1 0 Z - -> aY | aW B - -> ic 11 W -^bR\b C - -> 2A 4.2 Regulárni gramatika podle konečného automatu Při zjišťování gramatiky generující tentýž jazyk, který je rozpoznáván zadaným konečným automatem, je nejjednodušší obrátit postup, který jsme použili pro vytvoření automatu podle gramatiky. Když jsme sestrojili konečný automat podle regulární gramatiky, automat měl vždy tyto vlastnosti: • pokud v jazyce generovaném gramatikou není slovo e, pak - existuje jediný koncový stav (nově přidaný), obvykle pojmenovaný X, - ze stavu X nevede žádný přechod (tj. když se výpočet dostane do koncového stavu, nelze dále pokračovat). • pokud v jazyce generovaném gramatikou je slovo e, pak - kromě nově přidaného koncového stavu X je v množině koncových stavů i počáteční stav, - ze stavu X nevede žádný přechod, - do počátečního stavu nevede žádný přechod (ekvivalent k faktu, že pokud v gramatice máme pravidlo S —> e, pak se symbol S nesmí vyskytovat na pravé straně žádného pravidla). 4.2 Regulární gramatika podle konečného automatu 51 Abychom tedy mohli použít opačný postup k postupu předchozímu, musíme zadaný automat nejdřív upravit do tvaru odpovídajícího výše uvedeným požadavkům. Úprava spočívá v těchto krocích (jejich pořadí je důležité): 1. Jestliže počáteční stav patří do množiny koncových stavů a zároveň do tohoto stavu vede některý přechod: • vytvoříme nový počáteční stav (také zařadíme do množiny koncových stavů), do kterého nebudou vést žádné přechody, ale z něho budou vést tytéž přechody jako z původního počátečního stavu, • původní počáteční stav zůstane v množině koncových stavů. 2. Pokud je v množině koncových stavů více než jeden stav (případně kromě počátečního stavu, toho se tento bod netýká): • vytvoříme nový koncový stav X (nebo jinak označený), • ze stavu X nepovede žádný přechod, ale do tohoto stavu povedou tytéž přechody, které vedou do původních koncových stavů, • původní koncové stavy sice v automatu necháme, ale vyřadíme je z množiny koncových stavů (netýká se počátečního stavu). 3. Jestliže z koncového stavu vedou přechody, problém vyřešíme stejně jako v předchozím bodě. Příklad 4.3 - Nejdřív si ukážeme jednodušší případ - konečný automat odpovídající uvedeným požadavkům. Jak vidíme, stav q2 zde vlastně zastupuje stav X podle předchozího postupu. To znamená, že v gramatice bude množina neterminálů dvouprvková - {qo,qi}, ze stavu q2 žádný neterminál nevytvoříme a pravidla, která s ním souvisejí, budou sloužit k ukončení generování slova. Můžeme také přejmenovat neterminály. a b G = ({90,9i}, {a,b}, P, qo) G = ({A, B}, {a,b}, P, A) 9o qi 92 q0 -> aq1\b A - aB j b qi 92 91 q1 ->■ a 1 bqi B - > a\bB <- 92 Gramatika, kterou jsme vytvořili, generuje jazyk L(G) = ab*a + b, což je také jazyk rozpoznávaný zadaným automatem. 52 Kapitola 4 Regulární gramatiky Příklad 4.4 - Vytvoříme regulární gramatiku generující jazyk tohoto automatu: •O s <0 Tento automat má dva koncové stavy, z nichž žádný není počáteční, proto musíme redukovat počet koncových stavů. Navíc z obou koncových stavů vycházejí přechody, to je další důvod pro transformaci. Vytvoříme stav X, do kterého nasměrujeme všechny přechody mířící do původních koncových stavů. Stav X pak bude jediným koncovým stavem. Po úpravě sestrojíme regulární gramatiku stejně jako u předchozího příkladu. •O s a b c s A, X S A B,X B C C A, X <- X G = ({S, A, B,C}, {a,b,c},P,S) S -> aA \ a \ bS A — aB a B - - bC C - cA 1 c Jazyk generovaný gramatikou je L (G) = b*a(abc)*(e + a). Příklad 4.5 - Následující automat nemusíme upravovat, můžeme přímo napsat regulární gramatiku -startovací symbol patří do množiny koncových stavů, ale do něho nevede žádný přechod. M s M B 0 1 s A A A B <- B G = {{S, A}, {0,1}, P, S) S 1A | e A -> 0A I 1 Generovaný (rozpoznávaný) jazyk je L (G) = 10*1. Příklad 4.6 - V posledním příkladu si ukážeme převod automatu, jehož počáteční stav je zároveň stavem koncovým a vedou do něho přechody. Nejdřív automat upravíme. Přidáme nový (počáteční) stav C, který také bude patřit do množiny koncových stavů (aby automat mohl rozpoznat prázdné slovo e) - tento stav bude 4.2 Regulární gramatika podle konečného automatu 53 využit pouze na začátku výpočtu. Potom přidáme nový koncový stav X, který využijeme na konci každého výpočtu. Původní koncové stavy (kromě počátečního stavu C vyřadíme z množiny koncových stavů. Ze stavu B nevede cesta do koncového stavu, proto může být odstraněn. Výsledná gramatika je následující: G = ({C,S,A}, {0,1}, P C) C ^0A S 0A A -> OB | 0 | 1 Jazyk generovaný gramatikou G vyjádřený regulárním výrazem je L(G) = 0(10)*(0 + 1). Úkol 4.2 - K následujícím konečným automatům vytvořte ekvivalentní regulární gramatiky: (a) 0} a vytvoříme derivaci (odvození) slova aabaab. G = ({S,A}, {a,b}, P, S) S Ab A —> aAa\b Neterminál A generuje téměř celé slovo, až na poslední symbol b. Část slova generovaná tímto neterminálem je symetrická, proto pravidla jsou vlastně lineární (každá lineární gramatika je zároveň bezkontextová, tedy zadání je v tomto směru splněno). Následuje derivace slova aabaab: S =>• Ab =>• aAab =>• aaAaab =>• aabaab Derivační strom je vlastně graf, který je stromem (má jediný kořen, každý uzel kromě kořene má právě jednoho předka a hrany jsou orientované, i když orientaci neznačíme), tvořený podle pravidel gramatiky použitých v derivaci, podle které je derivační strom vytvořen. 55 56 Kapitola 5 Bezkontextové gramatiky Příklad 5.2 - Sestrojíme bezkontextovou gramatiku pro jazyk L = {0n102nl* | i, n > 1} a vytvoříme derivaci slova 0010000111 a derivační strom k této derivaci. G = ({S, A, B}, {0,1}, P, S) S AB A -> 0A00 | 0100 B -> 15 | 1 Derivace slova 0010000111 je následující: S=> AB=> 0A005 00100005 => 001000015 => 0010000115 => 0010000111 Modře je vyznačena pravá část pravidla, které bylo v daném kroku odvození použito (například v druhém kroku jsme použili pravidlo A —> 0A00). Derivační strom se vždy vztahuje ke konkrétní derivaci. Podle výše uvedené derivace postupně sestrojíme derivační strom takto (jsou uvedeny i mezikroky): S => AB S=>AB=> 0A00B B 0 A 0 0 S=> AB=> 0A005 => 00100005 S => ... => 00100005 => 001000015 A —>• 0100 S B^IB S 0 1 0 0 0 1 0 0 s=> ...=> 001000015 => 0010000115 s=> ...=> 0010000115 => 0010000111 B^IB S S Q A Q Q l B Q A Q Q l B 0100 1 B 0100 í B 1 5.2 Vlastnosti bezkontextových gramatik 57 V jednotlivých krocích je kromě samotného stromu uvedeno použité pravidlo a také momentální stav derivace. Modře je vyznačena větná forma, kterou jsme v daném kroku vytvořili. Můžeme si všimnout, že v derivačním stromě vždy jde o obsah listů stromu v daném kroku. Derivační strom dané derivace je poslední v pořadí. Úkol 5.1 - 1. Podle gramatiky a uvedené derivace z příkladu 5.1 sestrojte derivační strom. 2. Podle zadané gramatiky vytvořte derivaci slova ababa a k ní derivační strom. G = ({S, A, B}, {a,b}, P, S) S -> bAB | aBA | e A —> abAab | e B —> baBba | e 3. Podle gramatiky z předchozího příkladu vytvořte derivaci jakéhokoliv slova o délce alespoň 6 začínajícího symbolem b a k této derivaci sestrojte derivační strom. 4. Sestrojte gramatiky generující následující jazyky. V každém jazyce vyberte jakékoliv slovo o délce alespoň 3 symboly, vytvořte jeho derivaci a sestrojte k ní derivační strom. (a) Li = {(abýci(baý | i, j > 0} (b) L2 = {0nlln | n > 3} U {e} (c) L3 = {OAO' | i > 1} U {VOV | i > 1} (d) l4 = {abc, bad, faa, diff} (nezapomeňte, že na pravé straně pravidla může být jakýkoliv řetězec) 5.2 Vlastnosti bezkontextových gramatik 5.2.1 Redukce gramatiky Účelem redukce gramatiky je snížení počtu neterminálů při zachování generovaného jazyka. Odstraňujeme • nadbytečné neterminály (tj. neterminály ze kterých nelze vygenerovat žádné terminálni slovo), • nedostupné symboly (terminálni i neterminální - nelze je vygenerovat ze startovacího symbolu). 58 Kapitola 5 Bezkontextové gramatiky Zachováváme toto pořadí - nejdřív nadbytečné a pak teprve nedostupné. Používáme podobný postup jako při redukci množiny stavů konečného automatu. Příklad 5.3 - Redukujeme následující gramatiku: G = {{S, A, B, C, D}, {a, b, c, d}, P, S) S -> bS | bD | e A -> aCB | b AD B -> dB\d C -> bCC | aAbB D -> | cDfe | aS | e Nejdřív odstraníme nadbytečné neterminály. Rekurzívně vytvoříme množinu všech symbolů, které jsou buď terminálni a nebo z nich lze vygenerovat terminálni řetězec (v případě, že jde o neterminál). Bází rekurze je množina všech terminálů. V dalších krocích přidáváme neterminály z levých stran pravidel, na jejichž pravé straně jsou pouze symboly, které jsme do naší množiny přidali v předchozích krocích (a nebo pro ně existuje s-pravidlo). A^o = {a, b, c, d} Ni = {a, b, c, d, S, B, D} (podle pravidel S —> e, B —> d, D —> e) A^2 = {a, b, c, d, S, B, D} (podle pravidel S -> bS | bD, B -> dB, D -> cDb \ aS) Protože jsme do množiny A^2 oproti množině Ni nic dalšího nepřidali, rekurze končí. Množina neterminálů bude N P1N2 = {S, B, D}, vyřadíme neterminály AaC včetně všech pravidel, která je obsahují na levé nebo pravé straně. Gramatika po odstranění nadbytečných symbolů je následující: G' = ({S,B,D}, {a,b,c,d}, P', S) S -> bS I bD j e B -> dB j d D —> cDb j aS I e Zbývá odstranit nedostupné symboly. Postupujeme opět rekurzívně. Vytvoříme množinu symbolů, které se nacházejí v nějaké větné formě v derivaci ze startovacího symbolu. Začneme množinou obsahující pouze startovací symbol, v každém kroku přidáváme symboly, které se nacházejí na pravých stranách pravidel přepisujících symboly zařazené v předchozích krocích. Vo = {S} Vi = {S, b, D} (podle pravidel S -> bS | bD) V2 = {S, b, D, c, a} (podle pravidel D —> cDb \ aS) V3 = V2 Z postupu vyplývá, že pokud v některém kroku přidáme pouze terminálni symboly, v následujícím kroku již nelze nic přidat (protože terminály se nepřepisují žádným pravi- 5.2 Vlastnosti bezkontextových gramatik 59 dlem) a rekurze končí. Je zřejmé, že nedostupný neterminál je jeden (5) a terminál taktéž jeden (d). Redukovaná gramatika (tj. již bez nadbytečných i nedostupných symbolů) je následující: G" = ({S,D}, {a,b,c}, P", 5) S -> bS | bD | e D —> c56 I a5 I e Úkol 5.2 - Redukujte tyto gramatiky: d = ({5, A, B, C, D}, {a, b, c, d}, P, 5) G2 = ({5, A, B, C, D, E}, {0,1,2, 3}, P, 5) S -> aBa \bA\c\ ABc 5 -> ABO \ 2E \ AI \ e A -> aA | dL» | 6L»a A -> 0A0 | 15 | 15 5 -> a5 | | 65 5 -> 015 | ID \ EB C ^ aSc\cC \c C -> 2A | 15 | 0 D —> | aA6 5 ^ 51 | 35 5 -> 051 I 15 5.2.2 Převod na nezkracující bezkontextovou gramatiku Nezkracující bezkontextová gramatika buď vůbec neobsahuje e-pravidla (pokud v jazyce generovaném gramatikou není prázdné slovo), a nebo existuje jediné takové pravidlo, a to pro startovací symbol gramatiky, pak ale se startovací symbol nesmí vyskytovat na pravé straně žádného pravidla (to znamená, že v každé derivaci se vyskytuje pouze na jejím začátku, pak už ne). Při převodu na nezkracující gramatiku odstraňujeme e-pravidla tak, že „simulujeme" jejich použití. Příklad 5.4 - K následující gramatice vytvoříme ekvivalentní gramatiku s nezkracujícími pravidly. G = ({S,A,B}, {a,b}, P, 5) S —> aaB | bAb A —> aBa\e 5 -> AbAa | a Téměř všechna pravidla jsou nezkracující, je zde pouze jediné e-pravidlo - A —> e. Přepisovaný symbol A se nachází na pravé straně dvou pravidel - druhého a pátého. Obě tato pravidla necháme a přidáme jejich varianty se „simulovaným" použitím e-pravidla: 60 Kapitola 5 Bezkontextové gramatiky G' = ({S,A,B}, {a,b}, P', S) S -> aaB | bAb \ bb A —> aBa B —> AbAa | 6Aa | Aba \ ba \ a U prvního ze zpracovávaných pravidel máme jen jeden výskyt neterminálu A, tedy existuje pouze jediná další varianta (toto jediné A odstraníme - přepíšeme na e). U druhého zpracovávaného pravidla jsou dva výskyty neterminálu A, proto musíme vytvořit variant více - odstraníme jen první A, odstraníme jen druhé, a nebo odstraníme obě. Derivace v gramatice G' bude téměř stejná jako v gramatice G, ale kroky s použitím s-pravidel jsou „přeskočeny", například v gramatice G: S =>• aaB =>• aaAbAa =>• aabAa =>• aabaBaa =>• aabaaaa v gramatice G': S =>• aaB =>• aabAa =>• aabaBaa =>• aabaaaa Příklad 5.5 - K zadané gramatice vytvoříme ekvivalentní nezkracující gramatiku (tj. generující tentýž jazyk). G = ({S,A}, {a,b,c}, P, S) S —> aaS | bbA \ e A —> cSbSc | e Gramatika generuje také prázdné slovo. Proto nejdřív použijeme stejný postup jako v předchozím příkladu, ale pak ještě musíme zajistit, aby výsledná gramatika také generovala prázdné slovo a přitom zůstala nezkracující. Nejdřív vytvoříme pomocnou gramatiku G', která nemá žádná e-pravidla, její jazyk je L(G') = L(G) - {e}. G' = ({S,A}, {a,b,c}, P', S) S —> aaS | aa \ bbA \ bb A —> cSbSc | cbSc \ cSbc \ cbc Přidáme nový neterminál (startovací symbol) a vytvoříme gramatiku, která již bude ekvivalentní původní gramatice. G" = ({S',S,A}, {a,b,c}, P", S') S' -> S\e S —> aaS\ aa \ bbA\ bb A —> cSbSc | cbSc \ cSbc \ cbc Derivace v gramatice G: S => aaS => aaaaS => aaaa Derivace v gramatice G": S' => S => aaS => aaaa 5.2 Vlastnosti bezkontextových gramatik 61 Příklad 5.6 - Někdy se může stát, že „simulací" e-pravidla vytvoříme další e-pravidlo. Pak je třeba postup provádět rekurzívně tak dlouho, dokud nejsou všechna e-pravidla odstraněna. G = ({S,A,B}, {a,b}, P, S) S —> b A | aS | bB \ a A -> baB | e B -> AA | 6 Po odstranění pravidla A —> e dostaneme tuto gramatiku: G' = ({5,A,5}, {a, b}, P', S) S -^bA\b\aS\bB\a A -> feaS B -> AA | A | e | b Odstraněním obou symbolů A v pravidle B —> vzniklo další e-pravidlo, které je také třeba odstranit: G" = ({S,A,B}, {a,b}, P", S) S -^bA\b\aS\bB\b\a A —> baB | 6a B -> AA I A I 6 Rekurze při řešení pravidel se zbavíme tak, že ji přeneseme jinam. Můžeme použít řešení podobné tomu z redukce gramatiky - vytvoříme (rekurzívně) množinu N£ všech neterminálů, které lze (třeba i po více než jednom kroku) přepsat na prázdné slovo e. V množině iV£)o bude pouze prázdný řetězec, tj. iV£)o = {e}. V dalších krocích do této množiny přidáváme neterminály, které lze přepsat na řetězec skládající se pouze ze symbolů, které byly do této množiny přidány v předchozích krocích, tj. Ne>i = A^_i U{XeN\X^a, ae A^_i}. Příklad 5.7 - Podle pravidel gramatiky G = ({S, A, B, C, D}, {a, b, c, d}, P, S) S —> aAa | aa A^BC\b B -> aC \cD\e C -> AAa | e D -> AAB | d vytvoříme tyto množiny: Ns,o = {e} N£:i = {B, C} podle B —> e, C —> e, prázdné slovo už nezařazujeme 62 Kapitola 5 Bezkontextové gramatiky jV£i2 = {B, C, A} podle A -> BC N£i3 = {5, C, A, Z?} podle D -> AA£ V dalším kroku již nelze další neterminál přidat (ostatně všechny už v množině jsou), proto N£ = N£,3 = {B, C, A, D}. Množiny použijeme takto: pokud je na pravé straně pravidla některý z neterminálů obsažených v množině N£, pak vytvoříme další pravidla se „simulovaným" použitím e-pravidel na tento neterminál, e-pravidla odstraníme. Postup je prakticky stejný jako předchozí, ale zpracování gramatiky již není třeba provádět rekurzívně (rekurze byla použita při generování množiny N£). Fialovou barvou jsou zvýrazněny neterminály obsažené v množině N£ (a tedy vytvoříme pravidlo, ve kterém je odstraníme), modrou barvou pak nová pravidla. S —> aAa | aa \ aa (vlastně máme dvě stejná pravidla, jedno může být odstraněno) A -> BC | C | B j b B —> aC | a | cD \ c C —> AAa | Aa \ a D -> AAB \AB\B\d Příklad 5.8 - Postup předvedený v předchozím příkladu použijeme na gramatiku z příkladu 5.6. G = ({S, A, B}, {a,b}, P, S) S —> b A | aS | bB \ a A -> baB | e B -> AA | b Opět rekurzívně vytvoříme množinu N£: Ns,o = {4 Ne,l = {A} N£j2 = {A,B} = N£j3 = N£ Vychází nám tato gramatika: G' = ({S, A, B}, {a,b}, P', S) S -^bA\b\aS\bB\b\a A —> baB | ba B —> AA\A\b Oproti původnímu řešení není třeba několikrát přepisovat pravidla gramatiky. 5.2 Vlastnosti bezkontextových gramatik 63 Úkol 5.3 - K následujícím gramatikám vytvořte ekvivalentní nezkracující gramatiky. = ({S,A,B}, {a, &}, P S) G3 = ({S,A,B}, {a,b}. , i3, 5) S - -> aSbA ab S - -> BAa aS e A - -> aAbA e A - B - -> bAbB | b B - -> j e G2 = ({S, A}, {0,1} G4 = {5,^,5}, {a, 6}, P S) S - 5151 | A | e S - -> AB BA b A - -> 0A0 | 1 A - -> aaA e B - ^ 1 65 1 a 5.2.3 Odstranění jednoduchých pravidel Jednoduchá pravidla jsou taková pravidla, na jejichž pravé straně máme jen jediný symbol, a to neterminál, například A —> B. Jednoduchá pravidla zbytečně prodlužují výpočet a v některých algoritmech mohou být překážkou při programování. Pokud tento typ pravidel chceme odstranit, můžeme jednoduše nahradit symbol na pravé straně jednoduchého pravidla celou množinou pravidel, na která se tento symbol přepisuje. Například pokud existují pravidla B —> a \ (3 | 7, pak jednoduché pravidlo A —> B nahradíme pravidly A —> a | /3 | 7 (v derivaci to bude znamenat zkrácení odvození o jeden krok - zpracování jednoduchého pravidla). Protože touto náhradou můžeme opět pro daný neterminál dostat jednoduché pravidlo, postup je rekurzivní a lze ho zjednodušit přenesením rekurze na množiny neterminálů podobně jako v předchozích postupech. Vytváříme množiny Na postupně pro všechny neterminály A G N, které inicializujeme jednoprvkovou množinou obsahující neterminál v označení množiny (tj. v tomto případě A). Jde o množiny neterminálů, jejichž pravidla se pomocí jednoduchých pravidel mají postupně připsat do množiny pravidel pro daný neterminál A. Příklad 5.9 - Odstraníme jednoduchá pravidla v následující gramatice: G = ({S,A,B,C}, {a,b}, P, S) S —> aBaj A A -> aA j B B -> 65 I AB\C I e C -> 6A I 6 64 Kapitola 5 Bezkontextové gramatiky Rekurzívně vytvoříme množiny N$, Na, Nb, Nc- Na začátku rekurze, v bázi, bude v dané množině pouze ten symbol, pro který množinu tvoříme, tj. například Ns,o = {S}. Ns,o = {S} NS,! = {S,A} (podle S -+ A) NS,2 = {S,A,B} (podle A ^ B) Ns,3 = {S, A, B, C} = NSA = Ns (podle B ^ C) NA,o = {A} NA,i = {A, B} (podle A -> B NA,2 = {A, B, C} = NA,3 = NA (podle B -+ C) NB,o = {B} NB,i = {B, C} = NB,2 = NA (podle B C) Nc,o = {C} = Nc,i = Nc Z gramatiky odstraníme všechna jednoduchá pravidla. Po jejich odstranění pak použijeme vytvořené množiny - pokud například pro neterminál A je ./v4 = {A, B, C}, pak v gramatice pro neterminál A použijeme všechna pravidla, která v původní gramatice byla pro neterminály A,B,C. G' = ({S,A,B,C}, {a,b}, P', S) S -> aBa \aA \ bB | AB | e | bA | b A -> aA j bB \ AB \ e \ bA\b B -> bB j AB j e j bA | b C -^bA\b Pokud nám vadí pouze jednoduchá pravidla samotná, předchozí postup je dostačující. Jestliže však je překážkou samotné chování jednoduchých pravidel (například prodlužování derivace), je třeba předem odstranit e-pravidla. Například v gramatice z příkladu 5.10 po odstranění jednoduchých pravidel existuje derivace S => AB => A => ..., kde nacházíme ekvivalent použití jednoduchého pravidla S —> A z původní gramatiky. Příklad 5.10 - Gramatiku z příkladu 5.10 předem upravíme - převedeme na nezkracující. Pak teprve odstraníme jednoduchá pravidla. G = ({S,A,B,C}, {a,b}, P, S) S —> aBaj A A-> aA\ B B -> 65 I AB\C I e C -> bA j 6 Po převodu na nezkracující gramatiku: Ne = {B,A,S} 5.2 Vlastnosti bezkontextových gramatik 65 G'= ({S,A,B,C}, {a,b}, P', S) S —> aBa | aa \ A | e A -> aA | a | 5 B->bB\b\AB\A\B\C C -^bA\b Pravidlo S —> e můžeme nechat, protože se 5 nevyskytuje na pravé straně žádného pravidla (není nutné vytvářet nový startovací symbol). Odstraníme jednoduchá pravidla: NS = {S,A,B,C} NA = {A, B, C} Nb = {B, A, C} (všimněte si rozdílu oproti podobné množině v příkladu 5.10) NC = {C} G" = ({S,A,B,C}, {a,b}, P", S) S —> aBa | aa \ aA \ a \ e \ aA \ a \ bB \ b \ AB \bA\b A-> aA\a\bB \ b\ AB \ bA\b B ->bB\b\ AB\aA\a\bA\b C -^bA\b Úkol 5.4 - Odstraňte jednoduchá pravidla z následujících gramatik: d = ({S, A, B}, {0,1}, P, S) G2 = ({S, A, B}, {a, b}, P, S) S -> 0A1 | B | e S -> aA \ bB | A A -> 1S | S | B A -> bAb | S | e 5 -> 1A I S I 0 5 aBa \ A\a 5.2.4 Gramatika bez cyklu a vlastní gramatika Gramatika bez cyklu je taková gramatika, kde neexistuje žádná derivace A =>+ A pro jakýkoliv neterminál A. Už z definice je zřejmé, jak gramatiku upravit, aby splňovala tuto vlastnost - stačí ji převést na nezkracující gramatiku (bez e-pravidel) a odstranit jednoduchá pravidla. Vlastní gramatika je gramatika bez cyklu, nezkracující a bez nadbytečných symbolů. Postup je tedy následující: • převedeme gramatiku na nezkracující, • odstraníme jednoduchá pravidla, • odstraníme nadbytečné symboly postupem, který již známe z redukce gramatiky. 66 Kapitola 5 Bezkontextové gramatiky 5.2.5 Levá a pravá rekurze Gramatika je rekurzivní zleva, pokud v ní existuje derivace A =>+ Aa, gramatika je rekurzívní zprava, pokud v ní existuje derivace A =>+ a A, A je některý neterminál gramatiky, a je jakýkoliv řetězec z terminálů a neterminálů. Levá nebo pravá rekurze nám může bránit v některých dalších úpravách a nebo v naprogramování postupu popsaného gramatikou. Obvykle nám vadí jen levá a nebo jen pravá rekurze, proto jejich odstranění řešíme jednoduše převodem na tu, která nám nevadí. Při odstraňování rekurze vycházíme z toho, že k témuž řetězci lze dojít více různými způsoby. Ukážeme si odstranění přímé rekurze, jejíž existence je patrná přímo z pravidla. Příklad 5.11 - Následující gramatiku zbavíme přímé levé rekurze. G = ({S,A,B}, {a,b,c}, P, S) S —> aAb|b A —> Aa \ bB \ ab B —> Ba | Bb | ca Levá rekurze je v pravidlech A —> Aa a dále B —> Ba | Bb. Nejdřív vyřešíme první z těchto pravidel - pro neterminál A. Množinu pravidel A —> Aa | bB | ab nahradíme jinou množinou, která generuje tentýž řetězec. Jak může vypadat derivace z neterminálů A? A => Aa => Aaa => Aaaa =>* AáL => bBáL (generujeme zprava doleva, a to nejdřív rekurzívním pravidlem, rekurze je pak ukončena vlevo některým nerekurzívním pravidlem). Stejný řetězec lze generovat pravou rekurzí, a to přidáním nového neterminálů a úpravou pravidel (původní pravidla jsou A —> Aa \ bB \ ab): A -> b B A' | abA' \ bB\ab A' -> a A' | a Derivace ze symbolu A pak vypadá následovně: A => b B A' => bBaA' => bBaaA' =>* bBa^Ä => bBď Zbývá upravit pravidla pro neterminál B - B —> Ba | Bb | ca, nahradíme je pravidly B —> caB' | ca B' -> aB' \bB' \a\b Vytvořili jsme tedy ekvivalentní gramatiku bez přímé levé rekurze: G' = ({S,A,A',B,B'}, {a,b,c}, P', S) S —> aAb|b A -> b B A' | abA' \ bB\ab A' -> a A' | a B —> caB' | ca B' aB' \ bB' \a\b 5.2 Vlastnosti bezkontextových gramatik 67 Uvedený postup je použitelný pouze na vlastní gramatiku (tj. gramatiku bez cyklu, nezkracující, bez nadbytečných symbolů). Gramatika z předchozího příkladu je vlastní, proto nebylo třeba ji předem upravovat. Příklad 5.12 - Odstraníme přímou levou rekurzi v následující gramatice: G = ({S, A, B}, {a,b,c}, P, S) S -> bAa | c | A A-> Ba\b\ Abb B —> aBb | Bbc \ca\e Tato gramatika není vlastní. Je třeba nejdřív převést ji na nezkracující, odstranit jednoduchá pravidla a teprve potom můžeme odstranit levou rekurzi. 1. Odstraníme e-pravidla (resp. jediné, B —> e): G' = ({S,A,B}, {a,b,c}, P', S) S -> bAa | c | A A -> Ba | a \ b \ Abb B —> aBb | ab \ Bbc \ bc\ ca 2. Odstraníme jednoduché pravidlo S —> A: G" = ({S,A,B}, {a,b,c}, P", S) S —> bAa | c | Ba \ a \ b \ Abb A -> Ba | a \ b \ Abb B —> aBb | a6 | Bbc \ bc\ ca 3. Odstraníme přímou levou rekurzi. Pravidla A —> 5a | a | 6 | Abb nahradíme pravidly A -> SaA' | aA' | b A' \ Ba \ a | b A' -> 66A' | 66 Dále pravidla i? —> ai36 | a6 | i36c | 6c | ca nahradíme pravidly B -> aSĎP/ | «65' | aS' | |6cB' | caS' | aBb \ab\bc\ca B' -> 6CjB' | 6c Vytvořili jsme tuto gramatiku: G"' = ({S,A,A',B,B'}, {a,b,c}, P'", S) S —> 6Aa | c | i3a | a | 6 | A66 A -> SaA' | aA' | 6A' | fia | a | 6 A' -> 66A' | 66 B -> aBbB' | abB' \ aB' \ \bcB' \ caB' \ aBb \ab\bc\ca B' -> bcB' I 6c 68 Kapitola 5 Bezkontextové gramatiky Příklad 5.13 - Odstraníme přímou pravou rekurzi v této gramatice: G = ({S,A,B}, {a,b,c}, P, S) S -> aAb | AB A —> abA | c | Sc B ->bbB \cB\a Jde o vlastní gramatiku, nemusíme ji předem do tohoto tvaru upravovat. Postupujeme stejně jako u odstranění levé rekurze, jen zaměníme levou a pravou stranu. Přidáme nové neterminály a upravíme pravidla. Z neterminálu A může být například tato derivace: A abA ababA =4>* (abýA (abfc Pravidla A —> abA \ c \ Sc nahradíme pravidly A -> A'c | A'Sc \c\Sc A' -> A'ab I ab Derivace z neterminálu A se změní: A=> Nc=> A'abc => A'ababc =>* A'^abf^c (abýc Vygenerovaný řetězec je tentýž, ale zatímco u pravé rekurze byl generován zleva doprava, u levé rekurze je generován opačně - zprava doleva. Podobně upravíme pravidla B —> bbB | cB | a: B —> B'a | a B' -> £'66 | B'c | 66 | c Vychází nám tato gramatika: G' = ({S,A,A',B,B'}, {a,b,c}, P', S) S -> aAb | A£ A -> A'c | A'Sc | c j Sc A' -> A'a6 | a6 B —> iř>'a | a B' -> £'66 I B'c I 66 I c Rekurze může být také nepřímá, například v pravidlech A —> i36a | a B -> Aa6 | 6 Levou rekurzi, včetně nepřímé, odstraníme tak, že pravidla převedeme do tvaru, kdy pravá strana pravidla začíná neterminálem pouze za přesně určených okolností. Postup: 1. Stanovíme pořadí neterminálu. Můžeme si je například označit indexy, přejmenovat nebo jednoduše určit jejich pořadí. Nechť pořadí neterminálu je (Ai, A2,..., An). 5.2 Vlastnosti bezkontextových gramatik 69 Účelem algoritmu je upravit pravidla tak, aby mohla začínat pouze neterminály s vyšším indexem než je index přepisovaného neterminálu. Tím zcela odstraníme levou rekurzi. 2. Pro neterminály Aí,Aj, 1 < i, j < n postupně transformujeme pravidla. Pro první krok stanovíme i = l,j = 1. • Pokud j < i a existuje pravidlo Ai —> Aja, kde a je jakýkoliv řetězec (tj. pravidlo pro Ai začíná neterminálem Aj), pak symbol A j v pravidle nahradíme postupně všemi pravými stranami pravidel pro Aj, například Ai -> AjabB Aj -> bDA-ia | CAjd První z uvedenených pravidel nahradíme pravidly Ai —> bdAiddbB \ CAjddbB. Provedeme j = j + 1. • Pokud j = i, pak odstraníme přímou levou rekurzi podle postupu, který už známe. Provedeme j = j + 1. • Pokud j > i, provedeme i = i + 1, j = 1. 3. Bod 2 postupu provedeme pro všechna i, 1 < i < n. Aby byl postup použitelný, musí být uplatněn pouze na vlastní gramatiku. Postup pro pravou rekurzi je obdobný, jen zaměníme levou za pravou stranu. Příklad 5.14 - Odstraníme levou rekurzi v následující gramatice: G = ({S,A,B}, {a,b,c}, P, S) S -> aA\ AB \b A —> SBa|a B -> Bb\ Aa\c Přímá levá rekurze je zde jen v jednom pravidle, ale nepřímá rekurze se týká více pravidel. Gramatika je vlastní, není třeba ji do tohoto tvaru upravovat. Stanovíme pořadí neterminálu: (A1,A2, A3) = (S, A, B). • i = 1, j = 1 : není třeba upravovat, pravidla pro S neobsahují přímou rekurzi. • i = 2, j = 1 : jedno z pravidel pro A začíná neterminálem s „nižším indexem", S; upravíme: A -> aABa \ ABBa \ bBa \ a • i = 2, j = 2: řešíme přímou rekurzi (protože i = j): A -> aABaÄ \ bBaA' \ a A' \ aABa \ bBa \ a A' -> BBaA' I BBa 70 Kapitola 5 Bezkontextové gramatiky • i = 3, j = 1 : žádné z pravidel pro 5 nezačíná symbolem S • i = 3, j = 2 : změna se týká druhého pravidla pro symbol B (začíná symbolem A, jehož index je 2). Při nahrazení symbolu A v tomto pravidle použijeme již upravená pravidla pro A: B —> Bb | aABaA'a \ bBaA'a \ aA'a \ aABaa \ bBaa \ aa \ c • i = 3, j = 3 : odstraníme přímou rekurzi: B -> aABoA'aS' | bBaA'aB' \ aA'aB' \ aABaaB' \ bBaaB' \ aaB' \ cB' aABaA'a \ bBaA'a \ aA'a \ aABaa \ bBaa \ aa \ c B' -> 65' | 6 Celá gramatika bez levé rekurze: G' = ({S, A, A', B, B'}, {a,b,c}, P', S) S -> aA\ AB | 6 A -> aABaA' \ bBaA' \ aA' \ aABa \ bBa \ a A' -> BBaA' | 55a 5 aA5aA'a5' | bBaA'aB' | aA'a5' | aABaaB' \ bBaaB' | aa5' | c5' aABaA'a \ bBaA'a \ aA'a \ aABaa \ bBaa \ aa \ c B' -> 65' I 6 Odstraněním přímé rekurze rozšiřujeme množinu neterminálů, proto je nutné dynamicky upravovat také nadefinovanou posloupnost neterminálů určující pořadí. Neterminály s pravidly které takto vytvoříme, je třeba zahrnout do algoritmu. Příklad 5.15 - Odstraníme levou rekurzi v následující gramatice: G = ({S, A, B}, {a,b}, P, S) S ^ aA j 65 A -> BaA | a6 5 -> BaA | 6 • i = 1, j = 1 : není třeba upravovat, pravidla pro S* neobsahují přímou rekurzi. • i = 2, j = 1,2 : není třeba upravovat, pravidla pro A nezačínají symboly S a A. • i = 3, j = 1, 2 : není třeba upravovat, pravidla pro 5 nezačínají symboly S a A. • i = 3, j = 3 : odstraníme přímou rekurzi. 5 -> 65' | 6 5' -> Aa5' I Aa 5.3 Normální formy bezkontextových gramatik 71 Měníme posloupnost: (Ai, A2, A3, AA = (S, A, 5, B') • i = 4, j = 1 : není třeba upravovat, pravidla pro B' nezačínají symbolem S. • i = 4, j = 2 : B' —> BaAaB' \ abaB' \ BaAa \ aba • i = 4, j = 3 : B' —> bB'aAaB' \ baAaB' \ abaB' \ bB'aAa \ baAa \ aba • i = 4, j = 4 : není třeba upravovat. Výsledná gramatika: = ({S, A, B, B'}, {a,b}, P', S) S -^aA\bB A -> BaA | ab B -^bB' \ b B' -> AaB' | Aa B' —> bB'aAaB' I baAaB' I abaB' I bB'aAa I 6aAa I a&a Úkol 5.5 - 1. Odstraňte levou rekurzi v těchto gramatikách (zvažte, zda není třeba gramatiku předem upravit): d = ({S, A, B}, {a, b, c}, P, S) G2 = ({S, A, B}, {a, b}, P, S) S -> aAB \b\SB\e S -> AB \ BA A^bA\ Aac \ AB \ a A —> ABbA \ b A | e B -> 56A j c S -> SA I a j 56A 2. Odstraňte pravou rekurzi v těchto gramatikách (příp. gramatiku předem upravte): 5.3 Normálni formy bezkontextových gramatik Normálni formy (čehokoliv) slouží k usnadnění porovnávání a případných dalších úprav. V případě bezkontextových gramatik lze využít Chomského normální formu (CNF) a Gre-ibachovu normální formu (GNF). G1 = ({S,A,B}, {0,1}, P S) S -> 11A I 015 I e A —> 11A I 501 I 10 B -> 015 I 00A5 I 1A1 I 01 G2 = ({1S,A,5}, {a, b}, P, S) S -> oA6 j a&5 | AS*A A -> 6 A j 5 j e 5 —> bbB I a6A5 I a&6 72 Kapitola 5 Bezkontextové gramatiky 5.3.1 Chomského normálni forma Při převodu gramatiky do Chomského normálni formy je třeba, aby pravidla byla ve tvaru • A —> BC, tedy na pravé straně dva neterminály, • A —> a, tedy na pravé straně jeden terminál, a nebo • S —> e (S je startovací symbol gramatiky), a to pouze v případě, že S se nevyskytuje na pravé straně žádného pravidla (tj. toto pravidlo lze využít pouze na začátku derivace). Postupujeme takto: 1. Převedeme gramatiku do tvaru vlastní gramatiky (tj. převod na nezkracující gramatiku, odstraníme jednoduchá pravidla, odstraníme nadbytečné neterminály). 2. Pravidla, která mají na pravé straně jen jeden symbol (půjde vždy o terminál, protože jednoduchá pravidla jsme již odstranili) necháme - odpovídají požadavkům na normální formu; dále zpracováváme jen pravidla, jejichž pravá strana má délku alespoň 2. 3. Pro každé pravidlo A —> a, kde \a\ > 1, provedeme tyto úpravy: • každý terminál a v řetězci a nahradíme novým (nově vytvořeným) neterminá-lem Na (podle dolního indexu poznáme, který terminál byl nahrazen), takže například pravidlo A —> BaAbca zaměníme za pravidlo A —> BNaAN^NcNa, • vytvoříme nová pravidla Na —> a pro každý terminál a. 4. Délku pravých stran všech pravidel omezíme na nejvýše 2 takto: pro každé pravidlo A —> B1B2B3 ... Bn, n > 2, vytvoříme množinu pravidel A -> £1X1 X\ —> B2X2 Xn-3 —> Xn-2Bn-2 Xn-2 —> Bn-iBn Například pravidlo A —> BCDEF nahradíme množinou pravidel A -> BXi Xi —> CX2 x2 X3 —> EF Neterminály Xi,... ,Xn-2, které používáme při propojení generování pravé strany původního pravidla, musí být nové, tedy různé pro různá pravidla, která takto upravujeme. 5.3 Normální formy bezkontextových gramatik 73 Příklad 5.16 - Následující gramatiku převedeme do Chomského normální formy: G = ({S,A,B}, {a,b,c}, P, S) S —> aBAc | c A -> Ab | e 5 -> 65 | AS | a Tato gramatika není vlastní. Nejdřív odstraníme e-pravidlo A —> e. 5 —> aBAc | a5c | c A -> A6 | 6 5 -> 65 | AS | S | a Jedno z pravidel je jednoduché (5 —> S), to je třeba odstranit: S —> aBAc | a5c | c A -> A6 | 6 5 -> 65 | AS | a5Ac | aBc \ c \ a Všechna pravidla, jejichž pravá strana je dlouhá alespoň 2 symboly, upravíme - terminály nahradíme příslušnými neterminály: S ^ NaBANc | NaBNc | c A -> ANb | 6 5 -> NbB | AS | NaBANc | 7Va57Vc | c | a Na^a Nb^b Nc^c Všechna pravidla s pravou stranou delší než 2 zkrátíme a získáme tuto gramatiku: GCnf = ({S,A,B, Na,Nb,Nc, X1,X2,X3,X4,X5,X6}, {a,b,c}, P', S) S -> NaXx | NaX3 | c 5 -> 7V65 | AS* | 7VaX4 | 7VaX6 | c | a Na-> a Xi -> BX2 XA -> 5X5 JVb -> 6 X2 -> A7VC Xb -> A7VC 7VC -> c X3 ^ 57VC X6 ^ 57VC A -> A7V6 | 6 Jedna z derivací v původní gramatice G: S =>• aBAc =>• aaAc =>• aaAbc =>• aa6c Derivace stejného slova v gramatice G" (po předběžné úpravě): S =>• aBAc =>• aaAc =>• aa6c Obdobně ve výsledné gramatice Gcnf-S =>- NaXi =>- aXi =>- aBX2 =>- aBANc =>- aBAc =>- aaAc =>- aabc 74 Kapitola 5 Bezkontextové gramatiky Úkol 5.6 - Následující gramatiky převeďte do Chomského normálni formy: = {{S,A,B}, {a,b}, P S) G3 = {{E,F,G}, {a,b}, P, 5) S - -> AaB ba aA E - -> aaF \GF\b A - -> aAB aAb ab F - -> aFaa \ e B - -> bBASb | b G - -> aFGbG | e G2 = ({S,A,B}, {0,1}, P S) GA = ({5, A, 5}, {0,1}, 5 5) S - ■+ OB | 1A | e S - ■* 01A50 | 105A1 | e A - -> 10A1 | AB | e A - -> 1A51A51 | 111 B - -> A1B01 1 151 1 0 B - -> 05 1 0 5.3.2 Greibachova normálni forma Gramatika je v Greibachově normální formě, pokud všechna pravidla této gramatiky jsou v jednom z těchto tvarů: • A —> aB\B2 ... Bn, n > 0, tedy na pravé straně je vždy jeden terminál a následují pouze neterminály (nemusí být žádný neterminál), • S —> e (5 je startovací symbol gramatiky), a to pouze v případě, že S se nevyskytuje na pravé straně žádného pravidla (tj. toto pravidlo lze využít pouze na začátku derivace). Podobně jako u převodu na Chomského normální tvar, i zde budeme gramatiku předem upravovat. Možnost existence e-pravidla pouze pro startovací symbol znamená nutnost převést gramatiku na nezkracující. Dále odstraníme jednoduchá pravidla a případně také nadbytečné symboly. Kromě toho je zde požadavek na terminálni symbol na začátku pravidla. Pokud pravidlo začíná neterminálem, logickým postupem by bylo dosazovat za tento neterminál postupně všechna pravidla, na který lze neterminál přepsat, a to rekurzívně tak dlouho, dokud nezískáme pravidlo začínající terminálem. Pokud je však v gramatice levá rekurze, dosazovali bychom do nekonečna, proto je třeba předem odstranit levou rekurzi. Celý postup je následující: 1. Převedeme gramatiku do tvaru vlastní gramatiky (převod na nezkracující, odstranění jednoduchých pravidel, odstranění nadbytečných symbolů). 2. Odstraníme levou rekurzi. Pokud jsme jejím odstraněním vytvořili e-pravidla nebo jednoduchá pravidla, opakujeme bod 1. 5.3 Normální formy bezkontextových gramatik 75 3. Pravidla, jejichž pravá strana má délku 1, již vyhovují požadavkům na normální formu (a také případné e-pravidlo pro startovací symbol). 4. Pravidla, jejichž pravá strana má délku > 2, dále zpracováváme: • pokud pravidlo začíná neterminálem, dosadíme za tento neterminál všechna pravidla, která ho přepisují, tj. například pravidlo A —> BbAa při existenci pravidel B —> a | (3 | 7 nahradíme pravidly A —> abAa | /3bAa \ ^bAa, • to provádíme rekurzívně tak dlouho, dokud všechna pravidla nezačínají termi-nálním symbolem, • Všechny terminálni symboly a na pravých stranách pravidel, kromě prvního terminálu v řetězci, nahradíme příslušnými symboly Na (podobně jako při převodu na Chomského normální tvar). 5. Vytvoříme nová pravidla Na —> a pro všechny terminály a. Příklad 5.17 - Následující gramatiku převedeme do Greibachovy normální formy. G = ({S,A,B,C}, {a,b,c}, P, S) S —> aBba \ baA | e A -> BaAB \ bb\e B —> CBab | abc C —> bCb | a Sestrojíme ekvivalentní vlastní gramatiku - odstraníme e-pravidla. Podle množiny N£ = {S, A} je zřejmé, že existují pouze dvě e-pravidla. Jedno z nich je pro startovací symbol, který se však nevyskytuje na pravé straně žádného pravidla. Proto není nutné přidávat nový neterminál a měnit startovací symbol gramatiky. G' = ({S,A,B,C}, {a,b,c}, P', S) S —> aBba \ baA \ ba \ e A -> BaAB | BaB \ bb B —> CBab | abc C —> bCb | a Při převodu do Greibachovy normální formy nejdřív zajistíme, aby nejlevějším symbolem v pravých stranách pravidel byl vždy terminál. To provedeme přepsáním toho neterminálu, který je na začátku upravovaného řetězce. Pravidlo A —> BaAB nahradíme těmito pravidly: A -> CBabaAB \ abcaAB Jedno z pravidel opět začíná neterminálem, tedy úpravu provedeme znovu: A -> bCbBabaAB I aBabaAB I abcaAB 76 Kapitola 5 Bezkontextové gramatiky Pravidlo A —> BaB nahradíme pravidly A —> CBabaB \ abcaB Po druhé úpravě: A —> bCbBabaB \ aBabaB \ abcaB Pravidlo B —> C Bab nahradíme pravidly B -> bCbBab \ aBab V této fázi jsme získali následující pravidla: S —> aBba \ baA \ ba | e A —> bCbBabaAB \ aBabaAB \ abcaAB \ bCbBabaB \ aBabaB \ abcaB \ bb B —> bCbBab \ aBab \ abc C —> 6C6 | a Zbývá splnit podmínku, podle které v pravých stranách pravidel jsou všechny symboly kromě nejlevějšího neterminální. Ggnf = ({S,A,B,C,Na,Nb,Nc}, {a,b,c}, P", S) S -> aBNbNa | bNaA \ bNa | e A -> bCNbBNaNbNaAB | aBNaNbNaAB \ aNbNcNaAB | bCNbBNaNbNaB aBNaNbNaB \ aNbNcNaB | 67V6 B -> bCNbBNaNb | aBNaNb | a7V67Vc C -> 6C7V6 | a A^a -> a Příklad 5.18 - Následující gramatiku převedeme do Greibachovy normální formy. G = ({S,A,B}, {a,b}, P, S) S -> aA\ AB \b A —> SBa|a B Bb | a V gramatice nejsou žádná e-pravidla ani jednoduchá pravidla, aleje tu levá rekurze, kterou musíme předem odstranit. Přímá rekurze je v jednom z pravidel pro B, nepřímá rekurze je v pravidlech pro neterminály S a A. Budeme postupovat podle algoritmu popsaného na straně 68. Stanovíme pořadí neterminálů (Ai, A2, A3) = (S, A, B). • i = 1, j = 1 : není třeba upravovat, pravidla pro S neobsahují přímou rekurzi. • i = 2, j = 1 : dosadíme pravé strany pravidel pro S do prvního z pravidel pro neterminál A: A -> aABa I ABBa I 6Pa I a 5.3 Normální formy bezkontextových gramatik 77 • i = 2, j = 2 : odstraníme přímou rekurzi: A -> aABaÄ \ bBaA' \ a A' \ aABa \ bBa \ a A' -> BBaA' | BBa • i = 3, j = 1, j = 2 : beze změny. • i = 3, j = 3 : odstraníme přímou rekurzi: B -> aB' \a B' -> 65' | 6 Upravená gramatika bez levé rekurze (také nepřímé) je následující: G' = ({S,A,A',B,B'}, {a,b}, P', S) S -> aA\ AB | 6 A -> aABaA' \ bBaA' \ a A' \ aABa \ bBa \ a A' BBaA' | BBa B —> aB' | a 5' -> 65' | 6 Teď už můžeme gramatiku převést do Greibachovy normální formy. Nejdřív zajistíme, aby pravé strany pravidel začínaly vždy terminálním symbolem. S -> aA | aABaA'5 | bBaA'B \ aA'B | aABaB \ bBaB \aB\b A -> aABaA' \ bBaA' \ aA' \ aABa \ bBa \ a A' aB'BaA' \ aBaA' \ aB'Ba \ aBa B —> aB' | a B' -> 65' | 6 V dalším kroku všechny terminály na pravých stranách pravidel, kromě nejlevějšího, zaměníme za příslušné neterminální symboly. GGNF = ({S,A,A',B,B',Na}, {a,b}, P", S) S -> aA | aA57VaA'5 | bBNaA'B | aA'5 | aABNaB | 657Va5 | a5 | 6 A -> aABNaA' \ bBNaA' \ aA' | aABNa \ bBNa \ a A' -> aB'BNaA' \ aBNaA' \ aB'BNa \ aBNa B —> a5' | a 5' -> 65' I 6 Úkol 5.7 - Převeďte následující gramatiky do Greibachovy normální formy.