Faculty of Informatics Masaryk University Brno Cvičení k předmětům IB005 Formální jazyky a automaty a IB102 Automaty a gramatiky poslední modifikace 3. listopadu 2017 Tato sbírka byla vytvořena z příkladů ke cvičení z předmětu Formální jazyky a automaty I, které byly původně připraveny Ivanou Černou. Na opravě chyb a doplnění příkladů se podílelo mnoho studentů a cvičící předmětů IB005 a IB102 Jiří Barnat, Vojtěch Řehák a Jan Strejček. Formální jazyky, regulární gramatiky 1.1 Jsou dány jazyky L1; L2 nad abecedou {x,y,z}, kde Lx = {xy, y,yx}, L2 = {y, z}. Vypočítejte: a) Li U L2 b) Lx n L2 c) Li ■ L2, L2 ■ L1 d) L°, L|, Li L2, L+ e) co — L'2 1.2 Vypočítejte: a) 0*, 0+, {£}+ b) 0U{e}, 0n{£}, 0nL, {e}nL c) 0 ■ {e}, 0 ■ L, {£} • {e}, {e} ■ L 1.3 Jsou dané jazyky L\, L2 C {a, 6, c, d}*, kde Li = {a, aa, ba}, L2 = {ba, abc, a, e}. a) Vypočítejte L\ U L2. b) Vypočítejte L\ n L2. c) Vypočítejte Li • L2. d) Rozhodněte, zda platí L\ ■ L2 = L2 • L\. e) Najděte slovo w G Li • L2 n L2 ■ Li. f) Rozhodněte, zda platí Li C L\ ■ L2. Pokud ano, platí tvrzení pro libovolnou dvojici jazyků L\, L2? Pro pokročilé: platí e G L2 Li C L\ ■ L2? g) Rozhodněte, zda platí • aabaabc G L\ • baaabc € L2 • ababc 6 L2 h) Popište co — L2 (komplement jazyka L2). 1.4 Buď L libovolný jazyk, rozhodněte zda platí: a) pro Vi G N platí V = {wi w G L} b) pro Vi G N platí w € U \w\ = i c) najděte jazyk, pro který oba výše uvedené vztahy platí 1.5 Porovnejte (slovně popište) jazyky a rozhodněte zda L\ = l4 • Li = {x,y,z}* • L2 = {.vy z}* . l3 = {xy ■ {Vy ■ {z}* . L4 = ({.r}* • {y}* ■ {z}*)* . L5 = ({x,y}*U{z}*)* 1 • Le = {x, y, z}* ■ {x} ■ {x, y, z}* 1.6 Porovnejte (slovně popište) jazyky a rozhodněte zda L\ = L3 • Li = {x, y, z}* • L2 = {x, y, z}+ . L3 = {x}* ■ {y}* ■ {z}* . U = {x}* ■ {y}2 ■ {z}* . L5 = ({x}* ■ {y}* ■ {z}*)* • L6 = {x, y, z}* ■ {x} ■ {x, y, z}* 1.7 Pomocí jazyků L\ = {a}, Ľž = {b} nad abecedou {a, b} a množinových operací sjednocení (U), průniku (n), konkatenace (•), iterace (*,+) a doplnku (co— ) vyjádřete jazyk, obsahující všechna slova, která a b c d e f g 1.8 Pro a b c d e f obsahují alespoň 2 znaky a mají sudou délku začínají znakem a a končí znakem b začínají a končí stejným znakem obsahují podslovo aba splňují b) a c) nesplňují b) libovolné jazyky L\, L2, L3 dokažte, zda platí, nebo neplatí: Li C Li ■ L2 (Li U L2) • L3 = (Li • L3) U (L2 • L3) (Li n L2) • L3 = (Li • L3) n (L2 • L3) pro Vi e N platí L\ ■ L\ = (Li • L2)J L\ UL?2 = (L1UL2)* L1- L1= L1 (LiUL2)* = (ií -L2-(ii)*)* 1.9 Jaký jazyk generuje gramatika G a jakého je typu? a) G = ({S, A, B, C},{a, b, c, d},P, S), kde P = { S ■> aSb cAd cA - ■> ŕiB Ca, Bd - ■> 5& A Cad - -> a& e } b) G = ({S, A},{b, c, a},P, S), kde p = { S -> &5 I oS* I aA, i ^ I 6A I a \ b \ c } 1.10 Jaký jazyk generuje následující gramatika? Diskutujte vhodné označení neterminálu ( aA &B A - ■> aS &C*, B - ■> aC 65, C - ■> aB } 1.11 Navrhněte regulární gramatiky pro následující jazyky: a) L = {a, b, c, d}* 2 b) L = {a, b, c d}1 {a, b, c, d}*;i = 2,10,100 c) L = {w w G {a, b}*, \w\ > 3} d) L = {w w e {«,&}*, H = 3fc, k > 0} e) L = {w w G {a, b, c}*, w obsahuje podslovo abb} f) L = {w ■ wR w e {a, b}*} g) L = {w w G {a, b, c}*, první 3 znaky w = poslední 3 znaky w} h) L = {w w G {a, b, c}*, w neobsahuje podslovo abb} i) L = {w w e {a, b, c}*, #a(w) = 2k, #b(w) = 31+1, k, l > 0} j) L = {w w G {0,1,..., 9}*, w je zápis přir. čísla dělitelného 5} k) L = {w w G {0,1,..., 9}*, w je zápis přir. čísla dělitelného 3} 1) L = {w w G {0,1,..., 9}*, w je zápis přir. čísla dělitelného 25} 3 Deterministické konečné automaty, pumping lemma 2.1 Je dán následující konečný automat: A = ({qo, qi,q2, Qa}, {a, b}, ô, qo, {la}) S(q0,a) = q1 ô(q0,b) = q2 ô(q1,á) = q3 S(q1,b) = q1 <%2,a) = 92 S(q2,b) = q2 S(qa,a) = qi S(q3,b) = q2 a) Uveďte jinou formu zápisu automatu. b) Popište jazyk akceptovaný konečným automatem A. c) Diskutujte variantu konečného automatu, kde F = {q$, q2}; <5(t/3, a) = qo 2.2 Konstruujte deterministické FA, které rozpoznávají následující množiny a) {a, b, c}5 • {a, b, c}* b) {w w e {«}*; \w\ = 2k nebo \w\ = 71; k,l>0} c) {w w e {a,b}*; #a(w) = 3k;k > 0} d) {w w G {a, b}*; w obsahuje podslovo abbab} e) {w w G {a, b}*; w obsahuje podslovo ababb} f) {w w G {a, b}*; w neobsahuje podslovo abbab} g) {a, b}* ■ ({c, d} U ({d} ■ {a, b}* ■ {c})) • {a, b}+ h) ({a} U {b} ■ {a} ■ {b}* ■ {a} ■ {b})* 2.3 Konstruujte deterministické FA pro následující jazyk nad abecedou {a, b, c, d} a) L = {a, b}* ■ {c} • {aa, b}* ■ {d}+ b) L = {w | w G {a, b, c}*, w neobsahuje podslovo babb} c) L = {a, b}* ■ ({cd}+ ■ {d} ■ {a, b}* ■ {c}) • {a, b}+ 2.4 Pomocí množin {a}, {b}, {c}, {d} a množinových operací sjednocení (U), průniku (n), konkatenace (•), iterace (*,+) a doplnku (co—) vyjádřete jazyk akceptovaný automatem: 6 4 2.5 Co akceptuje následující automat? (#a(w) = je špatná odpověď) 2.6 Pomocí věty o vkládání dokažte, že jazyk L není regulární: a) L = {cřb> \j>i>l} b) L = {w | w e {a, b}*; #a(w) = #6(w)} c) L = {w ■ wR | w G {a, b}*} d) L = {an | n = 2J; i > 0} e) L = {ďb> \ i,j > 0} f) L = {a™&(™!)2 n > 0} g) L = {cia:ibk j < k; i, j, k e N} 2.7 O každém z následujících jazyků nad abecedou T, = {a, b, c} rozhodnete, zda je regulární, a vaše tvrzení dokažte. a) {uv u, v G {a, b}*, \u\ < \v\} b) {ucv u, v G {a, b}*, |«| < \v\} 2.8 Pro pokročilé: Zkonstruujte konečný automat A rozpoznávající jazyk L = {a}* ■ {b}. Dokažte, že automat rozpoznává zadaný jazyk, tedy že L(A) = L. 2.9 Konstruujte deterministické FA pro všechny regulární jazyky příkladu 1.11. 5 Minimalizace DFA, nedeterministické FA, (Myhillova-)Nerodova věta 3.1 Pro následující konečné automaty zadané tabulkou: • ověřte, že všechny stavy jsou dosažitelné • zkonstruujte minimální automat • minimální automat zapište v kanonickém tvaru a) a b -> 1 2 3 2 5 2 3 3 5 <- 4 12 2 <- 5 7 8 6 4 9 7 12 11 8 4 6 9 10 8 <- 10 3 2 <- 11 12 6 12 3 10 b) a b o 1 3 2 2 6 4 3 3 5 <- 4 4 2 5 10 8 6 6 7 <- 7 7 5 <- 8 8 2 <- 9 11 2 10 10 9 <- 11 11 5 3.2 Odstraňte nedosažitelné stavy z DFA zadaného tabulkou vlevo a minimalizujte ho a převeďte do kanonického tvaru. Poté ověřte, zdaje výsledný automat ekvivalentní s automatem zadaným tabulkou vpravo. a) a & -> 1 5 2 2 2 8 3 2 7 <- 4 9 4 5 2 1 6 2 5 <- 7 8 6 8 2 4 9 8 9 a b -> 1 4 2 2 2 5 3 3 6 4 4 2 <- 5 5 3 <- 6 6 2 6 b) a b 1 3 1 -> 2 9 4 3 - 1 <- 4 9 4 5 8 5 6 5 4 <- 7 6 9 8 11 - 9 7 9 10 12 3 11 8 1 12 - 10 a b A B A <- B C A C D E D D D -> E A E 3.3 Overte, zda DFA z príkladu 3.1 a) je ekvivalentní s následujícím DFA zadaným tabulkou a b A A C -> B D A <- C D A D C D 3.4 Navrhnete nedeterministické konečné automaty pro následující jazyky: a) L = {w G {a, b, c, d}* \ w obsahuje podslovo abbc nebo bba nebo aba} b) L = {w G {a, 6, c}* | w obsahuje podslovo abbc nebo acbca nebo bcabb} c) L = {w G {a, 6, c, eí}* | w končí řetězcem aaaa} d) L = {w G {0,1}* | w má čtvrtý symbol od konce 1} e) L = {w G {0,1}* | w končí řetězcem 01011} f) L=(({0}*-{l})U({0}+-{l}*-{0})*)* g) L=(({0}-{0}-{0}*)U({l}.{l}.{l}*))* 3.5 K daným nedeterministickým FA zkonstrujte deterministické FA. a) a b c a b c -> 1 {2,3} {3,4} {1} -> 1 {1,2} {1} 0 <- 2 {3} {4} {2} <- 2 0 {3} {1} 3 {1,2,3} {1} {3,4} 3 0 0 {1,4} 4 {1} {1} {3,4} 4 {5} 0 0 5 0 {6} 0 6 {7} 0 0 <- 7 0 0 0 3.6 Popište jazyk akceptovaný automatem: 3.7 Kolik různých jazyků rozhodují automaty s jedním nebo se dvěma stavy nad abecedou {x} nebo {a 3.8 Dokažte, že neexistuje (totální deterministický) automat se 4 stavy, který akceptuje jazyk: a) L = {w e {a, b}* | \w\ > 4} 7 b) L = {w e {a, b}* | \w\ = 5fc, k e N0} 3.9 Najděte a formálne popište alespoň dvě relace ~ C {a, b}* x {a, b}* splňující podmínky Nerodovy věty pro j azyk L = {w | w G {a, b}*, w obsahuje podslovo abb}. Určete indexy těchto relací. 3.10 Pomocí Nerodovy věty a posléze pomocí Myhillovy-Nerodovy věty dokažte, že není regulární: a) L = {an | n = 2\ i > 0} b) L = {anbm n < m < 2n, n, m > 0} c) L = {wwR | w G {a, b}+} d) L = {aiV\iŕJ; i,j>0} 3.11 Pomocí MN věty dokažte, že je regulárni: • L = {w e {a, b}* | #a(w) = 3fc, k > 0} 3.12 Každý jazyk jednoznačně určuje relaci ~£ předpisem u ~£ v právě když pro každé w platí uw Gítt vw G L. Určete index této relace pro jazyky: a) L = {a}* ■ {b}* ■ {c}* b) L = {anbncn n > 0} 3.13 Nechť T, = {a, b}. Uvažte následující relace na množině T,*: a) u ~ v <^^> #a(w) mod 4 = #a(v) mod 4 b) u ~ « <^^> #a(w) mod 4 = #a(v) mod 4 nebo m i « končí na stejné písmeno c) m ~ v <^^> #a(w) mod 4 = #a(v) mod 4 a m i « končí na stejné písmeno (Prázdné slovo končí na stejné písmeno jako prázdné slovo, ale žádné neprázdné slovo na stejné písmeno nekončí.) U každé relace určete, zda je to ekvivalence. Pokud ano, určete její index a zda je pravou kongruencí. Pokud ano, nalezněte jazyk L takový, že ~£ = ~. Nakonec nalezněte jazyk Ľ, který je sjednocením některých tříd rozkladu T,*/ ~, ale přitom ~£/ ^ ~. 8 Regulární gramatiky a výrazy <(=4> FA, čS-kroky, Kleeneho věta 4.1 Zkonstruujte ekvivalentní konečný automat k následující gramatice: G = ({S, A, C, B},{a, b, c},P, S), kde P= { s - aA bC a e, A - bB aA b c, B - aB bC aC cA C - -> a b aA bB } 4.2 Zkonstruujte ekvivalentní konečný automat k následující gramatice: G = ({S, X, Y, Z},{a, b, c},P, S), kde P= { s - aX bY x - bX bS, Y - bS cZ, Z - aS b 4.3 Zkonstruujte ekvivalentní regulárni gramatiku k automatu: 4.4 Zkonstruujte ekvivalentní regulárni gramatiku k automatu: a d 4.5 K danému automatu s e-kroky zkonstruujte ekvivalentní automat bez e-kroků. c d 4.6 K danému automatu s e-kroky zkonstruujte ekvivalentní automat bez e-kroků. a 9 4.7 K danému automatu s e-kroky zkonstruujte ekvivalentní automat bez e-kroků. a b c e -> 1 {1,2} 0 0 {2} 2 {5} {3,5} 0 0 3 0 {6} 0 0 4 0 {4} 0 {1,5} 5 {5} 0 {3} {6} <- 6 0 0 {3,6} {2} 4.8 K danému regulárnímu výrazu zkonstruujte ekvivalentní FA a) (ab)* (aa + bb)(a + ab)* b) ((a + b(a + c))* + (b + c))* c) (((a + b)* + c)* + d)* 4.9 K danému FA zkonstruujte ekvivalentní regulárni výraz 4.10 K danému FA zkonstruujte ekvivalentní regulárni výraz c 4.11 Pomocí regulárních výrazů popište násl. jazyky: a) L = {w G {a, b}* \ w končí na ab} b) L = {w e {a, b}* | = 2k,k> 0} c) L = {w G {a, b}* | w začíná a končí stejným symbolem } d) L = {w e {a, b}* | H =2k,k> 0} 4.12 Ukažte, jaký je vztah mezi třídou regulárních jazyků 1Z a nejmenší třídou a) Mi, která obsahuje všechny konečné jazyky a je uzavřená vzhledem k sjednocení, zřetězení a průniku (U, - , fl). b) M'2, která obsahuje všechny konečné jazyky a je uzavřená vzhledem k sjednocení, průniku a komplementu (U, n, co— ). c) M3, která obsahuje všechny konečné jazyky a je uzavřená vzhledem k sjednocení, průniku a mocnině (U, fl,"). 10 Uzáverové vlastnosti 1Z 5.1 Rozhodněte, zda platí: jsou-li jazyky Li, L2, L3,... regulární, pak i jazyk O i=l je regulárni jazyk. 5.2 Najděte takovou posloupnost regulárních jazyků L\, L2, L3,... aby jazyk 00 O i=l nebyl regulární. 5.3 Nechť L\, L2 jsou neregulární j azyky nad abecedou {a, b}. Dokažte nebo vyvraťte, zdaje či není regulární: a) Li n L2 b) Li U L2 c) Li \ L2 d) Li • L2 e) Lí f) co—Li 5.4 Nechť Li je regulární a L\ n L2 je neregulární jazyk. Platí, že jazyk L2 je nutně neregulární? 5.5 Platí následující implikace? a) L\ je regulární, L2 je neregulární => L\ n L2 je neregulární b) Li je regulární, L2 je neregulární =^> L\ n L2 je regulární c) L\ je regulární, L2 je neregulární => L\ \ L2 je neregulární d) Li je regulární, L2 je neregulární => L\ \ L2 je regulární e) Li je regulární, L2 je neregulární =^> L2 \ L\ je neregulární f) L\ je regulární, L2 je neregulární => L2 \ Li je regulární 5.6 Def: operace 0 rozšířeného sjednocení dvou jazyků takto: Li 0 L2 = {u ■ v I m, v e (Li U L2)} Dokažte, že jestliže jsou jazyky L\ a L2 regulární, pak i jazyk L\ 0 L2 je regulární. Dále najděte dva takové neregulární jazyky L\ a L2, aby jazyk L\ 0 L2 byl regulární. 5.7 Nechť L C S* je regulární jazyk. Dokažte, že jazyky jsou regulární: a) = {« I existuje íigS' takové, že u.v G L} b) L* = {w I existují x,y, z E E* takové, že y G L a w = a:í/,z} 11 5.8 Dokažte, že pro libovolný jazyk L a libovolný konečný jazyk K platí: a) L je regulární <^^> L \ K je regulární b) L je regulární <^^> L U K je regulární 5.9 Def: Homomorfismus h : T,* —> A* je daný předpisem: h(e) = e h(u.v) = h(u).h(v) pro všechny u, v € T,* Def: Nechť L je jazyk, pak h(L) = {w \ w = h(u), kde měL} Def: Inverzní Homomorfismus: h-^y) ={iGE* | h(x)=y} h-^L) = {x e £* e L} Příklad /i(a) = 01 h(b) = 011, pak • h(abb) = 01011011 • ^-1(0101011) = {aab} • /i-^OOlO) = 0 • pokud navíc h(c) = e pak /i—1 (01011) = L(c*ac*bc*) Ukažte, že 1Z je uzavřena na h,h~ľ. 5.10 Nechť je dána abeceda {a, b, c} a homomorfismus /i; h(a) = ac, h(b) = cb, h(c) = ca. Určete: • h(aabc), h(cbaa) • h~x (cccaaccb), h~x (accba) • h(L),L = {anbncn n > 0} 5.11 Nechť je dána abeceda {a, b, c} a homomorfismus h; h(a) = aa, h(b) = ba, h(c) = a. Určete: • h~x (aabaaabaa) . h(L), L = {we {a*, b*} | #a(w) = #b(w)} • h-^L), L={w e {a*} | \w\ = 2k,ke N} 5.12 Dokažte nebo vyvraťte . h{Lx ■ L2) = ft(Li) • h(L2) • h(L1UL2) = h(L1)Uh(L2) . ft((L! • L2)ň) = ft(Lf) • fc(L*) • /i(L1nL2) = /i(L1)n/i(L2) • /i(/i(L)) = h(L) • h^ihiĽ)) = L . ft-^Li -L2) = /i"1(ii) -h-^L.,) h-1^ U L2) = ft-^Li) U /i"1^) ft-^ii n l2) = /i"1^!) n ft-1^) 12 Bezkontextové gramatiky 6.1 Co generují tyto gramatiky? a) G = {{S, B, A},{a, b},P, S), kde P = { S —> aB I bA e, A aS bAA, B bS aBB } b) G = ({S, A},{a, b},P, S), kde P = { S —> aAS | a, A &a | 5&a } 6.2 Pro následující gramatiku G = {{S, A, B},{a, b},P, S), kde P = { S -> AaB | BaA, A ^ AB a, B ^ BB b } a) najděte derivační strom s výsledkem bbbbaa b) je tento strom určený jednoznačně? c) kolik různých nejlevějších odvození má slovo bbbbaa d) je gramatika jednoznačná? e) je jazyk L(G) jednoznačný? 6.3 Jaké mají charakteristické vlastnosti derivační stromy pro regulární gramatiky? 6.4 Obsahuje množina jednoznačných CFL všechny regulární jazyky? 6.5 Odpovězte zda pro G = ({S},{a},P, S), kde P = { 5 —> SSS I a } a) je gramatika jednoznačná? b) je jazyk L(G) jednoznačný? 6.6 Navrhněte jednoznačnou gramatiku generující jazyk L = {wwR \ w € {a, b}*} U {ak k > 1}. 6.7 Navrhněte gramatiku pro jazyk L = {axVck \ i,j,k > l,i = j nebo j ^ k}, je gramatika jednoznačná? Lze sestrojit jednoznačnou gramatiku pro tento jazyk? 6.8 Najděte ekvivalentní redukovanou gramatiku k této gramatice: ({S, A, B, C, E,F,D},{a, b, c},P, S), kde {S aA 6B, A -> aAB aa AC* | AE, B -> bBA && CB | BF, C -> DE, D —> CC L>L>, E -> FF FE, F -> £c£ } 13 6.9 Najděte bezkontextovou gramatiku, na níž lze ukázat, že opačné pořadí aplikace odstranění nenormovaných neterminálů a odstranění nedosažitelných symbolů vede k neredukované gramatice. 6.10 Je jazyk generovaný gramatikou G bezkontextový? G = ({S,T},{x,y},P,S), kde P = { S -> xT, T Sx, xTx —> y } 6.11 Navrhněte bezkontextové gramatiky pro jazyky: a) L = {wwR w e {a, b, c}*} b) L = {w | iŕ< € {a, b,c}*,w = wR} c) L = {a'in+2b2n n > 2} d) L = {a"6"bm+1cm_1 n > 0,m > 1} e) L = {anbmcmdn n,m > 0} f) L = {uxv u, x, v e {a, b, c}*,uv = (uv)R, g) L = {w\w € {a,b}*,#a(w) > #b(w)} h) L = {w\we{a,b}*,#a(w) = 2*#b(w)} 14 Normální formy CFG, pumping lemma pro CFL 7.1 Odstraňte e- ■pravidla: G = ({S, A B, C, D},{b, c, a},P, S), kde P= { S -i ► ABC, A -i ► AbA BC, B -i ► bB b cBbAa e, C* -; > cD 1 c Ab 1 e, D -h > sss 1 & } 7.2 Odstraňte e- -pravidla: G = ({S, A, B, C, D},{b, c},P, S), kde P={S y ABC, A -h y Ab BC, B - y bB \ b Ab 1 e. C - y cD c Ac e, D - y SSD cSAc } 7.3 Odstraňte e-pravidla: G = ({SJ,ľ,Z},{l,0},P,S), kde P= { S - > IX Yl 1 IZ, X - > 0YZ1 SUľ 1 Y, Y - > 1 \ XI e, Z - > SZ 1 0 1 e } 7.4 Význam konstrukce množin N£ na príkladu G = ({A, B, C},{a, b, c},P, A), kde P={A- y BC a e, B - y aB ACC 1 b, C - > cC AA 1 c} 7.5 Odstraňte jednoduchá pravidla. Diskuse o v; G = ({S, X, Y, A, D, B, C},{b, a},P, S), kde P= { S - > X r, A - > bS D, D - » ba, B - > Sa a, X - > aAS c, C - > aD S, Y - > SBb } 7.6 Převeďte do Chomského normálni formy G = ({S, A, B},{a, b],P, S), kde P= { S - > SaSbS aAa bBb, A - > a.4 aaa \ B \ e, B - > B6 66 1 6 } 15 7.7 Převeďte do Chomského normální formy G = {{S, H, L},{0,1},P, S), kde P = { S -> Oifl I 1L0 | e, H ^ HH \ OHI LH | e, L LL | 1L0 | ířL | e } 7.8 Navrhněte gramatiku v CNF: a) L = {wu'-R I w e {a,b}*} b) L = {a2ib3ic> i > l,j > 0} 7.9 Nechť G je gramatika v CNF. Nechť w € £(G), |«'| = n. Jaká je minimální a maximální délka odvození slova w v G? 7.10 Odstraňte levou rekurzi a transformujte do GNF G = ({S,A,B},{a,b},P,S), kde P={ S ^ Aa Bb | íiaA | SaA | A -> AAb | a6 | 5B6, B -> Bbb | BBB | M& } 7.11 Odstraňte levou rekurzi a transformujte do GNF G = ({S,A,B},{1,0},P,S), kde P = { S -> AI | 0 1B, A BSO | 10 | 550, B ^ OB | BLB | 50 } 7.12 Odstraňte levou rekurzi a transformujte do GNF G = ({S,X,Y},{c,d,b,a},P,S), kde P = { S ^ Xc. \ Yd \ Yb, X ^ Xb | a, Y SaS1 | la } 7.13 Odstraňte levou rekurzi a transformujte do GNF G = ({5,T},{í,s},P,5), kde P = { S —> TTí | Tí T5 I s, T 5sT | TsT | t } 7.14 Transformujte do Greibachové NF. Výslednou gramatiku převeďte do 3GNF. G = ({A, B, G, D},{a, b},P, A), kde P = { A - * BG, B - CD AB, C - D - DD } 7.15 Dokažte, že následující jazyky nejsou bezkontextové a) L = {wcw | w € {a, b}*} b) L = {anbncn | n > 1} c) L = {a"6mcn(im | »!, íř! > 1} 16 Zásobníkové automaty 8.1 Daný ZA A = ({qo,qi,q2,qz,qi},{a,b,c,d},{Z,A},5,qo,Z,{qi}) a, Z) = {(q0 AZ)} S(q0 a, A) = {(q0 AA)} b, A) = {(qi e)} ô(qi b, A) = {(qi e)} S(qi e, A) = {(q2 A),(q3,A)} S(q2 c, A) = {(q2 e)} d, A) = {fe £)} S(q2 e, Z) = {(94 z)} S(q3 e, Z) = {(94 z)} • Načrtněte stavový diagram ZA A. • Naznačte 4 různé výpočty na vstupu aab2c (stačí na obrázku). • Popište jazyk L (A). 8.2 Je daný ZA A = ({qo, q\, q2, qz, q 0} b) L = {w I w G {a, b}*; w = wR} c) L = {a3nb2n n > 1} d) L = {aan+2b2n-1 n > 1} e) L = {w I w e {a, b, c}*; #a(w) = #6(w)} f) L = {w I w e {a, b, c}*;#a(w) ± #b(w)} g) L = {akb> \ \ 1} i) L = {cŕVc? \ i, j > 1} U {akbkcm k,m > 1} j) L = {aklbak2b... bakr r > 1, k{ > 1 (i = 1,..., r; existuje p, s : p 7^ s, kp = ks)} 8.4 Daný ZA A = ({qo, qi}, {a, b}, {Z, A}, ô, qo, Z, {qi}) akceptující koncovým stavem transformujte na ekvivalentní automat akceptující prázdným zásobníkem. Určete L(A). ô(qo,a,Z) = {(q0,AZ)} S(q0,a,A) = {(q0, AA)} 5(qo,b,A) ={(qi,e)} S(q0,a, Z) = {(qo,X)} S(qi,a,Y) = {(qi,YY)} 5(q2,b,Y) = {(q2,e)} S(q3,c,X)={(q3,e)} 5(qo,a,X)={(qo,XX),(qi,YX)} S(Ql,b,Y) ={(q2,e)} S(q2,c,X) = {(q3,e)} S(q3,d,X)={(q4,e)} 17 8.5 Daný ZA A = ({q}, {(,)}, {Z, L, P}, 6, q, Z, 0) akceptující prázdným zásobníkem transformujte na ekvivalentní automat akceptující koncovým stavem. Určete L(A). S(q,(,Z) = {(q,L)} S(q,(,L) ={(q,LL)} S(q,),L)={(q,e)} 8.6 Pro danou G navrhněte (rozšířený) ZA, který provádí syntaktickou analýzu: a) shora dolů, b) zdola nahoru. V obou případech proveďte analýzu slova ababaa. G = ({S, A, B},{a, b},P, S), kde P = { S -> e I abSA, A AaB aB \ a, B aSS | bA } 8.7 Rozšířený zásobníkový automat, který vznikl metodou syntaktické analýzy zdola nahoru z gramatiky z příkladu 8.10 převeďte na standardní zásobníkový automat. 8.8 Daný ZA A = ({qo, qi, q-ž}, {«, b, c}, {A, B, C}, Ô, qo, A, 0) akceptující prázdným zásobníkem transformujte na ekvivalentní bezkontextovou gramatiku. 6(q(ha,A) = {(qi,B)} ô(qu c, A) = {(q2, e)} S(q2, e, B) = {(q2, e)} 5(q0,b,A) ={(Ql,AB)} S(qi,a,B) = {(q0,ABC)} 6(q2,e,C) = {(q0,A)} 8.9 Daný ZA A = ({qo, qi}, {a, b}, {Z, X}, S, 0, Z, 0) akceptující prázdným zásobníkem transformujte na ekvivalentní bezkontextovou gramatiku. 6(q0,a,Z) = {(q0,AA)} 5(q0,a,A) = {(q0,AAA)} S(q0, b, A) = {(t]i, e)} 5(qub, A) = {(que)} 8.10 Pomocí algoritmu C-Y-K rozhodněte, zda následující gramatika generuje slovo kolaloka. G = ({S, A, B, D, C},{fc, o, a, !},P, S), kde P= { S A B C D AB k 0 a 1 DB, AB, BD AC DC SC, SA, AC } 18 Uzáverové vlastnosti CFL 9.1 O každé z následujících implikací rozhodněte, zda je pravdivá a) Li, L'2 bezkontextové => L\ U Ľž je kontextový b) L\ bezkontextový A L\ n Ľž není bezkontextový => Ľž není bezkontextový c) L\ regulární A Ľž bezkontextový => co—{L\ n L 2) bezkontextový d) L\ konečný A L2 bezkontextový => co—{L\ n L2) bezkontextový 9.2 Jsou dané jazyky L = {wwR I w G {a, b}*} R = L((a + b)*a + e) Navrhněte ZA pro jazyk L n R. Jazyky L, R jsou akceptovány zásobníkovým a konečným automatem s těmito přechodovými funkcemi a koncovými stavy. SL(q0,x,Z) = {(q0,xZ)} \Jx e {a, b} SR(p0,a)=p0 SL(qo,x,y) = {(q0,xy)} Vx,y e {a,b} SR(p0,b)=p1 SL(q0,e,x) = {(qi,x)} \Jxe{a,b,Z} SR(p1,b)=p1 5L{qi,x,x) = {(qi,e)} \Jx e {a,b} SR(p1,a)=p0 6L(qi,e,Z) ={(q2,Z)} FL = {q2} FR = {p0} 9.3 Je dána bezkontextová gramatika G = ({S},{a, b},P, S), kde P = { S —> aS I Sb I a} a) Má tato gramatika vlastnost sebevložení? b) Má jazyk generovaný gramatikou vlastnost sebevložení? c) Je j azyk generovaný gramatikou regulárni? d) Jaký je vztah mezi vlastností sebevložení a regularitou? 9.4 Je dán bezkontextový jazyk L, L C {a, b}* Zkonstruujeme nový jazyk L\ takto: a) L\ = {x I 3y e {a, b}*; xy e L} b) L\ = {x I 3y G {a, b}*; yx e L} Dokažte, že L\ je taky bezkontextový. 19 Konstrukce Turingových strojů 10.1 Navrhněte determinstický jednopáskový Turingův stroj rozhodující jazyk L = {anbmďlďn m, n > 1} 10.2 Navrhněte deterministický jednopáskový TS se vstupní abecedou {0,1} a takový, že výpočty na slovech tvaru 0*1* jsou akceptující a výpočty na ostatních slovech jsou nekonečné. 10.3 Navrhněte 3-páskový (vstupní + 2 pracovní pásky) TS pro jazyk L = {w € {a, b}* | #a(w) = #b(w)} 10.4 Navrhněte TS (determ. nebo nedeterm.) TS pro jazyk: a) L = {aib1ck | k = ij,i,j G N} b) L = {ww | w G {a, &}*} c) L = {ap | p není prvočíslo } d) L = {anw w € {0,1}*, w je binární zápis čísla n} 20 Vztah TS a gramatik typu O, uzáverové vlastnosti 11.1 Objsaněte rozdíl mezi pojmy TS akceptuje a TS rozhoduje. 11.2 Je daný DTS T (resp. jeho část). Podle algoritmu ze skript navrhněte k němu ekvivalentní gramatiku: ô(q, d>) = (q, d>, R) 6(q, a) = (p, A, R) ô(p, b) = (q, a, L) 6(q, u) = (p, A, R) S(p, u) = (q, a, L) 5{q, b) = {qaccept, A, R) Kde d> je levá koncová značka, u označuje prázdné políčko, stavy jsou {p, q, qaCcePt}, Q je počáteční stav, vstupní abeceda je {a, b} a pásková abeceda odpovídá množině {[>, u, A, a, b}. 11.3 O každé z následujících implikací rozhodněte, zda je pravdivá. a) R je regulární, L je rekurzivně spočetný => R n L je regulární b) L je rekurzivní => co-L je rekurzivní c) L je rekurzivní => L* je rekurzivní d) L je kontextový => co-L je rekurzivní e) L není rekurzivní =>co—L není rekurzivní f) L není rekurzivní a R je rekurzivní => L \ R není rekurzivní g) L není rekurzivní, R je rekurzivní & RCL=>L^R není rekurzivní 11.4 Navrhněte gramatiky pro následující jazyky: • {w | w e {a, b, c}*, #a(w) = #6(w) = #c(w)} • {ww I w G {a, b, c}*} • {anbncn n > 0} • {an | n je mocnina 2} 11.5 Ukažte, že jazyk L = {w \ w je kód dvojice (A, v) takové, že TS A zastaví svůj výpočet nad slovem v} je jazyk typu 0 dle Chomského hierarchie. 11.6 Existuje jazyk, který není ani jazykem typu 0 dle Chomského hierarchie? 21 Redukce 12.1 Rozhodněte, zda platí následující implikace. Své rozhodnutí zdůvodněte. a) A co—A A je regulární c) A je rekurzivně spočetná a co—A A je rekurzivní d) A je rekurzivně spočetná a A A je rekurzivní e) A B je rekurzivní f) A je rekurzivně spočetná => A 0} • Příklad 6.1 • Příklad 6.2 • Příkald 6.3 • Příklad 6.4 • Příklad 6.5 • Příklad 6.6 • Příklad 6.8 • Příklad 6.9 • Příklad 6.10 • Příklad 6.11 (dle času) • Příklad 6.7 rozmyslet za DU 8. cvičení: Normální formy CFG • Připomeňte princip ostraňování e-pravidel • Příklad 7.2 • Připomeňte princip ostraňování jednoduchých pravidel • Příklad 7.5 • Definujte Chomského NF (CNF) a připomeňte postup převodu CFG do CNF • Příklad 7.6 • Příklad 7.8a) • Příklad 7.9 • Vysvětlete odtranění přímé levé rekurze na A->Ab I Ac I d I e • Příklad 7.12 25 9. cvičení: Zásobníkové automaty a syntaktická analýza • Příklad 8.1 (zadejte přechodovou relaci tabulkou [q^Z/a —> (qo,AZ)] • Příklad 8.2 • Příklad 8.3b • Příklad 8.6 • Příklad 8.8 • Diskutujte ekvivalence způsobu akceptování zás. automatů a podstatu převodu • Zbude-li čas, cvičte příklady 8.4, 8.5 a 8.7 10. cvičení: Uzáverové vlastnosti bezkontextových jazyků a pumping lemma pro bezkontextové jazyky • Příklad 7.15 • Příklad 9.1 • Příklad 9.2 (není nutné konstruovat celou přechodovou funkci) • Příklad 9.3 • Příklad 9.4 (formální konstrukce) 11. cvičení: Konstrukce Turingových strojů • Připomeňte jak fungují Turingovy stroje • Příklad 10.1 • Příklad 10.2 • Příklad 10.3 • Příklad 10.4 - formulujte princip algoritmu pro TS 12. cvičení: Vztah TS a gramatik typu 0, uzáverové vlastnosti • Příklad 11.1 • Diskutujte vztah TS acceptuje/rozhoduje a gramatiky typu 0 • Příklad 11.2 • Příkakl 11.3 • Příklad 11.4a • Příklad 11.4b-d pouze myšlenky fungování CFG • Příklad 11.5 • Příklad 11.6 13. cvičení: Redukce 26 Zadání cvičení IB102 1. cvičení: Operace nad jazyky • Připomeňte pojmy abeceda, slovo, jazyk apod. • Připomeňte základní operace nad jazyky a procvičte je s využitím příkladů 1.1 (průnik a sjednocení cvičit netřeba) a 1.2. • Příklad 1.3 d) e) f) h). U d) vysvětlete, že neplatnost tvrzení dokazujeme protipříkladem. • Příklad 1.4. • V sudých skupinách cvičte příklad 1.5, v lichých příklad 1.6. • Příklad 1.7. • Příklad 1.8 b). Zdůrazněte, že dva jazyky jsou stejné, právě když platí obě inkluze Ca3. Jednu inkluzi dokažte. • Příklad 1.8 c). Pozor, rovnost neplatí. 2. cvičení: Gramatiky, deterministické konečné automaty • Připomeňte pojem gramatiky a cvičte příklad 1.9 a) anebo b). • Příklad 1.11 a) d). • Příklad 2.1. • Příklad 2.2 a) b) c) d). Dejte prosím studentům možnost, aby se pokusili alespoň nějaký automat sestrojit sami. Pozor, automaty musí být deterministické. • Příklad 2.3 a) b). • Pokud vám zbyde čas, cvičte příklad 2.5 a následně zbylé části příkladu 1.11 nebo příklad 2.7. 3. cvičení: Pumping lemma a Myhillova-Nerodova věta • Zopakujte Pumping lemma. • Příklad 2.6. Z lehčích příkladů a)-c) udělejte jeden pořádně, ostatní zrychleně. Dále udělejte pořádně příklad g) a zrychleně příklad e). Upozorněte studenty, že vlastní text důkazu zůstává v podstatě stejný (důkaz lze prezentovat jako formulář, který se vždy na pár místech doplní). • Zopakujte Myhillovu-Nerodovu větu a pojmy, které využívá. Zdůrazněte následující aspekty: 1. Z DFA lze odvodit pravou kongruenci s konečným indexem takovou, že L je sjednocení nějakých tříd ekvivalence. Zopakujte, jak se to dělá. 2. Z takové pravé kongruence lze odvodit DFA (samotná kongruence neurčuje koncové stavy, ty určí až Ľ). Zopakujte, jak se to dělá. 27 3. Pro každý jazyk L C T,* (i neregulární) je ~£ vždy pravá kongruence a L je sjednocením nějakých tříd rozkladu T,*/ ~£. Má-li ~£ konečný index, lze sestrojit DFA pro L a L je tudíž regulární. 4- ~l je nejhrubší ze všech pravých kongruencí ~ takových, že L je sjednocením některých tříd rozkladu £*/ ~. • Příklad 3.9. • Příklad 3.12. 4. cvičení: Myhillova-Nerodova věta • Zkontrolujte znalost Myhillovy-Nerodovy věty a pojmů, které využívá. • Příklad 3.10. Jednu odrážku udělejte pořádně, ostatní zrychleně. • Příklad 3.8. Udělejte jednu odrážku. Pak zkuste totéž pro jazyk L = {a}* ■ {&}* • {c}* • {d}* a upozorněte, že přestože index ~£ je 5, existuje pro L deterministický FA se čtyřmi stavy. Problém je v tom, že tento automat není totální a tudíž není minimální. • Příklad 3.13. 5. cvičení: Minimalizace a kanonizace konečných automatů, nedeterministické automaty, determinizace, odstranění e-kroků • Zdůrazněte, že před minimalizací automatu je třeba odstranit nedosažitelné stavy a ztotálnit přechodovou funkci. • Příklad 3.2 b). • Budete-li mít pocit, ze jeden příklad na minimalizaci nestačil, pokračujte příkladem 3.1 a) a případně 3.3. • Zopakujte nedeterministické FA. • Příklad 3.4 a) c) d). • Zopakujte determinizaci. • Příklad 3.5 a) nebo b). Upozorněte, že determinizaci může vzniknout stav 0 a jeho následníci se počítají běžným způsobem. • Zopakujte odstranění e-kroků. • Příklad 4.5. Příklad řešte pomocí tabulkového zápisu. Chcete-li, můžete nejdřív ukázat, jak snadno se v tom udělá chyba, když se to dělá přímo na grafu. • Budete-li mít pocit, že příklad 4.5 nestačil, pokračujte příkladem 4.7 (obvykle stačí spočítat jen pár řádků). • Zbude-li čas, udělejte ostatní části příkladu 3.4. 6. cvičení: Uzáverové vlastnosti regulárních jazyků • Zopakujte, na které operace jsou regulární j azyky uzavřené. Diskutujte, na které operace je/není uzavřena třída konečných jazyků. • Příklad 5.8. Tento příklad ukazuje, že konečná změna jazyka (tj. přidání či odebrání konečně mnoha slov) nemá vliv na jeho (ne)regularitu. Toto pozorování lze použít v dalších příkladech, např. v příkladu 5.3. • Příklad 5.1. • Dokažte uzavřenost neregulárních jazyků na komplement (včetně formálního důkazu). 28 • Příklad 5.2. • Příklad 5.3. • Příklad 5.4. • Příklad 5.5. • Příklad 5.6. • Zbude-li čas, udělejte příklad 4.12 a) a ukažte, proč b) nevyjde stejně. 7. cvičení: Regulární výrazy, převod formalismů pro popis regulárních jazyků • Příklad 4.8. Stačí 2 odrážky. • Příklad 4.9. • Příklad 4.10. • Příklad 4.11. • Příklad 4.2. • Příklad 4.4. 8. cvičení: Bezkontextové gramatiky, derivační stromy, jednoznačnost, redukované gramatiky • Příklad 6.11 a). • Příklad 6.1. U druhé gramatiky neztrácejte moc času, příklad slouží jen jako demonstrace popisné síly bezkontextových gramatik. • Příklad 6.2. • Příklad 6.3. • Příklad 6.5. • Příklad 6.6. Není třeba formálně dokazovat, že je navržená gramatika jednoznačná. Slovní argumentace postačí. • Příklad 6.7. Stačí identifikovat problém. • Příklad 6.8. Připomeňte, že nejdříve je třeba odstranit nenormované symboly a až pak ty nedosažitelné. Opačné pořadí může vyústit v neredukovanou gramatiku, což lze ukázat i na příkladu 6.8. • Zbyde-li čas, dělejte další odrážky z příkladu 6.11. 9. cvičení: Transformace bezkontextových gramatik, Pumping lemma pro bezkontextové jazyky • Příklad 7.2. • Příklad 7.5. • Příklad 7.6. • Příklad 7.8 a). Pokud stíháte, udělejte i část b). • Příklad 7.15. Jednu odrážku udělejte pečlivě, v dalších se soustřeďte jen na to podstatné (pokud nestíháte). 29 10. cvičení: Odstranění levé rekurze a převod do GNF, zásobníkové automaty • Vždy explicitně zdůrazněte pořadí netermínálů, které používáte při odstranění levé rekurze a při převodu nelevorekurzivní CFG do GNF. • Připomeňte odstranění přímé levé rekurze na pravidlech A —> Ab \ Ac \ dA \ e. • Příklad 7.13. Substituci nedodělávejte celou, je to dlouhé. • Příklad 7.12. Tento lze dopočítat do konce. • Budete-li mít pocit, že předchozí příklady nestačily, udělejte i příklad 7.10 (pouze odstranění levé rekurze). • Příklad 7.14 (bez transformace do 3GNF). Tento příklad je poučný, neboť gramatika generuje prázdný jazyk a dle algoritmu tedy přímo vyjde gramatika s jediným pravidlem S —> aS. Ovšem většina studentů se vrhne do odstraňování levé rekurze. • Příklad 8.1. Zmiňte prosím, že byl definován pojem krok výpočtu, ale pojem výpočet pro PDA definován nebyl. Lze si představit hned několik definic, které kromě zjevných požadavků splňují i tyto: 1. Musí se přečíst celý vstup. V tom případě by v příkladu existoval jen 1 výpočet. 2. Musí se číst "dokud to lze". V tomto případě existují 4 výpočty. 3. Stačí přečíst libovolnou část vstupu. V tom případě je výpočtů hodně. 11. cvičení: Konstrukce zásobníkových automatů, nedeterministická syntaktická analýza, C-Y-K • Příklad 8.3. Udělejte pořádně aspoň dvě odrážky včetně c). Zbude-li čas, můžete se na konci k dalším odrážkám vrátit. • Příklad 8.6. Ukažte, jak lze konstrukci analyzátoru shora dolů použít u příkladů na konstrukci PDA: nejdřív se zkonstruuje CFG a z ní pak lehce PDA. Velmi elegantně tak lze řešit třeba příklad 8.3 c). • Příklad 8.10. Používejte prosím stejný zápis jako na slajdech. 12. cvičení: Uzáverové vlastnosti bezkontextových jazyků • Příklad 9.1. • Příklad 9.2. • Příklad 9.3. • Příklad 9.4. • Zbude-li čas, řešte příklad 11.4. 30 Řešení některých příkladů 31 Formální jazyky, regulární gramatiky 1.1 a) {xy,y,yx,z} b) {y} c) {xyy,xyz,yy,yz,yxy,yxz}, {yxy,yy,yyx,zxy,zy,zyx) d) {£}> {V,*}, {yy,yz,zy,zz}, {yyy,yyz,yzy,yzz,zyy,zyz,zzy,zzz}, {e, y, z, yy, yz, zy, zz, yyy, yyz, yzy, yzz, zyy, zyz, zzy, zzz,...} tj. libovolné slovo z písmenek y a z včetně e, {y, z, yy, yz, zy, zz, yyy, yyz, yzy, yzz, zyy, zyz, zzy, zzz,...} tj. libovolné slovo z písmenek y a z kromě e e) {x, y, z}* n. {y, z} tj. libovolné slovo složené z písmenek x, y a z včetně e, kromě slov y a z 1.2 a) {e}, 0, {e}, {e} b) {e}, 0, 0, {e} pokud e e L jinak 0 c) 0, 0, {e}, L 1.3 a) {a, aa,ba, abc, e} b) {a, ba} c) {aba, aabc, aa, a, aaba, aaabc, aaa,baba,baabc,baa,ba} d) ne, protipříklad aabc G L\ ■ L2 \ L2 ■ L\ e) jedno slovo z množiny {a, aa, ba, aba, aaa, baba, baa} f) ano, protože e G L2; ne, protipříklad L\ = {a},L2 = {b}; pro pokročilé: implikace lí=^v platí, implikace "^=" platí pouze v upravené podobě e £ L2 <= (L\ C L\ ■ L2 A L\ 7^ 0) g) ano, ano, ne h) všechna slova nad danou abecedou, kromě slov z jazyka L2, formálně: {a, b, c, d}* \ L2 1.4 a) Neplatí. Protipříklad: L = {aa, bb}, i = 2, U = {aaaa, aabb, bbaa, bbbb}, {w1 w € L} = {aaaa, bbbb} b) Neplatí. Protipříklad: L = {aa}, L2 = {aaaa}, ale \aaaa\ 7^ 2 c) L = {a} 1.5 L\ = L4 = L5 D L2, L\ = L4 = L5 D L3, Li = L4 = L5 D L@, neporovnatelné: L2, L3, -Z^ Li - všechna slova nad {x, y, z} L2 - všechna slova nad {x, y, z} tvaru xyzxyzxyz ... xyz L3 - všechna slova nad {x, y, z}, ve kterých jsou všechna x před všemi y a z a všechna y před všemi z L4 - všechna slova nad {x, y, z}; protože {x, y, z} C {x}* ■ {y}* ■ {z}* L5 - všechna slova nad {x, y, z}; protože {x, y, z} C {x, y}* U {z}* Le - všechna slova nad {x, y, z}, která obsahují alespoň jeden výskyt x 1.6 L\ = L5 D L2 D Lq, L\ = L5 D L3 D L4, L2 D L4, neporovnatelné: L2 a L3, L@ a L3, Lq a L4 Li - všechna slova nad {x, y, z} L2 - všechna slova nad {x, y, z}, kromě e L3 - všechna slova nad {x, y, z}, ve kterých jsou všechna x před všemi y a z a všechna y před všemi z L4 - ty slova z L3, která mají právě 2 výskyty y L5 - všechna slova nad {x, y, z}; protože {x, y, z} C {x}* ■ {y}* ■ {z}* Lq - všechna slova nad {x, y, z}, která obsahují alespoň jeden výskyt x 1.7 a) (Li U L2)* ■ Li • (Lx U L2)* ■ Lx ■ (Lx U L2)* b) (Lx • Lx U Lx ■ L2 U L2 ■ Lx U L2 ■ L2)* c) L\ ■ (Li U L2)* ■ L2 d) L\ U L2 U Li • (Li U L2)* ■ ^1 U L2 ■ (L\ U L2)* ■ L2 a pokud naznáme, že e také začíná a končí stejným znakem, je třeba k řešení přidat U {L\ C\L2) e) (L\ U L2)* -L\-L2-L\ - {L\ U L2)* f) (Li-Li ULi-L2 UL2-Li UL2-L2)* n Li-(Li U L2)* ■ L2 g) ((Li-Li ULrL2 UL2-Li UL2-L2)f 1.8 a) ne, Li = {a} a I2 = {&} b) ano, nutno dokázat obě inkluze C a D c) ne, L\ = {a}, L2 = {ab} a L3 = {b,e} d) ne, L\ = {a} a L2 = {b} e) ne, L\ = {a} a L2 = {b} f) ano, nutno dokázat obě inkluze C a D g) ne, L\ = {a} a L2 = {b} 1.9 a) {anbn \ n e N0}, typu 0 b) {b, c}* ■ {a} ■ {a, b, c}+, typu 3 (regulární) 1.10 {w G {a, b}* I #a(w) = 2fc,#b(w) = 2j;j,k € No}, dolní indexy u navržených neterminálů představují zbytek po dělení počtu 'a' (resp. 'b') dvěma Deterministické konečné automaty, pumping lemma b) L = {a} ■ {b, aa}* ■ {a} c) L = ({a} ■ {b}* ■ {aa})* ■ ({a} ■ {b}* ■ ({a} U {ab} ■ {a, b}*) U {b} ■ {a, b}*) b a a,b 32 33 a,c ____^____ a,b,c 2.4 L={a}.{by.{a}.({c}.{d}yi){b} 2.5 L = {w e {a, &}* | #a(w) = #(,(») Atí = w.v |#a(u) - #6(u)| < 3} 2.6 U příkladu e) je třeba volit slovo a™&™!+™. 2.7 Příklad a) je regulární, b) není, jako slovo lze zvolit například ancbn^ a,b,c,d c 1.1 lf Není regulární. b,c l.llh l.lli B-í--D 0 ' o b 0 34 l.llj Minimalizace DFA, nedeterministické FA, (Myhillova-)Nerodova věta 3.1 a) 3.2 a) a b -> A B C B D B C C D <- D C B a b -> A B C B C A C C D D C E A B C B D B <- C B C <- D E B E F C F F F Výsledné automaty v obou případech nejsou ekvivalentní automatům uvedeným v zadání vpravo. 3.3 Není. 6 3.4 a) a.b.c.d a.b.c.d c) a,6,c,d a a a a d) e) 1 0,1 0,1 0,1 0,1 0 10 11 35 o o 3.5 a) a b c [1] [23] [34] [1] <- [23] [123] [14] [234] [34] [123] [1] [34] <- [123] [123] [134] [1234] [14] [123] [134] [134] <- [234] [123] [14] [234] [134] [123] [134] [134] <- [1234] [123] [134] [1234] b) a b c [1] [12] [1] 0 [12] [12] [13] [1] 0 0 0 0 [13] [12] [1] [14] [14] [125] [1] 0 <- [125] [12] [136] [1] [136] [127] [1] [14] <- [127] [12] [13] [1] 3.6 ({a, &}.{&} U {a, b}.{b}.{a, b})*.{a, b}.{b} 3.8 a) Předpokládejme, že takový automat existuje. Pak ze slov a°, a , a , a, a musejí dvě nutně padnout do stejné třídy rozkladu £*/ i < j. Pak platí Označme je a1, aJ (i =í j) a bez újmy na obecnosti předpokládejme, že a?.(ŕ'i a4+i-j aA e L, ÍL a tedy a1 7^ aJ |~£,| > 5. b) Analogicky jako v a). 3.10 a) Důkaz sporem. Předpokládejme, že L je regulární. Pak prefixová ekvivalence ~£ má konečný index, označme jej n. Pak ovšem ze slov a, a2, a4,..., a2 nutně musí některá dvě slova padnout do stejné třídy rozkladu, označme je ak,al (BUNO k 7^ l). Po přiřetězení slova ak dostáváme slovo akak G L a slovo alak £ L. Tím je dosažen spor s ak ~£ a1 a proto L není regulární. b) Analogicky. Ze slov a, a2,... ,an,an+1 musí být alespoň dvě ekvivalentní. Nechť ak ~£ a1 (BUNO k < l). Ovšem ak.bk e L, a1 .bk g L. c) Analogicky. Ze slov abb, a2bb,..., an+1bb musí být alespoň dvě ekvivalentní. Nechť akbb ~£, albb (BUNO k ^ l). Ovšem akbb.ak e L,albb.ak g L. d) Analogicky. Ze slov e, a, a2,..., an musí být alespoň dvě ekvivalentní. Nechť ak ~£ a1 (BUNO k < l). Ovšem ak.bk g L, al.bk e L. 3.11 Definujeme binární relaci ~ takto: u ~ v ~ je ekvivalence, ~ je pravá kongruence, | 3.12 a) 4 b) nemá konečný index #„(«) = (mod 3) 3, tedy má konečný index, L {w I #a(w) mod 3 = 0} 3.13 a) ~ je ekvivalence i pravá kongruence, index je 4. L může být libovolný jazyk, jehož minimální automat odpovídá přímo relaci ~. Takových jazyků je 12, což je vidět po nakreslení automatu (bez akceptujících stavů) podle ~ a zvážení, pro které označení koncových stavů je automat minimální. Jazyky Ľ jsou právě ty, které lze popsat stejným automatem, ale s takovou množinou koncových stavů, při které automat není minimální. Např. Ľ = {a, b}*. b) ~ není ekvivalence (není tranzitivní). c) ~ je ekvivalence i pravá kongruence, index je 9. Lze podle ní sestavit tento automat: 36 0& 16 2b 3b O O O O 6 6 6 6 Je vidět, že automat nebude při žádném označení koncových stavů minimální: stavy e, Oa, 0& mají stejné přechody a vždy budou alespoň dva z nich označeny jako akceptující nebo neakceptující a tudíž ty dva stavy budou jazykově ekvivalentní. Naopak Ľ může být jakýkoliv jazyk rozpoznávaný uvedeným automatem s libovolným označením koncových stavů. Takových jazyků Ľ je tedy celkem 29. Regulární gramatiky a výrazy FA, s-kroky, Kleeneho věta 4.1 a b c o Š {Ä q f} {č} 0 Ä {Á} {B,qf} B {B,C} {C} {A q f] Č {A q/} {B,qf} 0 <-9f 0 0 0 4.2 a b c {X} {Y} {if} ~x 0 {S, X} 0 Y 0 {S} m ~Ž {Š} {if} {in <-9f 0 0 0 4.5 a b c d o 0 {0,1,2,3,4} 0 0 {3,4} 1 {0,1,2,3,4} 0 0 {3,4} <- 2 {3,4} 0 0 0 3 0 {3,4} {2} 0 4 0 {3,4} {2} 0 4.7 a b c -> 1 {1,2,5,6} {2,3,5,6} 0 2 {2,5,6} {2,3,5,6} 0 3 0 {2,6} 0 4 {1,2,5,6} {1,2,3,4,5,6} {2,3,6} 5 {2,5,6} {2,3,5,6} {2,3,6} <- 6 {2,5,6} {2,3,5,6} {2,3,6} 4.11 a) (a + b)*ab b) b*(ab*ab*)* c) a(a + b)*a + b(a + b)*b +a + b (pokud e také začíná a končí na stejným symbolem, přičteme ještě e) d) ((a + 6)(a + &))* 4.12 a) Mi je třída všech konečných jazyků. 37 b) Nechť Ei je nějaká abeceda. Pak C(Ti) definujeme jako množinu všech slov, kde se každé písmeno z abecedy vyskytuje aspoň jednou, tj. C(T') = {w e £í | Va e Ei : #a(w) > 0}. Pak M'2 je třída všech jazyků L takových, že pro všechny T\, které jsou podmnožinou abecedy jazyka L, platí: L n C(Ľi) je konečný nebo C(Ti) \ L je konečný. Poměrně snadno se ukáže, že M2 všechny takové jazyky musí obsahovat a že je tato třída zároveň uzavřená na sjednocení, průnik a komplement. c) M3 je třída všech konečných jazyků. Uzáverové vlastnosti 7Z 5.1 Neplatí. Jazyky Li = {erb1} pro každé i > 0 jsou konečné a tudíž regulární, ale IJi^i Li = {anbn n > 0} není regulární. 5.2 Li = {a, b}* n. {erb1} pro každé i > 0. Pak Hi^i Li = {a, b}* \ {anbn \ n > 0}, což není regulární jazyk, protože {anbn n > 0} není regulární jazyk a regulární jazyky jsou uzavřené na doplněk. 5.3 Neregulární jazyky jsou uzavřené na komplement. U všech ostatních operací lze najít jazyky takové, že výsledkem je neregulární jazyk, i takové, že výsledek je regulární. Nechť R = {anbn n > 0} je jazyk nad T, = {a, b}. R jistě není regulární. operace regulární výsledek neregulární výsledek lx nL2 R n co-R = 0 RDR = R LÍ\JL2 RUco-R = T,* RUR = R Li \ L2 i?\i? = 0 R n. co-R = R Lx-L2 (R u {e}) • co-R = T,* R-R L\ (co-R)* = T* R* 5.4 Platí. 5.5 Ani jedna implikace neplatí. 5.6 Stačí zvolit L\ jako libovolný neregulární jazyk a L2 jako doplněk L\. Bezkontextové gramatiky 6.1 a) L = {w G {a, b}* \ #a(w) = b) Jazyk se nedá moc rozumně popsat. 6.4 Ano, každý regulární jazyk je jednoznačný CFL. 6.7 Nelze. Průnik podmínek (slova s nejednoznačným odvozením) nelze popsat bezkontextovou gramatikou (nelze formulovat podmínky disjunktně tak, aby šly popsat pomocí pravidel bezkontextových gramatik). Normální formy CFG, pumping lemma pro CFL 7.9 Minimální i maximální délka odvození je 2n — 1. Zásobníkové automaty 8.2 a) {á1 V i > j > 0} Uzáverové vlastnosti CFL 9.3 a) ano b) ne c) ano d) třída bezkontextových jazyků bez vlastnosti sebevložení se rovná třídě regulárních jazyků Konstrukce Turingových strojů 10.2 Návod: TS bude donekonečna číst vstupní pásku a posouvat se vpravo, nebo bude ve dvou krocích opakovaně posunovat hlavu vlevo a vpravo. Vztah TS a gramatik typu 0, uzáverové vlastnosti 38 11.3 a) Neplatí. Stačí vzít libovolný neregulární rekurzivně spočetný L nad abecedou T, a R = T,*. b) Platí (viz. skripta), c) Platí (viz. skripta), d) Platí, e) Platí, f) Neplatí. Stačí vzít R D L. g) Platí. Plyne z uzavřenosti rekurzivních jazyků na sjednocení. 11.4 a) G = ({S, A, B, C}, {a, b, c}, P, S), kde množina pravidel P obsahuje následující pravidla. S -> ABCS \ e AB -> BA AC -> C A BC -> CB A^a BA -> AB C A -> AC CB ^ BC B^b C^c Lze snadno upravit na kontextovou gramatiku. b) G = ({S', S, A, B, C, K}, {a, b, c}, P, S'), kde množina pravidel P obsahuje následující pravidla. S' - -+ SK Aa - > aA Ba - > aB C*a - > aC* s - >aSA | bSB | cSC \ e Ab- > b A Bb- > &B C*&^ > &C* K - -> e Ac- y cA Bc - >■ cB C*c^ > cC* AK - -+ aif BK - C*K - c) Kontextová gramatika: G = ({S', 5, B, Ě1}, {a, &, c}, P, 5'), kde P obsahuje následující pravidla. S' S | e a&c, 5 —> aBSc | afic, Ba aB, Sfi mb bb 11.6 l = {w | w je kód dvojice (A, v) takové, že TS A nezastaví svůj výpočet nad slovem v} Redukce 12.1 a) Platí (přímo z definičního vztahu), b) Neplatí. A = {ww \ w G {a, b}*}, B = {0}, f (x) = 0 pokud x je tvaru ww, f (x) = 1 jinak, c) Platí, d) Platí (připomeňme, že A