Faculty of Informatics 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\, L2 nad abecedou {x,y,z}*, kde L\ = {xy,y,yx}, L2 = {y,z}. Vypočítejte: a) LiUL2 b) Lx n L2 c) Li ■ L2, L2 ■ Li d) L2, L\, L\, L\, L*2, L2 e) co — L2 1.2 Vypočítejte: a) 0*, 0+, {e}*, {e}+ b) 0 U jej, 0 n jej, 0 n L, {e} n L c) 0-{e|, 0-L, {£}•{£}, {£}•£ 1.3 Jsou dané jazyky Li,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 Li n L2. c) Vypočítejte Li ■ L2. d) Rozhodněte, zda platí L\ ■ L2 = L2 ■ L\. e) Najděte slovo w E L\ ■ L2 n L2 ■ L\. f) Rozhodněte, zda platí L\ C L\ • L2. Pokud ano, platí tvrzení pro libovolnou dvojici jazyků Lx,L-2 ? g) Rozhodněte, zda platí • aabaabc e L2 • baaabc € L\ • ababc e Ĺ2 h) Popište co — L2 (komplement jazyka L2). 1.4 Buď L libovolný jazyk, rozhodněte zda platí: a) pro Vi £ N platí L8 = {w8 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\ = L 4 • Li = {x,y,z}* • L2 = {xyz\* . L3 = {x}* ■ {y}* ■ {z}* . U = ({x}* ■ {y}* ■ W)* . L5 = ({x,y\*U{z\*y • 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}* I • L2 = {x, y, z}+ . L3 = {x\* ■ {y}* ■ {z}* . L4 = {x}* ■ {y}2 ■ {z}* . L5 = (w*-w*-w*r • L6 = {x,y,zY ■ {x\ ■ {x,y,zY 1.7 Pomocí jazyků L\ = {a}, L2 = {b} a množinových operací sjednocení (U), průniku (fl), konkatenace (•), iterace (*,+) a doplňku (co— ) vyjádřete jazyk, obsahující právě všechna slova, která obsahují alespoň 2 znaky a 1.8 Pro a b c 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í: L\ C L\ ■ L2 (Li UL2)-L3 = (L1- L3) U (L2 ■ L3) (Li HL2) -L3 = (Li -L3) n (L2 -L3) pro Vi e N platí L| ■ L\ = (Lx ■ L2) L\\JL*2 = (L1\JL2)* ^1 - = ^1_ (Li U L2)* = (L* • L2 ■ (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 \ cAd, cA 4 aB j Ca, Bd ^ Sb \ A, Cad —> ab | e } b) G = ({S, A},{b, c,a},P, S), kde P = { 5 -> &5 I cS I aA, 4 -> ai j y I d I a I b | c} 1.10 Jaký jazyk generuje následující gramatika? Diskutujte vhodné označení neterminálů (Sqq, Sqi, Siq, Sh). G = ({S, A, B, C},{a, b},P, S), kde P = { S ->• aA j bB I e, ->■ aS bC, B aC bS, C ->■ aB bA\ 1.11 Navrhněte regulární gramatiky pro následující jazyky: a) L = {a, b, c, d}* b) L = {a, b, c, ďp{a, b, c, d}*; i = 2,10,100 c) L = {w w e {a, bY, M > 3} d) L = {w w G {a, by, H =3k,k> 0} e) L = {w w 6 {a, 6,c}*,w obsahuje podslovo a&&} f) L = {w wÄ 1 w G {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,cy,w neobsahuje podslovo abb\ i) L = {w w £ {a, b, c}*, #a(w) = 2fc, = 31 + 1, fc, i > 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}*, u> je zápis přir. čísla dělitelného 3} 1) L = {w w 6 {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 = ({qo, qi, q2, {a, b}, ô, qo, {(73}) S(q0,a) = gi S(q0,b) = q2 ô(qi,a) = q3 ô{q1,b) = q1 %2,a) =
  • 0} c) {w \ w E {a, b\* #a(w)=?,k;k>Q\ d) {w \ w e {a, b}* e) {w \ w G {a, b}* w obsahuje podslovo abbab} w obsahuje podslovo ababb} f) {w \ w E {a, b}* w neobsahuje podslovo abbab} g) {a, b}* ■ ({c, d} U ({d} ■ {a, b}* ■ {c})) • {a, b}+ h) (W U {6}-(W ■{&}*•{) je špatná odpověď) 2.6 Pomocí věty o vkládání dokažte, že jazyk L není regulární: a) L = {aV | j > i > 1} b) L = {«;|«,e{a,6r; #„(«;) = c) L = {w • wň w É {a, 6}*} d) L = {an\n = 2*"; i > 0} e) L = {a*V|i^j; j,j >0j f) L = {a"6("!^|n > 0} g) L = {ďajbk\j < k; i,j,k £ N} 4 Minimalizace KA, 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) a b -> 1 2 3 2 5 2 3 3 5 <- 4 12 2 1 5 2 -> 1 4 2 2 2 8 2 2 5 3 2 7 3 3 6 <- 4 9 4 4 4 2 5 2 1 <- 5 5 3 6 2 5 <- 6 6 2 <- 7 8 6 8 2 4 9 8 9 a 6 a 6 1 3 1 A B A -> 2 9 4 <- B C A 3 5 1 C D E <- 4 9 4 D D D 5 8 5 E A E 6 5 4 <- 7 6 9 8 10 10 9 7 9 10 8 1 5 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 £ {a, b, c, d}* | w obsahuje podslovo abbc nebo bba nebo aba} b) L = {w G {a, 6, c}* | u; obsahuje podslovo abbc nebo acbca nebo bcabb} c) L = {u; e {a, 6, c, 1 {2,3} {3,4} {1} -> 1 {1,2} {1} {1} <- 2 {3} {4} {2} <- 2 0 {3} 0 3 {1,2,3} {1} {3,4} 3 0 0 {4} 4 {1} {1} {3,4} 4 {5} 0 0 5 0 {6} 0 6 {7} 0 0 f- 7 0 0 0 3.6 Popíš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 {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 £ {a, b}*, \w\ = 5fc, k £ N0} 3.9 Najděte relaci ~ C {a, b\* x {a, b\*, splňující podmínky Nerodovy věty a určete její index. Pro jazyk L: • L = {w | w £ {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 e N0\ b) L = {anbm | n < m < 2n; n, m > 0} c) L = {wwH | w G {a, b}+} 3.11 Pomocí MN věty dokažte, že je regulárni: • L = {w e {a, b}* | #a(w) = Sk pro k G N0\ 3.12 Každý jazyk jednoznačně určuje relaci ~£ předpisem u ~L v právě když pro každé w platí uw G L <4> uw € L. Určete index této relace pro jazyky: a) L = L(a*b*ď) b) L = {anbncn | n > 0} 5 Reg. gramatiky a výrazy <^> KA, e 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 je, B ^ aB \ bC \ aC \ cA | c, C a aA | &5j 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 je, X ^ bX \ bS, Y -»• 65 | cZ, Z a5 | 6 TcT 4.3 Zkonstruujte ekvivalentní gramatiku k automatu: 6 a c 4.4 Zkonstruujte ekvivalentní gramatiku k automatu: a d 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} 7 4.8 K danému regulárnímu výrazu zkonstruujte ekvivalentní K A a) (ab)*(aa + bb)(a + ab)* b) ((a + b(a + c))* + (b + c))* c) (((a+ 6)* +c)* +d)* 4.9 K danému KA zkonstruujte ekvivalentní regulárni výraz 4.10 K danému K A zkonstruujte ekvivalentní regulárni výraz c c 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 £ {a, &}* | #a(» = 2k,k> 0} c) L = {w G {a, &}* | w začíná a končí stejným symbolem } d) L = {w £ {a, b}* | \w\ =2k,k> 0} 4.12 Ukažte, jaký je vztah mezi 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) M2, 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, H,™). 5 Uzáverové vlastnosti 1Z 5.1 Rozhodněte, zda platí: jsou-li jazyky Li, L2, L3,... regulární, pak i jazyk 00 je regulárni jazyk. 5.2 Najděte takovou posloupnost regulárních jazyků L\, L2,L%,... aby jazyk nebyl regulární. 5.3 Nechť L\,L2 jsou neregulární jazyky nad abecedou {a, b}. Dokažte nebo vyvraťte, zdaje či není regulární: a) Li n L2 b) L1UL2 c) Li \ L2 d) Li • L2 e) Lí f) co — L\ 5.4 Nechť Li je regulární a Li fl L2 je neregulární jazyk. Platí, že jazyk L2 je nutně neregulární? 5.5 Platí následující implikace? a) Li b) Li je regulární, L2 je regulární, L2 je neregulární = je neregulární = >LX >U fl L2 je neregulární fl L2 je regulární c) Lx je regulární, L2 je neregulární = >LX \ L2 je neregulární d) Li je regulární, L2 je neregulární = >Lx \ 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 \ L\ je regulární 5.6 Def: operace 0 rozšířeného sjednocení dvou jazyků takto: Li 0 L2 = {u ■ v I u, 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 Li © L2 byl regulární. 5.7 Nechť L je regulární jazyk. Dokažte, že jazyky LŘ jsou regulární: a) L# = {v I existuje u takové, že u.v G L} b) = {w I existuje x, y, z takové, že y G L a w = xyz} 5.8 Def: Homomorŕismus h : E* —>■ A* je daný předpisem: /i(e) = e h(u.v) = h(u).h(v) pro všechny u,v £ S* Def: Nechť L je jazyk, pak h(L) = {w | w = h(u), kde u e L\ Def: Inverzní Homomoríismus: h-^y) = {x G E* I h(x)=y} /i-i(L) = {x G E* j /i(x) G L} Příklad /i(a) = 01 = 011, pak • h(abb) = 01011011 • h-1 (0101011) = {aab} • /i-^OOlO) = 0 • pokud navíc h(c) = e pak h^1 (01011) = L(c*ac*bc*) Ukažte, že 1Z je uzavřena na h, /i-1. 5.9 Nechť je dána abeceda {a, b, c} a homomoríismus 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 = {anbnď \ n > 0} 5.10 Nechť je dána abeceda {a, b, c\ a homomoríismus h; h{a) = aa, h(b) = ba, h(c) = a. Určete: • h^1 (aabaaabaa) • h(L),L = {w£{a*,b*} | #aH = #6H} • h~1(L),L = {w G {a*} | H = 2fc, k G 5.11 Dokažte nebo vyvraťte • -L2) = ft(Li) -^(L2) • /i(Li UL2) = h{L1)iJh{L2) . • L2)«) = ) ■ ft(L^) • /i(Li nL2) = /i(Lx) n/i(L2) • /i(/i(L)) = /i(L) • hrl(h(L)) = L . h-1(L1-L2) = h-1(L1)-h-1(L2) • /i-1(L1ui2) = /r1(i1)u/í-1(L2) • /i_1(Li n L2) = /;_1(Li) n /i_1(L2) IU Bezkontextové gramatiky 6.1 Co generují tyto gramatiky? G = ({S,B, A},{a, b},P, S), kde P = { S aB j b A j e, A -> aS \ bAA, B -> bS | aBB } G = {{S,A\,{a,b\,P,S), kde P = { S 4 aAS | ä, A -> ba | Sba } 6.2 Pro následující gramatiku G = {{S,A,B\,{a,b\,P,S), kde P = { S AaB | BaA, 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 = {wwH \ w e {a, b}*} U {ak \ k > 1}. 6.7 Navrhněte gramatiku pro jazyk L = {alWck \ i, j, k > 1, 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 TbB, A aAB j aa | AC \ AE, B j bb \ CB \ B f, D ^ cc | DD, e ff f ->■ EcE } 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. n 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 = {™Ä I u; G {a, 6, c}*} b) L = {w | w £ {a, b,c}*,w = wH} c) L = {a3n+'2b2n | n > 2} d) L = {a"6"&™+1c™-1 | n > 0,m > 1} e) L = {anbmcmdn | n, m > 0} f) L = {uxu | m, x, v e {a, 6, c}*, uv = (uv)H, x = canb2nc, n > 0} g) L = {w \ w G {a,b}*,#a(w) > #b{w)} h) L = {w\we{a, 6}*, #„(«;) = 2 * 12 Normální formy CFG, pumping lemma pro CFL 7.1 Odstraňte e-pravidla: G = ({5, a, P, C, P},{6,c,a},P,S), kde P = { 5 -> ABC, a -»• aďa nsc; B ^ bB \ b | cBMa | e, C -t cD je j A6 je, £> -»■ 555 j 6 } 7.2 Odstraňte e-pravidla: G' = {{S,A,B,C,D\,{b,c\,P,S), kde P = { 5 -> ABC, a -»• .46 nsc; B ^ bB \ b \ Ab \ e, C -> cD je j Ac j e, £> -»■ 555 j c5Ac} 7.3 Odstraňte e-pravidla: G = {{S,X,Y,Z\,{1,0\,P,S), kde p = { 5 ii | yi yiiz, x -»• oyzí j 5ix i y, F 1 j XI j e, Z -»■ 5Z j 0 je} 7.4 Význam konstrukce množin na příkladu G = ({A,B,C},{a,b,c},P,A), kde p = { a -> PC' i a B ^ aB j acc | 6, 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 = { 5 -» x | r, a -> 65 Ľ -> ba] P —> 5a | a, X -> aA5 j C, C -> aD j 5, y -»■ 5P6} 7.6 Převeďte do Chomského normálni formy G = ({5,A,P},{a,6},P,5), kde P = { 5 -> 5a565 | «Aa | 6P6, A oA | aaa \ B | e, B -> Bb j 66 j 6 } 7.7 Převeďte do Chomského normálni formy G = (|5,P,P},{0,1},P,5), kde P = { 5 Oí/l | 1L0 | e, H -> HH | Offl | PffJ^ L -> LĹ | 1P0 M | e] 7.8 Navrhněte gramatiku v CNF: a) L = {a2ib3ici \ i > 1, j > 0} b) L = {wwR I w e {a, b}*} 7.9 Nechť G je gramatika v CNF. Nechť w e L(G), \w\ = 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 | aaA \ SaA | SbB, A -> AAb | ab TBBb, B ^ Bbb | 555 | bAb j 7.11 Odstraňte levou rekurzi a transformujte do GNF G = ({S,4,B},{l,0},P,S)7Edi p = { s ->■ | o | íg; A -»• 5S0 I 10 I S BO, B ^ 0B 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 ja, F SaS } 7.13 Odstraňte levou rekurzi a transformujte do GNF G = ({S,T},{t,s},P,S), kde P = { S -> TTí | Tí | TS | s, T -> SsT j TsT | t } 7.14 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 | AB, C D č>A | Ľ Ľ ) 7.15 Dokažte, že následující jazyky nejsou bezkontextové a) L = {wcw | w £ {a, b}*} h) L = {anbncn | n > 1} c) L = {a"6mc"dm | ra,m > 1} 14 Zásobníkové automaty 8.1 Daný ZA A = ({q0, qx, q2, q3, q4}, {a, b, c, d}, {Z, A}, ô, q0, Z, {q4}) ó{q0,a,Z) = {(q0,AZ){ ó(q0,a,A) = {(q0,AA){ ó(q0,b,A) = {(gi,e)} %i,M) = {{que)\ ô(que,A) = {(q2,A),(q3,A)}ó(q2,c,A) = {(q2,e)} ô(q3,d,A) = {(q3,e)} S(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 (A). 8.2 Je daný ZA A = ({q0, qi,q2,q3,q4}, {a, b, c, d}, {X, Y, Z}, ô, q0, Z, {q2,q4}), kde 6{q0,a,Z) = {(q0,X)} 6{q0, a, X) = {{q0, XX), (qu Y X)} ô{q^,Y) = {(gi,rr)} ó(qub,Y) = {(q2,e)\ 6(q2,b,Y) = {(q2,e){ ó(q2,c,X) = {(q3,e)\ Sfac, 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 = {a!¥ \ i^j, i, j > 0} b) L = {w | w e {a, b}*; w = wH} c) L = {a3nb2n | n > 1} d) L = {a3»+^»-i | n > i} e) L = {w | w £ {a, b, c}*; #a(w) = #b(w)} f) L = {w | w £ {a, b, c}*; #„(«;) jí #b(w)} g) L = {akb> | 1 < j < k < 2j} h) L = {an+mbm+pď+n | m^^n > 1} i) L = {(ŕV6> | 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 = ({(70)91}! {i, &}, {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)\ ó(q0,a,A) = {(q0,AA){ ó(q0,b,A) = {(gi, e)} 8.5 Daný ZA A = ({■ AaB j aB [li, 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 = ({go, • L2 není bezkontextový c) L\ regulární A L2 bezkontextový co — (Li n L2) bezkontextový d) L\ konečný A L2 bezkontextový co — (L\ fl L2) bezkontextový 9.2 Jsou dané jazyky L = {wwR I w € {a, b}*} R = L{{a*b+a)* + a*) Navrhněte ZA pro jazyk L Cl R 6L(q0,x,Z) = {(q0,xZ)\ Vx E {a, b\ SR(p0,a) = p0 ôL(q0,x,y) = {(q0,xy)} Mx,y G {a,b} SR(p0,b) = px óL(q0,e,x) = {(gi,x)} Vx e {a, b, Z} SR(p1,b)=p1 8L(qi,x,x) = {(q1,e)f Vx E {a, b\ 6R(p1,a) = p0 óL(qi,e,Z) ={{ 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 L\ takto: a) Li = {x I 3y E {a, b}*; xy E L\ b) Lx = {x j 3y e {a, b}*; yx E L} Dokažte, že L\ je taky bezkontextový. 17 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ý 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={idě {a, b\* | #a(w) = #&(?£>)} 10.4 Navrhněte TS (determ. nebo nedeterm.) TS pro jazyk: • L = {éWc} | k = e N} • L = {ww I w e {a, b\*\ • L = {ap | p není prvočíslo } • L = {anw | w £ {0, l}*,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: 6(q,>)=(q,>,R) S(q,a) = (p,A,R) S(p,b) =(q,a,L) S(q,U) = (p,A,R) ô(p,U) = (q,a,L) ô(q,a) = (qaccept, A, R) Kde > 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 zdaje pravdivá • R je regulární, L je rekurzivně spočetný R n 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,b,c}*,#a(w) = #b(w) = #c(w)} • {ww I w G {a, b, c}*\ • {anbncn | 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ľ 1$ Funkce FIRST a FOLLOW Definice: Buď dána gramatika G = (N, E, P, S). Funkce FIRSTi a FOLLOWi jsou definovány následovně: FIRSTi : (E U TV)* i-> 2Suí£> FIRSTi(a) = {w e E U {e} | (a =>* w A \w\ = 0) V (a =>* wu A |w| = 1; u e E*)} FOLLOVFi : TV h+ 2eu^> PC-PPOWi(A) = {w e E U {ej | 5 ^* wAa, w G FIRSTi(a) ; u e E*, a e (E U TV)*} Poznámka: Pozor na typ argumentu u jednotlivých funkcí. Funkce FIRST\{a) bere jako argument řetězec terminálů a neterminálů (a € (S U N)*), narozdíl od funkce FOLLOWi(Á), jejíž argumentem je vždy právě jeden neterminál (A e N). Běžně se používají zkrácené zápisy funkcí, FI\(a) pro FIRSTi(a) a FOi(A) pro FOLLCWi(A). 12.1 Určete FI\(A) pro gramatiku G = {{A\,{a,b\,P,A), kde P = { A -> Aa, A -> 6 } 12.2 Vypočítejte P/i(5), Fh(BBb), Fh(SAcB), FOi(A), FO^S), FOi(P) a FOi(C) pro následující gramatiku: G = {{S,A,B,C\,{a,c,b,e,d\,P,S), kde P = { 5 -> aAc | P, A aA | bSCe | e, P ^ aC je, C d je} 12.3 Vypočítejte POi(V), kde X £ {5, A, P, C, P} je-li zadána tato gramatika: G = {{S,A,B,C,D\,{a , 6, • SAc iC 1 £, C -t Sy Cz je, D ->■ aPD 1 12.4 Vypočítejte POi (X), kde X G {S, A, B, C, P} je-li zadána tato gramatika: G = {{S,B,A,D,C\,{a,c,b,d},P,S), kde P = { S -> aPcP, A ->• aA | Aa, P ->• PAc j 6A, C ->• cPc | aaP, D ^ d | dC } Věta: Gramatika je PP(1), právě když pro všechny neterminály A e TV, a pro každá dvě různá pravidla A ->■ P, A ->■ 7 platí: Pii (/? • POi (A)) n F7i (7 • POi (A)) = 0 12.5 Ověřte, zda následující gramatika je PP(1), pokud ano sestrojte PP(1) 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 | aA, P ->■ e I &AcA } 2a 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 -^^T,_ X -t Y \ bYa, Y -> a T^l 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 aAaB | bAbB, A ->■ a | bb, B bB j A } Poznámka: V jednoduché LL(1) 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(1) gramatik. 12.9 Navrhněte LL{\) jednoduchou gramatiku pro jazyk zapsaný následující množinou a) {1™ 2 0" lm 2 0m | n > 0, m > 0} b) {1™ 2 0™ ľ" 2 0m | n > 0, m > 0} 12.10 Najděte jazyk, který se nedá generovat žádnou jednoduchou LL(1) gramatikou. 21