Faculty of Informatics Masaryk University Brno Cvičení k předmětu IB005 Formální jazyky a automaty poslední modifikace 15. dubna 2021 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íleli Jiří Barnat, Vojtěch Řehák, Jan Strejček a mnoho dalších studentů a cvičících. 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 1 2 1 <- 2 3 1 3 4 5 4 4 4 -> 5 1 5 3.3 Overte, zda DFA z príkladu 3.1 a) je ekvivalentní s následujícím DFA zadaným tabulkou a & 1 1 3 -> 2 4 1 <- 3 4 1 4 3 4 3.4 Navrhnete nedeterministické konečné automaty pro následující jazyky: a) L = {w G {a, b, c, eř}* | w obsahuje podslovo abbc nebo &&a 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 /j"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 = {ain+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 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 Y, 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 15, 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, C-Y-K 8.1 Daný PDA A = ({q0, quq2, q3, q4}, {a, b, c, d}, {Z, A}, S, q0, Z, {q4}) ô(q0,a,Z) = {(q0,AZ)} ô(q0, a, A) = {(q0, AA)} ô(q0,b, A) ={(gi,e)} ô(qi,b,A) ={(gi,e)} ô(qi,e, A) = {(q2,A), (q3, A)} ô(q2, c, A) = {(q2,e)} S(q3, d, A) = {(q3,e)} S(q2, e, Z) = {(q4, Z)} S(q3,e,Z) = {(q4,Z)} a) Načrtněte stavový diagram PDA A. b) Naznačte 4 různé výpočty na vstupu aab2c (stačí na obrázku). c) Popište jazyk L (A). 8.2 Je daný PDA A = ({q0,q1,q2,q3,q4},{a,b,c,d},{X,Y,Z},S,q0,Z,{q2,q4}), kde ô(q0, a, Z) = {(q0,X)} ô(q0, a, X) = {(q0, XX), (quYX)} S(qi,a,Y) = {(qi,YY)} S(Ql,b,Y) ={(q2,e)} S(q2, b, Y) = {(q2,e)} S(q2, c, X) = {(q3, e)} S(q3, c, X) = {(q3,e)} S(q3, d, X) = {(q4, e)} a) Popište jazyk akceptovaný automatem, pokud F = {q2}. b) Popište jazyk akceptovaný automatem s původním F, tj. F = {q2, q4}. 8.3 Konstruujte PDA (akceptující koncovým stavem nebo prázdným zásobníkem) pro jazyky: a) L = {alV \ i,j > 0} b) L = {w | w G {a, b}*; w = wR} c) L = {a3nb2n n > 1} d) L = {aan+'2b'2n-1 n > 1} e) L = {w | w e {a, b, c}*; #a(w) = #6(w)} f) L = {w | 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 ^ s, kp = ks)} 8.4 Daný PDA 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 (Ä). ô(q0,a,Z) = {(q0,AZ)} S(q0,a,A) = {(q0, AA)} ô(q0,b,A) ={(gi, e)} 17 8.5 Daný PDA 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ý) PDA, který provádí syntaktickou analýzu: a) shora dolů, b) zdola nahoru. V obou případech proveďte analýzu slova ababbb. G = ({5, A, B},{a, b},P, 5), kde P = { S —> abAS | 66, A AbB aB \ a, B —> 655 aB \ e } 8.7 Rozšířený zásobníkový automat, který vznikl metodou syntaktické analýzy zdola nahoru z gramatiky z příkladu 8.6 převeďte na standardní zásobníkový automat. 8.8 Daný PDA A = ({q0, qi, q2}, {a,b, e], {A, B,C},6,q0, A,$) akceptující prázdným zásobníkem transformujte na ekvivalentní bezkontextovou gramatiku. 8.9 Daný PDA A = ({qo,qi}, {a,b}, {Z, X},S,0, Z,$) akceptující prázdným zásobníkem transformujte na ekvivalentní bezkontextovou gramatiku. ô(q0,a,Z) = {(q0,AA)} 5(q0,a,A) = {(q0,AAA)} S(q0l 6, A) = {( 0 BD 5C C - -> a AC SA, D - l DC AC } S(q0,a,Á) S(q0,b,A) {(luÁB)} S(qi,c,A) = {(q2,e)} S(qi,a,B) = {(q0,ABC)} 6(q2,e,B) ={(q2,e)} S(q2,e,C) ={(q0,A)} 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 PDA 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. a) Má tato gramatika vlastnost sebevložení? b) Má jazyk generovaný gramatikou vlastnost sebevložení? c) Je j azyk generovaný gramatikou regulární? 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ý. SL(q0,x,Z) SL(qo,x,y) SL(q0,e,x) 5L{qi,x,x) 5L{qi,e,Z) Fl = {q2} {(q0,xZ)} {(Qo,xy)} {(12, Z)} \/x e {a, b} Vx, y G {a, b} \/x e {a, b, Z} \/x e {a, b} Sn(Po,a) =p0 Sn(Po,b) =pi ÔR.(pi,b) =pi Sn(pi,a) =p0 F r = {po} 9.3 Je dána bezkontextová gramatika G = ({S},{a, b},P, S), kde P = { S —> aS i Sb i a} 19 Konstrukce Turingových strojů 10.1 Navrhněte determinstický jednopáskový Turingův stroj rozhodující jazyk L = {anbmcndm \ m,n > 1} 10.2 Navrhněte deterministický jednopáskový TM 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) TM pro jazyk L = {w € {a, b}* | #a(w) = #&(w)} 10.4 Navrhněte TM (determ. nebo nedeterm.) pro jazyk: a) L = {aib1ck | k = ij,i,j € N} b) L = {ww w e {a, b}*} c) L = {ap | p není prvočíslo } d) L = {anw w G {0,1}*, u' je binární zápis čísla n} 20 Vztah TM a gramatik typu O, uzáverové vlastnosti 11.1 Objsaněte rozdíl mezi pojmy TM akceptuje a TM rozhoduje. 11.2 Je daný DTM 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 TM 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