\ ^^f/ ^ Faculty of Informatics \tÁS uí&^ Masaryk University Brno Příklady k cvičením - IB005 a IB102 Formální jazyky a automaty Ivana Černá Jiří Barnat Vojtěch Řehák poslední modifikace 20. února 2006 Formální jazyky, regulární gramatiky 1.1 Jsou dány jazyky L\, L^ nad abecedou {x,y,z}*, kde Li = {xy,y,yx}, L^ = {y,z}. Vypočítejte: a) Li U L2 b) Li n L2 c) Li • L2, L2 • Li d) L2, L2, L2, L2, L2, L2 e) co — L2 1.2 Vypočítejte: a) 0*, 0+, {e}*, {e}+ b) 0U{e}, 0n{e}, 0 n L, {e} n L c) 0-{e},0-L, {e} -{e}, {s} L 1.3 Jsou dané jazyky L\, L^ C {a, b, c, d}*, kde Li = {a, aa, 6a}, L2 = {ba, abc, a, e}. a) Vypočítejte Li U L2. b) Vypočítejte Li n L2. c) Vypočítejte Li • L2. d) Rozhodněte, zda platí Li • L2 = L2 • Li. e) Najděte slovo w £ L\ ■ L2 n L2 • Li. f) Rozhodněte, zda platí Li C Li • L2. Pokud ano, platí tvrzení pro libovolnou dvojici jazyků Li, L2 ? g) Rozhodněte, zda platí • aabaabc £ L\ • baaabc £ L2 • ababc £ L\ h) Popište co — L'2 (komplement jazyka L2). 1.4 Buď L libovolný jazyk, rozhodněte zda platí: a) pro Vi e N platí Ü = {wi | w £ L} b) pro Vi £ N platí w G Ll ^> \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 Li = L4 • Li = {x,y,z}* • L2 = {xyz}* . L3 = {x}* ■ {y}* ■ {z}* . l4 = ({x}* • {yy ■ {zyy . L5 = ({a;,2/}*U{z}*)* • L6 = {a;,y,z}* • {a;} • {x,y,z}* 1.6 Porovnejte (slovně popište) jazyky a rozhodněte zda Li = L3 • Li = {a;,y,z}* 1 L2 = {x,y,z}+ l3 = M* • {vY ■ w* U = {x}* ■ {vY ■ {z}* £5 = ({*}•• M* • {*}*)• Lq = {x,y,zY ■ {x} • {x,y,zY 1.7 Pomocí jazyků Li = {a}, L2 iterace (*,+) a doplňku (co— - {b} a množinových operací sjednocení (U), průniku (fl), konkatenace (•), vyjádřete jazyk, obsahující právě všechna slova, která L3 dokažte, zda platí, nebo neplatí: a) obsahují alespoň 2 znaky a b) mají sudou délku c) začínají znakem a a končí znakem b d) začínají a končí stejným znakem e) obsahují podslovo aba f) splňují b) a c) g) nesplňují b) 1.8 Pro libovolné jazyky Li, L2, a) Li C Li ■ Li b) (Li U L2) ■ L3 = (Li ■ L3) U (L2 ■ L3) c) (Li n L2) ■ L3 = (Li ■ L3) n (L2 ■ L3) d) pro Vi e N platí L\ ■ L\ = (Li ■ L2Y e) LI U L*2 = (Li U L2y f) LI ■ L\ = LI g) (LiUL2)* = (LYL2-(Li)*)* 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 I cAd, cA -> aß Ca, Bd -> Sb j A, Cad -^ ab \ e } b) G = ({S, A},{b,c, a},P, S), kde P={S -> bS \ cS \ aA, A ^ aA \ bA \ cA \ a \ b \ c } 1.10 Jaký jazyk generuje následující gramatika? Diskutujte vhodné označení neterminálů (Soq,Sqi,Siq,Sii G = ({S, A,B, C},{a, b},P, S), kde P = { S -> aA I bB j e, A -> a5 j 6C, C -> aS j 6A } 1.11 Navrhněte regulární gramatiky pro následující jazyky: L L L L L L L L L L L L {a, b, c, d}* {a, b, c,dY{a, b, c,d}*;i {w {w {w {w {w {w {w {w {w {w 2,10,100 w e {a,bY,\w\ > 3) w e {a,bY,\w\ =3fc,fc > 0} w € {a, b,c}*,w obsahuje podslovo abb} wR \w £ {a, &}*} w € {a, b, c}*, první 3 znaky w = poslední 3 znaky w} w € {a, b, c}*,w neobsahuje podslovo abb} w e {a,b,c}*,#a(w) =2k,#b(w) =31 + 1, k,l > 0} w G {0,1,..., 9}*, w je zápis přir. čísla dělitelného 5} w G {0,1,..., 9}*, w je zápis přir. čísla dělitelného 3} w G {0,1,..., 9}*, w je zápis přir. čísla dělitelného 25} 2 Konečné determ. automaty, pumping lemma 2.1 Je dán následující konečný automat: A = ({90,91, 92, 93}, {a, b}, ó, qo, {(73}) ô(q0,á) 8{qua) ô(q2,á) S(q3,a) 93 qi q\ ô(qo,b) S(qi,b) S(q2,b) S(q3,b) 92 9i 92 92 a) Popište jazyk akceptovaný konečným automatem A. b) Diskutujte variantu konečného automatu, kde F = {93,92}; ô(qs,a) = qo c) Uveďte jinou formu zápisu automatu. 2.2 Konstruujte deterministické KA, které rozpoznávají následující množiny a) {a, b, c}5 ■ {a, b, c}* \w\ =2k nebo \w\ = 71; k,l>0} #a(w)=3k;k>0} w obsahuje podslovo abbab} w obsahuje podslovo ababb} 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é KA pro následující jazyk nad abecedou {a,b,c,d} a) L = {a, b}* ■ {c} ■ {aa, b}* ■ {d}+ b) L = {w j w € {a, b, c}*,w neobsahuje slovo babb} c) L = {a, b}* ■ ({cd}+ ■ {d} ■ {a, b}* ■ {c}) • {a, b}+ d) a pro všechny regulární jazyky příkladu 1.11 2.4 Pomocí množin {a}, {&}, {c}, {d} a množinových operací sjednocení (U), průniku (fl), konkatenace (•), iterace (*,+) a doplňku (co—) vyjádřete jazyk akceptovaný automatem: b) {w w £ {a}*; c) {w w £ {a, b} d) {w w £ {a, b} e) {w w £ {a, b} f) {w w £ {a, b} 3 2.5 Co akceptuje následující automat? (#a(w) = #j(w) je špatná odpověď) 2.6 Pomocí věty o vkládání dokažte, že jazyk L není regulární: a) L = {ďV | j > i > 1} b) L = {w | w € {a,b}*; #„(«;) = #&(«>)} c) L = {w ■ wR | w £ {a, &}*} d) L = {an\n = 2{; i > 0} e) L = {aiV\irJ; i,j>0} f) L = {anb^2\n>0} g) L = {éajbk\j < k; i,j,k e N} 4 Minimalizace K A, nedeterministické KA, (M-)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 b ->• 1 2 3 2 5 2 3 3 5 • 1 4 2 2 2 5 3 3 6 4 4 2 <- 5 5 3 <- 6 6 2 a b ->• 1 5 2 2 2 8 3 2 7 <- 4 9 4 5 2 1 6 2 5 • 2 9 4 3 5 1 <- 4 9 4 5 8 5 6 5 4 <- 7 6 9 8 10 10 9 7 9 10 8 1 a b A B A <- B C A C D E D D D -> E A E 3.3 Ověřte, zda KA z příkladu 3.1 je ekvivalentní s následujícím KA zadaným tabulkou a b A A C ->• B D A <- C D A D C D 3.4 Navrhněte nedet. KA 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, b, c }* | w obsahuje podslovo abbc nebo acbca nebo bcabb} c) L = - {w G {a, b, c , d}* | w končí řetězcem aaaa} d) L = ~-{wG {0,1}* | w má čtvrtý symbol od konce 1} e) L = ~-{wG {0,1}* | w končí řetězcem 01011} f) L = = (({0}*-{i}) U({0}+-{l}*-{0})*)* g) L = = (({0} • {0} • {0}*) U ({!}•{!} •{!}*))* 3.5 K daným nedet. KA zkonstrujte det. KA a b c ->• 1 {2,3} {3,4} {1} <- 2 {3} {4} {2} 3 {1,2,3} {1} {3,4} 4 {1} {1} {3,4} a b c ->• 1 {1,2} {1} {1} <- 2 0 {3} 0 3 0 0 {4} 4 {5} 0 0 5 0 {6} 0 6 {7} 0 0 <- 7 0 0 0 3.6 Popište jazyk akceptovaný automatem: -Q 3.7 Kolik různých jazyků rozhodují automaty s jedním nebo se dvěma stavy nad abecedou {x} nebo {x, y}? 3.8 Dokažte, že neexistuje automat se 4 stavy, který akceptuje jazyk: a) L = {w | w e {a, b}*, \w\ > 4} b) L = {w | w e {a, b}*, \w\ = 5fc, fc e N0 } 3.9 Najděte relaci ~ C {a, b}* x {a, &}*, splňující podmínky Nerodovy věty a určete její index. Pro jazyk L: • L = {w | w e {a, b}*, w obsahuje podslovo abb} 3.10 Pomocí Nerodovy věty a posléze pomocí Myhill-Nerodovy věty dokažte, že není regulární: a) L = {an \n = 2i pro i G N0} b) L = {anbm | n < m < 2n; n, m > 0} c) L = {wwR | w G {a, b}+} 3.11 Pomoci MN věty dokážte, že je regulárni: . L = {w G {a, b}* | #a(w) = 3fc pro k G N0} 3.12 Každý jazyk jednoznačně určuje relaci ~l předpisem u ~l v právě když pro každé w platí uw G L <í=> vw G L. Určete index této relace pro jazyky: a) L = L(a*b*ď) b) L = {anbncn | n > 0} 6 Reg. gramatiky a výrazy <^ KA, 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 j aA j b j c, B ^ aB \ bC \ aC \ cA c, 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 j c, X ^ bX \ bS, Y ^ bS \ cZ, Z ^ aS \ b | c } 4.3 Zkonstruujte ekvivalentní gramatiku k automatu: 4.4 Zkonstruujte ekvivalentní gramatiku k automatu: 4.5 K danému automatu s e kroky zkonstruujte ekvivalentní automat bez e kroků. 4.6 K danému automatu s e kroky zkonstruujte ekvivalentní automat bez e kroků. 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í KA a) (ab)*(aa + bb)(a + ab)* b) ((a + b(a + c))* + (b + c))* c) (((a + b)* + c)* + d)* 4.9 K danému KA zkonstruujte ekvivalentní regulárni výraz 4.10 K danému KA zkonstruujte ekvivalentní regulárni výraz 4.11 Pomocí regulárních výrazů popište nasi, jazyky: a) L = {w € {a, b}* \ w končí na ab} b) L = {w e {a, b}* | #a(w) = 2k,k> 0} c) L = {w € {a, b}* \ w začíná a končí stejným symbolem } d) L = {w e {a, 6}* | \w\ =2k,k> 0} 4.12 Ukažte, jaký je vztah mezi 7?. 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) M2, která obsahuje všechny konečné jazyky a je uzavřená vzhledem k sjednocení, průniku a komplementu (U,fl,co— ). c) M3, která obsahuje všechny konečné jazyky a je uzavřená vzhledem k sjednocení, průniku a mocnině (U,n,n). 8 Uzáverové vlastnosti TZ 5.1 Rozhodnete, zda platí: jsou-li jazyky Li,Z/2, £3,... regulární, pak i jazyk 00 O «=i 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ť Li, L2 jsou neregulární jazyky nad abecedou {a, b}. Dokažte nebo vyvraťte, zda je či není regulární: a) Li n L2 b) Li U L2 c) Li \ L2 d) Li • L2 e) LI f) co — Li 5.4 Nechť Li je regulární a Li n L2 je neregulární jazyk. Platí, že jazyk L2 je nutně neregulární? 5.5 Platí následující implikace? a) Li je regulární, L2 je neregulární =>• Li n L2 je neregulární b) Li je regulární, L2 je neregulární =>• Li n L2 je regulární c) Li je regulární, L2 je neregulární =>• Li \ L2 je neregulární d) Li je regulární, L2 je neregulární =>• Li \ L2 je regulární e) Li je regulární, L2 je neregulární =>• L2 \ Li je neregulární f) Li 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 © L2 = {u ■ v j u, v £ (Li U L2)} Dokažte, že jestliže jsou jazyky Li a L2 regulární, pak i jazyk Li 0 L2 je regulární. Dále najděte dva takové neregulární jazyky Li a L2, aby jazyk Li 0 L2 byl regulární. 5.7 Nechť L je regulární jazyk. Dokažte, že jazyky L# jsou regulární: a) LŘ = {v j existuje u takové, že u.v £ L} b) LŘ = {w j existuje x, y, z takové, že y £ L a w = xyz} 5.8 Def: Homomorfismus h : S* —> A* je daný předpisem: h(s) = s h(u.v) = h(u).h(v) pro všechny u,v € X* 9 Def: Nechť L je jazyk, pak h(L) = {w \ w = h(u), kde u £ L} Def: Inverzní Homomorfismus: h-Hy) ={xGX*\h(x)=y} h-^L) = {ies* h(x) a} Příklad h{a) = 01 h(b) = 011, pak • /i(ató) = 01011011 • /i-1(0101011) = {aab} • /i-^OOlO) = 0 • pokud navíc h(c) = e pak h~x(01011) = L(c*ac*bc*) Ukažte, že 7?. je uzavřena na h, h~x. 5.9 Nechť je dána abeceda {a, b, c} a homomorfismus h; h(a) = ac, h(b) = cb, h(c) = ca. Určete: • h(aabc), h(cbaa) • h~1{cccaaccb),h~1{accba) • h(L),L = {anbncn | n > 0} 5.10 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 = {w £ {a*,b*} | #„(«;) = #6(W)} • h~1{L),L = {w £ {a*} | H = 2k,k£ N} 5.11 Dokažte nebo vy vraťte . /i(Li • L2) =/i(Li) •/i(L2) . h(L1UL2)=h(L1)Uh(L2) . /j((Lx • L2)ß) = h(L*) • /!(L«) . /i(LinL2)=/i(Li)n/i(L2) . /i(/i(L)) = /i(L) • h-^hiL)) =L . hr1{L1-L2) = hr1{L1)-h-1{L2) . /i"1^! U L2) = h-^Li) U /i"1^) . /i"1^! n l2) = h-^Li) n h-1^) 10 Bezkontextové gramatiky 6.1 Co generují tyto gramatiky? G = {{S, B, A},{a, b},P, S), kde P = { S -> aB | bA \ e, A -> aS j MA, S -> 65 j oßß } G = ({S, A},{a, b},P, S), kde P = { 5 -»■ aAS | a, A -»■ &a j Ste} 6.2 Pro následující gramatiku G = ({S, A,B},{a, b},P, S), kde P = { 5 -> AaS | SaA, A -> AS j 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í charakteristikcé 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 = { S -> SSS | 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 > í}. 6.7 Navrhněte gramatiku pro jazyk L = {alVck \ i, j, k > í,i = j nebo j ^ k}, je gramatika jednoznačná? 6.8 Najděte ekvivalentní redukovanou gramatiku k této gramatice: G = {{S,A,B,C,E,F,D},{a,b,c],P,S), kde P = { S -> aA \ bB, A -> aAB j aa \ AC \ AE, B -> bBA j bb j CB j BF, C -> DE, D -> cc | DD, E ^ FF j FE, F -> £c£ } 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. 11 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 bezkontextove gramatiky pro jazyky: a) L = {wwR | w £ {a, b, c}*} b) L = {w | w G {a, b, c}* ,w = wR} c) L = {a3n+2b2n | n > 2} d) L = {a™^™-^™-1 | n > 0,m > 1} e) L = {a"&mcm(i™ |n,m>0} f) L = {uxv \ u,x,v £ {a, b, c}*, uv = (uv)R, x = canb2nc, n > 0} g) L = {w | w e {a, &}*, #aH > #6H} h) L = {w | W e {a, &}*, #„(«;) = 2 * #6(W)} 12 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 -> ABC, A -> AbA | BC, B ^ bB \ b | cL?6Aa | e, C -> cD j c j A& j e, Ľ -> 555 j & } 7.2 Odstraňte e-pravidla: G = ({S, A,B, C, D},{b,c},P, S), kde P = { S -> A5C, A -> Ab | SC, B ^ bB \ b \ Ab \ e, C -> cD j c j Ac j e, Ľ -> 555 j c5Ac} 7.3 Odstraňte e-pravidla: G = ({5, X, F, Z},{1,0},P, 5), kde P = { 5 -> IX | Fl | XZ, x -> OYZí | six | r, r -> 1 j XI j e, Z -> 5Z í 0 í e } 7.4 Význam konstrukce množin Ne na příkladu G = ({A,B, C},{a, b,c},P, A), kde P = { A -> SC | a | e, B ^ aB ACC j b, C ^ cC \ AA j c} 7.5 Odstraňte jednoduché pravidla. Diskuse o významu Na-G = ({S,X, Y, A,D,B, C},{b, a},P, S), kde p = = {S -> X 1 y, A -> bS 1 A D —>• 6a, B —>• 5a 1 a, X -> aA5 1 c, C -> aD 1 s, Y -> 5S&} 7.6 Převeďte do Chomského normálni formy G = ({S, A,B},{a, b},P, S), kde p = { 5 -> 5a565 | aAa | &L?&, A ^ aA | aaa | B | e, B ^ Bb \ bb \ b } 7.7 Převeďte do Chomského normálni formy G = ({5, if, L},{0,1},P, 5), kde P = { 5 -> OLH | ILO | e, íf -> ífíf j OLH j Lif | e, L ^ LL \ ILO \ HL \ e} 13 7.8 Navrhněte gramatiku v CNF: a) L = {a2ib3icj | i > í,j > 0} b) L = {wwR | w £ {a, b}*} 7.9 Nechť G je gramatika v CNF. Nechť w G L(G), \w\ = n. Jaká je minimální a maximální délka odvození slova w v Gl 7.10 Odstraňte levou rekurzi a transformujte do GNF G = ({S, A,B},{a, b},P, S), kde P = { S -> Aa \ Bb \ aaA | SaA | SbB, A -> AA6 j a& j SBb, B ^ Bbb j 555 j bAb } 7.11 Odstraňte levou rekurzi a transformujte do GNF G = ({S, A,B},{1,0},P,S), kde P = {S -> Al | 0 | 15, A -> 5S0 j 10 j S50, B ^ OB j SIS j 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 -^ SaS} 7.13 Odstraňte levou rekurzi a transformujte do GNF G = ({S,T},{t, s},P, S), kde P = { 5 ->• TTí | Tí | TS | s, T ->• SsT j TsT j t } 7A4 Transformujte do Greibachové NT. Výslednou gramatiku převeďte do 3GNF. G = {{A,B, C, D},{a, b],P, A), kde P = { A -> BC, B -> CD | AS, C -> Aa | 6, D ^ bA \ DD} 7.15 Dokažte, že následující jazyky nejsou bezkontextove a) L = {wcw I w € {a, 6}*} b) L = {anbncn | n > 1} c) T = {a"&mc"íf™ |n,m> 1} 14 Zásobníkové automaty 8.1 Daný ZA A = ({q0, qi, q2, q3, q4}, {a,b, c, d}, {Z, A}, ó, q0, Z, {q4}) ó(q0,a,Z) = {(qo, AZ)} ó(q0,a,A) = {(go, AA)} ô(q0,b,A) = {(qi,s)} ô(qi,b,A) = {(qi,e)} ô(qi,e,A) = {(q2,A),(q3,A)}ó(q2,c,A) = {(q2,e)} ô(q3,d,A) = {(q3,e)} ô(q2,e,Z) = {(q4,Z)} ó(q3,e,Z) = {(q4,Z)} • Načrtněte stavový diagram ZA A. • Naznačte 4 různé výpočty na vstupu a4b2c (stačí na obrázku). • Popište jazyk L(Ä). 8.2 Je daný ZA A = ({q0,qi,q2,q3,q4},{a,b,c,d},{X,Y, Z},ó,q0, Z,{q2,q4}), kde ó(q0,a,Z) = {(q0,X)} ó(q0, a, X) = {(q0, XX), (q4, YX)} ö(q1,a,Y) = {(q1,YY)} ö(q4,b,Y) = {(q2,e)} ô(q2,b,Y) = {(q2,e)} ô(q2,c,X) = {(q3,e)} ó(q3,c,X)={(q3,e)} ó(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 ZA (akceptující koncovým stavem nebo prázdným zásobníkem) pro jazyky: a) L = {aiV\iŕJ, i,j>0} b) L = {w | w e {a, b}*; w = wR} c) L = {a3nb'2n | n > 1} d) L = {a3"^2""1 | n > 1} e) L = {w | w e {a, b, c}*; #a(w) = #f,(w)} f) L = {w | w e {a, b, c}*; #a(w) ^ #6(w)} g) L = {akV \ll} i) L = {éWé | i, j > 1} U {akbkcm | k, m > 1} j) L = {aklbak2b.. .bakr | r > 1, fcj > 1 (i = 1,... ,r; existuje p,s : p ^ 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(Ä). ö(qo,a,Z)={(q0,AZ)} ô(q0,a,A) ={(qo,AA)} ô(q0,b,A) ={(qi,e)} 8.5 Daný ZA A = ({q}, {(,)}, {Z, L, P},ô,q, Z,fy) akceptující prázdným zásobníkem transformujte na ekvivalentní automat akceptující koncovým stavem. Určete L(A). 15 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 abababaa. G = ({S, A,B},{a, b},P, S), kde P = { S -> e | abSA, A -> AaB j aB \ a, B -> aSS j bA } 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ý ZA A = ({qo,qi,q2},{a,b,c},{A,B,C},ô,qo,A,fl)}) akceptující prázdným zásobníkem transformujte na ekvivalentní bezkontextovou gramatiku. ô(q0,a,A) = {(q1,B)} S(qi,c,A)={(q2,e)} ö(q2,e, B) = {(q2,e)} S(q0,b,A) = {(qi,AB)} S(qi,a,B) = {(q0,ABC)} ô(q2,e,C) = {(q0,A)} 16 Uzáverové vlastnosti CFL 9.1 O každé z následujících implikací rozhodněte zda je pravdivá a) L\, L2 bezkontextové =>• Li U L2 je kontextový b) Li bezkontextový A Li n L2 není bezkontextový => L2 není bezkontextový c) Li regulární A L2 bezkontextový =>• co — (L\ PI L2) bezkontextový d) Li konečný A L2 bezkontextový =>• co — {Li n L2) bezkontextový 9.2 Jsou dané jazyky L = {wwR j w G {a, b}*} R = L((a*b+a)* + a*) Navrhněte ZA pro jazyk Lf] R óL(qo,x, Z) = {(q0,xZ)} Vx e {a, 6} ÖL(qo,x,y) = {(qo,xy)} Vx,y G {a,b} ÔL(qo,£,x) = {(qiix)} Vx G {a,b,Z} ÖL(qi,x,x) = {(qi,e)} Vx G {a, b} 6L(que,Z) = {(q2,Z)} Fl = {92} 9.3 Je dána bezkontextová gramatika G = ({S},{a, b},P,S), kde P = { S -> aS j Sb I a } a) Má tato gramatika vlastnost sebevložení? b) Má jazyk generovaný gramatikou vlastnost sebevložení? c) Je jazyk 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 Li takto: a) L\ = {x I 3y G {a, b}*; xy G L} b) L\ = {x I 3y G {a, b}*; yx G L} Dokažte, že L\ je taky bezkontextový. ÔR(Po,a) =po ôn(po,b) =pi ôn(pi,b) =pi ôn(pi,a) =po F r = {po} 17 Konstrukce Turingových strojů 10.1 Navrhněte determinstický jednopáskový Turingův stroj rozhodující jazyk L = {ánbmcndm \ 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) = #í>(w)} 10.4 Navrhněte TS (determ. nebo nedeterm.) TS pro jazyk: • L = {aibjck | k = ij,i,j £ N} • L = {ww | w e {a, b}*} • L = {ap | p není prvočíslo } • L = {ánw | w € {0,1}*, w je binární zápis čísla n} 18 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: S(q, >) = (q, >,R) S(q, a) = (p, A, R) ó(p,b) =(q,a,L) S(q,U)=(p,A,R) <*(í>> U) = (?> a: L) %> a) = (q 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á • R je regulární, L je rekurzivně spočetný => R <~) L je regulární • L je rekurzivní =>• co-L je rekurzivní • L je rekurzivní =>• L* je rekurzivní (Zkuste neformální důkaz) • L je kontextový =>• co-L je rekurzivní (Zkuste neformální důkaz) 11.4 Navrhněte gramatiky pro následující jazyky: • {w\w £ |a,6,c}*,#a(w) = #ř,(w) = #c(w)} • {ww I w £ {a, b, c}*} • {a"6"cn | n > 0} • {a™ | 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? 19 Funkce FIRST a FOLLOW Definice: Buď dána gramatika G = (N, S, P, S). Funkce FIRSTi a FOLLOWi jsou definovány následovně: FIRSTí-.CĽUN)* ^ 2EU^> FIRSTxia) = {w G S U {e} | (a =^* w A \w\ = 0) V (a =^* wu A \w\ = 1; u G £*)} FOLLOW! : N i-> 2Suí£> FOLLOWi{A) = {w G SU{e} | S ^* uAa, w G FIRST^a) ; u G £*, a G (SUiV)*} Poznámka: Pozor na typ argumentu u jednotlivých funkcí. Funkce FIRSTi(a) bere jako argument řetězec terminálů a neterminálů (a £ (S U N)*), narozdíl od funkce FOLLOWi(A), jejíž argumentem je vždy právě jeden neterminál (A G N). Běžně se používají zkrácené zápisy funkcí, FIi(a) pro FIRSTi(a) a FOi(A) pro FOLLOW^ A). 12.1 Určete FI\{A) pro gramatiku G = ({A},{a,b},P, A), kde P = { A ->• Aa, A -»■ & } 12.2 Vypočítejte Fh(S), Fh(BBb), Fh{SAcB), FO^A), FOi(S), FOi(B) a FOi(C) pro následující gramatiku: G = ({S, A,B, C},{a, c, b, e, d},P, S), kde P = {S ^ aAc \ B, A -> aA j 65Ce | e, B ^ aC j e, C ^ d \ s } 12.3 Vypočítejte FOi(X), kde V e {5, A, J?, C, Ľ} je-li zadána tato gramatika: G = ({5, A,S, C, D},{a, &, d, c,x,y, z},P, S), kde P = { S -> aABbCD | e, A -> ASd j e, S -> SAc j xC | e, C ^ Sy \ Cz \ e, D -> aSD j e } 12.4 Vypočítejte FO\(X), kde V G {S, A, B, C, D} je-li zadána tato gramatika: G = ({S, B, A,D, C},{a, c, b, d},P, S), kde P = { S -> aScß, A -> aA | Aa, B -> DAc j bA, C ->• c£?c | aaJJ, D ^ d \ dC) Věta: Gramatika je LL(1), právě když pro všechny neterminály A G N, & pro každá dvě různá pravidla A ->• ß, A ->• 7 platí: F/i(/3 • FOi(A)) n F Ji (7 • FOi(A)) = 0 12.5 Ověřte, zda následující gramatika je LL(1), pokud ano sestrojte LL(l) analyzátor a proveďte analýzu slova bbac. G = ({S, A,B},{a, b,c},P, S), kde P = { S -> aAb | bB | c, A -> e j aA, B ^ e j 6AcA } 20 12.6 Ověřte, zda následující gramatika je LL(1), pokud ano sestrojte LL(1) analyzátor a proveďte analýzu slova baa. G = ({S,X, Y},{b, a},P, S), kde P = { S -+ X, X -> Y | bYa, Y -> a j s } 12.7 Ověřte, zda následující gramatika je LL(1), pokud ano sestrojte LL(1) analyzátor a proveďte analýzu slova bbbba. G = ({S, A,B},{a, b},P, S), kde P = { S -> aAaS | &A&B, A -> a j &&, B ^ bB \ A } Poznámka: V jednoduché L L (í) gramatice začínají všechny pravé strany pravidel terminálem, pravidla se stejnou levou stranou začínají různým terminálem. 12.8 Rozmyslete si jak probíhá analýza jednoduchých LL(Í) gramatik. 12.9 Navrhněte LL(Í) jednoduchou gramatiku pro jazyk zapsaný následující množinou a) {ln 2 0" lm 2 0m | n > 0, m > 0} b) {ln 2 0" lm 2 0m | n > 0, m > 0} 12.10 Najděte jazyk, který se nedá generovat žádnou jednoduchou LL(1) gramatikou. 21