Faculty of Informatics Masaryk University Brno Cvičení k předmětům IB005 Formální jazyky a automaty a IB102 Automaty, gramatiky a složitost poslední modifikace 12. března 2014 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 L\, L2 nad abecedou {x,y,z}, kde Li — {xy,y,yx}, L2 — {y,z}. Vypočítejte: a) L\ U L2 b) Li n L2 c) L\ ■ L2, L2 ■ Li d) L®, L\, L\, L\, L\, L\ e) co — L2 1.2 Vypočítejte: a) 0*, 0+, {e}*, {e}+ b) 0U{e}, 0n{e}, 0HL, {e}nL c) 0-{e}, 0-L, {e} • L 1.3 Jsou dané jazyky L\, L2 C {a, 6, c, Li C ■ L2? g) Rozhodněte, zda platí • aabaabc G L2 • baaabc G L2 • ababc G L| h) Popište co — L2 (komplement jazyka L2). 1.4 Buď L libovolný jazyk, rozhodněte zda platí: a) pro M i G N platí L% = {w' | w G L} b) pro Vi G N platí w G L* => |u>| = z 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 • L\ = {z, y, 4* . L2 = {a-,v4* • L3 = {x}* ■ {y}* ■ {z}* . L4 =({*}*■ {j/}* ■ {z}T . L5 = ({x,y}*U{z}*y 1 • L6 = {x, y, z}* ■ {x} ■ {x, y, z}* 1.6 Porovnejte (slovně popište) jazyky a rozhodněte zda L\ — L3 • Li = {z, y, z}* . L3 = {x}* • {y}* • {z}* . L4 = {x}* ■ {yf ■ {z}* . L5 = ({x}* • {y}* ■ {z}*)* • L6 = {x, y, z}* • {x} • {x, y, z}* 1.7 Pomocí jazyků Li = {a}, L2 — {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 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, L% dokažte, zda platí, nebo neplatí: a) Li C Li ■ L2 h) (Li U L2) • L3 = (Li • L3) U (L2 • L3) cj (Li n L2) • L3 = (Li • L3) n (L2 • L3) d) pro Ví G N platí L\ ■ L\ = (Lx ■ L2)1 e) LlUL*2 = (L1UL2)* í) Ll-Ll= L\ g) (L1UL2)*^(Lt-L2-(L1)*)* 1.9 Jaký jazyk generuje gramatika G a jakého je typu? a) G P b) G P ({S,A,B,C},{a,b,c, d},P, S), kde {S —>• aS6 I aAci, —>• a£? I Ca, Bal ^ Sb \ A, Cad —>• a& | e } ({S,A},{6, c,a},P,5), kde { 5 -> 65 I c5 I oA, A ^ aA UA I cA I 2 I 6 I c} 1.10 Jaký jazyk generuje následující gramatika? Diskutujte vhodné označení neterminálů {S 00, Spi, S10, Sn). G = ({S, A £?, C},{a, 6},P, S), kde P = { S | bB \ e, A -> aS I 6C, 5 -> aC I 6S, C -> aB I } 1.11 Navrhněte regulární gramatiky pro následující jazyky: a) L — {a, b, c, d}* 2 b) L = {a, 6, c, d}1 {a, b, c, d}*;í = 2,10,100 c) L = {w w G {a, b}*, \w\ > 3} d) L = {w w G {a, 6}*, M =3k, k> 0} e) L = {w w G {a, 6, c}*, w obsahuje podslovo a66} f) L = {w wR \w G {a, 6}*} g) L = {w w G {a, 6, c}*, první 3 znaky w = poslední 3 znaky w} h) L = {w w G {a, 6, c}*, w neobsahuje podslovo abb} i) L = {w w G {a, 6, c}*, #a(w) = 2fc, #6(w) = 3Z + 1, A;, Z > 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, 93}, {«, b}, ô, qo, {53}) ô(qo,a) = qi S(qo,b) = q2 ó(qi,a) = q3 S(q1,b) = q1 S(q2,a) = q2 S(q2,b) = q2 S(q3,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}; ô(q^, 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 I w G {a}*; \w\ = 2k nebo \w\ = 71; k, l > 0} c) {w\w G {a, 6}*; #a(w) = 3k;k> 0} d) {w I w G {a, 6}*; w obsahuje podslovo abbab} e) {w I w G {a, 6}*; w obsahuje podslovo ababb} f) {w I w G {a, 6}*; w neobsahuje podslovo abbab} g) {a, b}* ■ ({c, d} U ({d} ■ {a, b}* ■ {c})) • {a, b}+ h) ({«} U {6} • ({a} • {b}* ■ {a}) • {b})* 2.3 Konstruujte deterministické FA pro následující jazyk nad abecedou {a, b, c, d} a) L = {a, 6}* • {c} • {aa, 6}* • {d}+ h) L — {w I w G {a, 6, c}*, w neobsahuje slovo 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: b 4 2.5 Co akceptuje následující automat? (=fta(w) — #b(w) je špatná odpověď) 2.6 Pomocí věty o vkládání dokažte, že jazyk L není regulární: a) L = {alb> \j>i>\} b) L = {ro | iíj e {a, 6}*; #a(w) = #b(W)} c) L — {w ■ wR | w G {a, 6}*} d) L= {a"|n = 2J; i > 0} e) L^a^i^j; i, j > 0} f) L= {a"6("!)2|n> 0} g) L — {clajbk\j < k; i,j, k e N} 2.7 Pro pokročilé: Zkonstruujte konečný automat A rozpoznávající jazyk L — {a}* ■{&}. Dokažte, že automat rozpoznává zadaný jazyk, tedy že L (A) — L. 2.8 Konstruujte deterministické FA pro všechny regulární jazyky příkladu 1.11. 5 Minimalizace DFA, nedeterministické FA, (Myhill-)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} 7 b) L = {w | w G {a, b}*, \w\ = 5k,ke N0} 3.9 Najděte a formálně popište alespoň dvě relace ~ C {a, 6}* x {a, 6}* splňující podmínky Nerodovy věty pro jazyk 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í Myhill-Nerodovy věty dokažte, že není regulární: a) L= {an | n = 2J, i > 0} b) L — {anbm | n < m < 2n, n, m > 0} c) L — {wwR | w G {a, &}+} d) L={aib>\iŕj; i,]>0} 3.11 Pomocí MN věty dokažte, že je regulárni: • L — {w e {a, b}* | #a(w) — 3k, 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 £ĽS f w G L. Určete index této relace pro jazyky: a) L = {a}* • {6}* • {c}* b) L = {a"6"c™ | n > 0} 3.13 Nechť E = {a, 6}. Uvažte následující relace na množině E*: #a(v) mod 4 #a(v) mod 4 nebo m i f končí na stejné písmeno #a(v) mod 4 a m i f 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 ~l — ~. Nakonec nalezněte jazyk Ľ, který je sjednocením některých tříd rozkladu E*/ ~, ale přitom ~ľ ^ ~. a) u ~ v <í=> =^a (it) mod 4 = b) u ~ v <í=> =^a (it) mod 4 = c) u ~ v <í=> #a(«) mod4 = 8 Regulární gramatiky a výrazy FA, £-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 ->• 65 j j b j c, B aP j 6C j aC j cA | c, C -> a j b \ aA \ bB} 4.2 Zkonstruujte ekvivalentní konečný automat k následující gramatice: G = ({S,X,y,Z},{a,6, c},P, S), kde P = { S aX \ bY | c, X -> bX j 65, y bS j cZ, Z —>• aS | 6 | c } 4.3 Zkonstruujte ekvivalentní gramatiku k automatu: 4.4 Zkonstruujte ekvivalentní 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 -o 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 G {a, 6}* | #a(w) — 2k,k > 0} c) L — {w G {a, 6}* | w začíná a končí stejným symbolem } d) L = {w G {a, 6}* | 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, ■, L\ n L2 je neregulární b) Li je regulární, L2 je neregulární => L\ n L2 je regulární c) Li 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 \ 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 0 L2 = {u ■ v I m, v e (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 1Ř jsou regulární: a) IŘ — {v I existuje u takové, že u.v G L} b) L# = {w j existuje x, y, z takové, že y G L a w = ícy^} 11 5.8 Dokažte, že pro libovolný jazyk L a libovolný konečný jazyk K platí: a) L je regulární L U K je regulární b) L je regulární <í=4> L \ K je regulární 5.9 Def: Homomorfismus h : E* —>• A* je daný předpisem: h(u.v) — h(u).h(v) pro všechny u,v 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^1(aabaaabaa) . h{Ľ),L = {w e {a*, b*} | #aH = #b(W)} • /i-^L),!, = {w e {a*} | \w\ — 2k, k G N} 5.12 Dokažte nebo vyvraťte • /i(Li -L2) = ^(Lj) -/i(L2) • /i(Li U L2) = /i(L0 U h(L2) . ' L2)R) = /i(Lf) • h(LR) • /i(Li n l2) = /i(Li) n /i(l2) • h(h(L)) = /i(L) • h^ihiL)) = L . h-1(L1-L2)=h-1(L1)-h-1(L2) • h-^Li U L2) = /^(^í) U h-1 (£2) • /i"1^! n L2) = h-1^) n /i"1^) 12 Bezkontextové gramatiky 6.1 Co generují tyto gramatiky? a) G =({S,B,A},{a,b},P,S), kde P = { S ^ aB \ bA | e, A -> aS j b A A, B bS j aBB } b) G = ({S,A},{a,b},P,S), kde P = { S —>• a-AS1 | a, A —>• 6a | .S&a } 6.2 Pro následující gramatiku G = ({5, A, P},{a, 5), kde P = { S AaB | BaA, A AB 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 G {a, b}*} U {ak | k > 1}. 6.7 Navrhněte gramatiku pro jazyk L — {cŕb^c* \ í, j, k > í,í — 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 {S ■> aA 1 &B, A - ■> aAB | aa | AC 1 AE, B - ■> bBA CB 1 BF, C - ■> D£, D - ■> CC 1 DD, E - ■> PP 1 FS, F - ■> PcP } 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 G {a, b, c}*} b) L = {w | w G {a, b, c}*, w = u'ň} c) L = {a3™+262™ | ji > 2} d) L = {^W""1"1^-1 | n > 0, m > 1} e) L = {a"6mcmrf™ | n, m > 0} f) L = {mot I u, x, v G {a, b, c}*, uv — (uv)R, x = canb2nc, n > 0} g) L = {w | W G {n, 6}*, #„(«;) > #6M} h) L = {w | u> G {a, &}*,#„(«-) = 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 -> ABC, A AbA | BC, B ^ bB \ b | cB6A cD je j j s, Ľ 555 I 6 } 7.2 Odstraňte e-pravidla: G = ({S,A,B,C,D},{b,c},P,S), kde P = { 5 ylBC, A ^ Ab | BC, B ^ bB \ b \ Ab \ e, C cD je j j e, D 555 j c5,4c} 7.3 Odstraňte e-pravidla: G=({S,X,Y,Z},{1,0},P,S), kde p = { 5 IX | Fl | 12, X -> 0FZ1 j 51X j Y, Y -> 1 j XI j e, Z —>• 5Z j 0 je} 7.4 Význam konstrukce množin Xe na příkladu G = ({A, 5, C},{a, 6, c},P, A), kde P — { A —>• BC | a | e, B ^ aB ACC j 6, C eC j 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 {5 - X 1 K A - ■> 65 1 C, D - -> 6a, B - -> 5a 1 a, X - -> aAS 1 C, C - ííD 1 5, Y - 4 556} 7.6 Převeďte do Chomského normálni formy G — ({S, A, B},{a, b},P, S), kde P — { S -> SaSbS | ayia | bBb, A —> aA | aaa | B e, B ^ Bb j 66 j 6 } 15 7.7 Převeďte do Chomského normální formy G= ({S,H,L},{0,1},P,S), kde P — { S -> OHI | 1P0 | e, ií iíií j OPI \ LH \ e, L LL \ ÍLO \ HL \ s} 7.8 Navrhněte gramatiku v CNF: a) L — {a2lb3'c> \i > í,j > 0} b) L = {wwR | i/; G {a, 6}*} 7.9 Nechť G je gramatika v CNF. Nechť w G P(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 = { 5' Art | 56 | aaA | SrtA | SbB, A -> AAb j a& j S'P6, B ^ Bbb | PPP j 6.46 } 7.11 Odstraňte levou rekurzi a transformujte do GNF G — ({S, A, B},{1, 0},P, S), kde P — { S —>• AI | 0 | IP, A PSO j 10 j SBO, B ^ OB j BIS j SO } 7.12 Odstraňte levou rekurzi a transformujte do GNF G=({S,X,Y},{c, d,b,a},P,S), kde P = { 5 -> Ic | | F6, X -> Xb I 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 | TsT | f } 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 -> PC, P —» CD | AP, C -> Art j 6, P -» 6A \ DD} 7.15 Dokažte, že následující jazyky nejsou bezkontextové a) L — {wcw | w G {a, 6}*} b) P = {a"6"c™ | n > 1} c) P = {anbmcnďn | n,m > 1} 16 Zásobníkové automaty 8.1 Daný ZA A — ({q0, qi,q2,q3, q±}, {a, b, c, d}, {Z, A},S,q0, Z, {q4}) S(q0,a,Z) = {(q0,AZ)} S(q0,a,A) = {(q0,AA)} 5(q0,b,A) ={(qi,e)} S(qi,b,A) = {(gi,e)} S(qi,e,A) = {(q2,A),(q3,A)} S(q2,C,A) = {(q2,e)} S(q3, d, A) = {(g3, e)} S(q2, e, Z) = {(94, Z)} S(q3,e,Z) = {(q4,Z)} 8.2 Je daný ZAA= ({g0, gi, 92, \ i,j>0} b) L — {w I w G {a, b}*; w — wR} c) L — {a3nb2n I n > 1} d) L — {a3n+2b2n-1 I n > 1} e) L = {w I w e {a, b, c}*; #a(w) = #6(w)} f) L — {w \ w e {a, b, c}*; #„H # #6(W)} g) L = {afc6í I 1 < j < k < 2j} h) L — {an+mbm+pď+n | ri > 1} i) L = {aW I i, j > 1} U {afe6fecm | jfc,m > 1} j) L = {afel6afe26... bakr \ r > 1, &j > 1 (i = 1,..., r; existuje p,s : p ^ s,kp — ks)} 8.4 Daný ZA A. = ({ 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 — ({q0, q±, g2}, {a, b, c}, {A, B, C}, ô, qo,A, 0}) akceptující prázdným zásobníkem transformujte na ekvivalentní bezkontextovou gramatiku. 5(q,(,Z) ={(q,L)} ô(q,(,L) ={(q,LL)} S(q,),L) ={(q,e)} 5(q0,a, A) = {(q!,B)} ó(q0,b,A) ={(qltAB)} S(qi,c,A) = {(q2,e)} ô(qi,a,B) = {(q0,ABC)} 5(q2,e,B) ={(q2,e)} ô(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, L2 bezkontextové => L\ U L2 je kontextový b) Li bezkontextový A Li n L2 není bezkontextový => L2 není bezkontextový c) Li regulární A L2 bezkontextový => co — (Li n L2) bezkontextový d) Li konečný A L2 bezkontextový => co — (Li n L2) bezkontextový 9.2 Jsou dané jazyky L = {iowii I w G {a, 6}*} i? = L((a*6+a)* + a*) Navrhněte ZA pro jazyk LOR 5L(q0,x,Z) = {(g0,xZ)} SL(qo,x,y) = {(go,a;y)} 5L(g0,e,a;) = {(gi,^)} 5L(gi,x,x) = {(gi,e)} 5L(gi,e,Z) ={(g2,Z)} \fx e {a, 6} Vx, y G {a, 6} Vx e {a, 6, Z} \fx e {a, 6} £r(po, «) = Po ^ií(pi, &) = Pl SrÍPi, a) = po Fr = {p0} 9.3 Je dána bezkontextová gramatika G=({S},{a,b},P,S), kde P — { S ^ aS \ Sb \ 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) Li — {x I 3y e {a, 6}*; xy e L} b) Li = {x I 3y e {a, 6}*; yx e L} Dokažte, že Li je taky bezkontextový. 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ý 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 e {a, b}* | #a(w) — #&(»')} 10.4 Navrhněte TS (determ. nebo nedeterm.) TS pro jazyk: a) L^{albjck \ k = ij,i,j G N} b) L — {ww \w e {a, b}*} c) L — {aP | p není prvočíslo } d) L — {onw | w G {0,1}* ,w je binárni 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,t>,R) 6(q,á) =(p,A,R) S(p,b) = (q,a,L) ô(q,U) = (j>,A,R) S(P, U) = (q, a, L) S(q, a) = (qaCcept, A, R) Kde t> 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 D 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 i? je rekurzivní => L \ R není rekurzivní g) L není rekurzivní, R je rekurzivní ai?CL=>L\i? není rekurzivní 11.4 Navrhněte gramatiky pro následující jazyky: • {w | w E {a, b, c}*, #a(w) = #b(w) = #c(w)} • {to I w G {a, 6, 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? 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) ^4 B je rekurzivní f) A je rekurzivně spočetná =>• A LinL2ecoNP c) Li e NP,L2 C Li,L2 e coNP Li \ L2 e NP 13.5 Rozhodněte, zda jsou následující formule splnitelné. U splnitelných formulí popište nějaké splňující přiřazení. a) (x V y) A (x V -vy) A (^x V y) A (^x V ^y) b) (x V -.y) A (x V y V z) A (-.x V -.y) A (-.x V y) A (x V ^z) c) (x V -ny) A (x V ^y V z) A (->x V -ny) A (->x V y) A (x V ^z) d) (iiV^dV ^w) A (w V V z) A (w V ^z V x) A (x V y V z) e) (x V y V z) A (->x V y V z) A (x V V z) A (x V y V ^z) A (->x V V z) A (x V ~^y V ^z) A (->x V V -• U splňující (u,u1) e E => (f (u), f (u1)) e F} 23 13.7 Určete vztahy inkluze/rovnost mezi následujícími dvojicemi složitostních tříd. Svoje tvrzení zdůvodněte. a) TIME(n2) a TIME(n3) b) SPACE(2n2) a SPACE(100»2) c) SPACE(íi2) a TIME(n2) d) NSPACE(n2) a SPACE(n5) e) P a TIME(2") 13.8 Zkonstruujte jednopáskový deterministický Turingův stroj, který rozhoduje jazyk L — {0felfe | k > 0} v čase O(nlogn). Není nutné uvádět formální popis stroje. 24 Zadání cvičení IB005 1. cvičení: Operace nad jazyky • Připomeňte základní terminologii a definice • Připomeňte základní operace nad jazyky a přitom cvičte příklady 1.1 a 1.2 • Cvičte 1.3, u 1.3 d) nacvičte "neplatnost tvrzení dokazujeme protipříkladem". • Cvičte 1.4 • Cvičte 1.6 • Cvičte 1.7 • Cvičte 1.8 b) a c) (jednu inkluzi skutečně dokažte) • Připomeňte pojem gramatiky • Cvičte 1.9 • Dle zbývajícího času, jinak za DU, příklady 1.10, 1.11 2. cvičení: Konečné automaty a regulární gramatiky • K čemu slouží Konečné automaty? • Na příkladu 2.1 vysvětlete co jsou a jak fungují konečné automaty • Uveďte formální definici DFA • Příklad 2.2a-d,f ([deterministické FA!) • Příklad 2.2g,h volitelně dle času • Příklad 2.3a • Příklad 2.4 • Příklad 2.5 • Příklad 1.11 3. cvičení: Pumping lemma, (Myhill-)Nerodova věta • Znění a použití Pumping Lemma pro regulární jazyky • Příklad 2.6a poctivě, b zrychleně, g poctivě, e zrychleně • Znění Nerodovy věty a Myhill-Nerodovy věty • Vztah ~ a deterministických automatů a vztah ~£ a mininimálního automatu 25 • Příklad 3.9 • Příklad 3.12 • Příklad 3.10 jednu odrážku pořádně, další případně zrychleně 4. cvičení: Minimalizace a kanonizace DFA, nedeterministické FA a determinizace • Připomeňte si • Definujte minimální konečný automat. • Příklad 3.2 • Příklad 3.3 • Definujte nedeterministikcé FA, a způsob akceptování NFA. • Příklad 3.4 • Příklad 3.5 • Upozorněte, ze pro minimalizaci, je třeba vyjít z deterministického automatu. 5. cvičení: Ekvivalence FA, regulárních gramatik a regulárních výrazů, £-kroky, Kleeneho věta • Vysvětlete princip transfomrace odstranění e-kroků • Příklad 4.7 • Zopakujte vyjadřovací ekvivalenci dosud známých formalismů • Formulujte podstatu algoritmů pro převod FA na regulární gramatiky a zpět • Příklad 4.2 • Příklad 4.4 • Připomeňte si definici regulárních výrazů (syntax a sémantika) • Příklad 4.11 • Princip transformace regulárních výrazů na FA a zpět • Příklad 4.8 c) • Příklad 4.10 • Příklad 4.12 a) a diskuze k 4.12 b) 26 6. cvičení: Uzáverové vlastnosti regulárních jazyků • Příklad 5.1 • Příklad 5.2 • Příklad 5.3a - formulujte formální konstrukci synchronního součinu • Příklad 5.3b-f- slovní argumentace (hint důkazu) proč ano či ne • Příklad 5.4 • Příklad 5.5 • Příklad 5.6 • Příklad 5.7 - formální konstrukce 7. cvičení: Bezkontextové gramatiky a derivační stromy, redukovaná CFG • Připomeňte CFG a ukažte jak vypadá a jak funfuje CFG pro {anbn \ n > 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.8b) • 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 27 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říkald 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 28 Zadání cvičení IB102 1. cvičení: Operace nad jazyky, gramatiky • Připomeňte pojmy abeceda, jazyk, slovo apod. • Připomeňte základní operace nad jazyky a přitom cvičte příklady 1.1 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 C a 3- Jednu inkluzi dokažte. • Příklad 1.8 c). Pozor, rovnost neplatí. • Připomeňte pojem gramatiky a cvičte příklad 1.9 a) anebo b). • Pokud vám zbyde čas, cvičte příklady 1.10 a 1.11. 2. cvičení: Deterministické konečné automaty, pumping lemma • Příklad 1.11 a) d) (pokud jste nestihli na prvním cvičení). • 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). • Příklad 2.4. • Příklad 2.6. Z lehčích příkladů a)-c) udělejte jeden pořádně, ostatní zrychleně. Dále udělejte pořádně jeden zajímavější příklad, nejlépe g). Zbyde-li čas, projděte zrychleně i ostatní příklady, zejména 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í). 3. cvičení: Myhill-Nerodova věta • Zopakujte Myhill-Nerovou 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á. 29 3. Pro každý jazyk LCS* (i neregulární) je ~£ vždy pravá kongruence a L je sjednocením nějakých tříd rozkladu £*/ Má-li konečný index, lze sestrojit DFA pro L a L je tudíž regulární. 4- 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. • 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}* ■ {b}* ■ {c}* ■ {d}* a upozorněte, že přestože index ~l 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. 4. cvičení: Minimalizace a kanonizace konečných automatů, nedeterministické automaty, determinizace, odstranění £-kroků • Zdůrazněte, že před vlastní minimalizací se z automatu odstraní nedosažitelné stavy a automat se ztotální. • Příklad 3.2 b). • Příklad 3.1 a). • Příklad 3.3. • Zopakujte nedeterministické FA. • Příklad 3.4. Počet odrážek podle potřeby, zbytek můžete dodělat na konci hodiny, pokud zbyde čas. • Zopakovat determinizaci. • Příklad 3.5 a) nebo b). • Zopakovat odstranění e-kroků. • Příklad 4.5. Příklad řešte pomocí tabulkového zápisu. Máte-li čas, 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. 5. cvičení: Uzáverové vlastnosti regulárních jazyků • Příklad 5.1. • Příklad 5.2. • Příklad 5.3. • Příklad 5.4. • Příklad 5.5. • Příklad 5.6. • Příklad 5.8. • Příklad 4.12 a). Zbyde-li čas, řešte i b). Nechcete-li u části b) prezentovat plnohodnotné řešení (je trošku náročnější), můžete řešit zjednodušenou verzi, kde se přijme omezení, že n a U lze aplikovat jen na jazyky nad stejnou abecedou. Pak se snadno ukáže, že je třída všech konečných jazyků a jejich doplňků. Upozorněte, že bez toho omezení to ale neplatí, uveďte příklad. 30 6. cvičení: Ekvivalence FA, regulárních gramatik a regulárních výrazů • 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. • Alespoň sem byste měli určite dojít. Zkuste zvládnout ještě tyto příklady na bezkontextové jazyky. • 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. • Zbyde-li čas, dělejte další odrážky z příkladu 6.11. 7. cvičení: Bezkontextové gramatiky, derivační stromy, transformace • 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říklad 6.9. • Příklad 7.2. • Zbyde-li čas, dělejte dosud neprocvičené části příkladu 6.11. 8. cvičení: CNF, odstranění levé rekurze, pumping lemma pro bezkontextové jazyky • Příklad 7.5. • Příklad 7.6. • Příklad 7.8. • Příklad 7.12. Cvičte pouze odstranění levé rekurze (transformaci do GNF v IB102 neučíme). Pokud by jeden příklad nestačil, udělejte ještě příklad 7.13 nebo 7.10. • Příklad 7.15. Jednu odrážku udělejte pečlivě, v dalších se soustřeďte jen na to podstatné. 31 9. cvičení: Zásobníkové automaty, nedeterministická syntaktická analýza, uzáverové vlastnosti bezkontextových jazyků • 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ě. • Příklad 8.3. Udělejte pořádně aspoň dvě odrážky včetně c). • Příklad 8.6. • Příklad 9.1. • Příklad 9.3. • Zbude-li čas, cvičte další odrážky z příkladu 8.3. 10. cvičení: Konstrukce TM, frázové gramatiky, uzáverové vlastnosti rekursivních a rekursivně spočetných jazyků • Ukažte, že jazyk co—{ww \ w G {a, b}*} nad abecedou {a, b} je bezkontextový. • Příklad 10.1. • Příklad 10.2. • Příklad 10.4 b). Konstrukci ostatních strojů zformulujte jen neformálně. • Příklad 11.3 a) d) e) f) g). • Příklad 11.4. Není nutné vyřešit celý příklad. Co stihnete, to stihnete. 11. cvičení: Redukce a rozhodnutelnost problémů. • Příklad 12.1. • Příklad 12.2. • S využitím příkladu 12.3 připomeňte definici Postova korespondenčního problému. • Příklad 12.4. • Zbude-li čas, udělejte i příklad 12.5. 12. cvičení: Složitost • Příklad 13.1. • Příklad 13.3. • Příklad 13.4. • Zopakujte pojem konjunktivní normální forma (cnf-forma) formulí, pojem Scnf-forma a problém 3SAT. Ke zopakování můžete využít část příkladu 13.5. • Příklad 13.6 b) c). • Příklad 13.7. • Zbude-li čas, udělejte i příklady 13.6 a), 13.2 a 13.8. 32 Řešení některých příkladů 33 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) {£}, {y,z}, {yy,yz,zy,zz}, {yyy,yyz,yzy,yzz,zyy,zyz,zzy,zzz}, {s, 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, y z, zy, zz, yyy, yyz, yzy, yzz, zyy, zyz, zzy, zzz,...} tj. libovolné slovo z písmenek y a z kromě s e) {x, y, z}* \ {y, z} tj. libovolné slovo složené z písmenek x, y a z včetně s, kromě slov y a z 1.2 a) {e}, 0, {e}, {e} b) {e}, 0, 0, {e} pokud e G 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 6aa e) jedno slovo z množiny {a,aa,ba,aba,aaa,baba,baa} f) ano, protože e G L2; ne, protipříklad Li = {a}, L2 — {b}; pro pokročilé: implikace platí, implikace "<^==" platí pouze v upravené podobě e E L2 (Li C L\ ■ L2 A Li 7^ 0) g) ano, ano, ne h) všechna slova nad danou abecedou, kromě slov z jazyka L2, formálně: {a, b, c, ď}* \ L2 1.4 a) Neplatí. Protipříklad: L — {aa,bb}, i — 2, L1 — {aaaa,aabb,bbaa,bbbb}, {w1 \ w G L} — {aaaa,bbbb} b) Neplatí. Protipříklad: L — {aa}, L2 — {aaaa}, ale |aaaa| 7^ 4 c) L — {a} 1.5 L\ — l4 — L5 > L2, L\ — l4 — L5 > L3, L\ — l4 — L5 > Lq, neporovnatelné: L2, L3, Lg Li - všechna slova nad {x, y, z} L2 - všechna slova nad {x, y, z}, tvaru xyzxyzxyzxyzxyz ... 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}* Lq - všechna slova nad {x, y, z}, která obsahují alespoň jeden výskyt x 1.6 L\ — L5 > L2 > Lq, L\ — L5 > L3 > L4, L2 > l4, neporovnatelné: L2 a L3, Lq a L3, Lq a l4 Li - všechna slova nad {x, y, z} L2 - všechna slova nad {x, y, z}, kromě s 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 • (Li U L2)* ■ Lx ■ (Lx U L2)* b) (Li • Lx U Lx ■ L2 U L2 ■ Lx U L2 ■ L2)* c) Li ■ (Li U L2)* ■ L2 d) Li U L2 U Li • (Li U L2)* ■ L1 U L2 ■ (L1 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\ ílLj) e) (Li U L2)* ■ Li ■ L2- Li ■ (Li U L2)* f) (Li ■ Li U Li ■ L2 U L2 ■ Li U L2-L2)* n L\ ■ (L\ U L2)* ■ L2 g) ((Li-Li U Li ■ L2 U L2-Lx U L2 ■ L2)*)c 1.8 a) ne, L — 1 = {a} a L2 = {6} b) ano, nutno dokázat obě inkluze C a 3 c) ne; Li = {a}, L2 = {a6} a L3 = {6, e} d) ne, Li — {a} a L2 — {b} e) ne, Li — {a} a L2 — {b} f) ano, nutno dokázat obě inkluze C a D g) ne, Li = {a} a L2 — {b} 1.9 a) {a™6™ | n G N0}, typu 0 b) {b, c}* ■ {a} ■ {a, b, c}+, typu 3 (regulární) 1.10 {w G {a,b}* I =fta(w) — 2k,=fttl(w) — 2j;j,k G No}, dolní indexy u navržených terminálů představují zbytek po dělení počtu 'a' (resp. 'b') dvěma Deterministické konečné automaty, pumping lemma 2.1 a) b) L = {a} • {b, aa}* ■ {a} c) L — ({a} • {b}* ■ {aa,})* ■ ({a} • {b}* ■ ({a} U {ab} ■ {a, b}*) U {b} ■ {a, b}*) 34 35 c) 2.4 L = {a}.{b}*.{a}.({c}.{d})* U {b} 2.5 L={i»e {a, 6}* | #a(w) = #b(w) A w = u.v =>• |#a(u) - #6(u)| < 3} 2.6 U příkladu e) je třeba volit slovo anbn]+n. a,b,c,d 2.8 a) 1.11a Jj) a,b,c,d 1.11b- 1.11c — 5o ^ 5l ^ 5a _^53 l.lld 6,c l.lle_^_ o - o---o , _ÍL 1.1 lf Není regulární, b,c l.llh l.lli a.b.c 36 l.llj Minimalizace DFA, nedeterministické FA, (Myhill-)Nerodova věta 3.1 a) 3.2 a) a b -> A B C B D B C C D A B C B C A C C D D C E -í- E F E F D F b) b) a b <-> A B C B B C C C D 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í. b 3.4 a) a,b,c,d a,b,c,d c) d) e) 0,1 0,1 a,b,c,d a,b,c a a a a 1 0,1 0,1 0,1 0 10 11 37 3.5 a) a b c b) a b c [1] [23] [34] [1] [1] [12] [1] [1] <- [23] [123] [14] [234] <- [12] [12] [13] [1] [34] [123] [1] [34] [13] [12] [1] [14] > 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 Ch ^ Ch ^ Ch ^ w w w ^ Ch nutně musí některá dvě slova padnout do stejné třídy rozkladu, označme je ak,al (k ^ l). Po přiřetězení slova ak dostáváme slovo akak E L & slovo alak ^ L. Tím je dosažen spor s předpokladem a L není regulární. b) e, a, a2,an z čehož ak,al (BÚNO k < l), která akbk e L, albk L c) abb, a2bb,an+1bb z čehož akbb, cŕbb (k 7^ l), která akbbak G L, albbak ^ L d) e, a, a2,an z čehož ak,al (BÚNO k < l), která akbk g" L, albk e L 3.11 Definujeme binární relaci ~ takto: m ~ f •<=> #a(w) = #b(w) (rnod 3) ~ je ekvivalence, ~ je pravá kongruence, |~| = 3, tedy má konečná index, L — {w | #a(w) mod 3 = 0} 3.12 a) 4 b) nemá konečný index 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ční 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í). 38 c) ~ je ekvivalence i pravá kongruence, index je 9. Lze podle ní sestavit tento automat: a la-*- 2a-*- 3a-*- Oa 06 16 26 36 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, 0a, 06 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, e-kroky, Kleeneho věta 4.1 , _,_,_, a 6 c {Ä g/} {Č} 0 Ä {A} {B,qf} { 0}. Pak M2 je třída všech jazyků L takových, že pro všechny £1, které jsou podmnožinou abecedy jazyka L, platí: L n C(Ei) je konečný nebo C(Ei) \ 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 1Z 5.1 Neplatí. Jazyky Li — {erb1} pro každé i > 0 jsou konečné a tudíž regulární, ale (J^i ^4 — {«"6™ | n > 0} není regulární. 39 5.2 Li — {a, b}* \ {alb1} pro každé i > 0. Pak H^i L% — {a, b}* \ {anbn \ n > 0}, což není regulární jazyk, protože {anbn \ n > 0} není regulární jazyka 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 X — {a, b}. R jistě není regulární. operace regulární výsledek neregulární výsledek Lx n L2 i? n co-R = 0 Rľ\R = R L1UL2 R U co-R = E* i?Ui? = R Li \ L2 i?\ iž = 0 R \ co-i? = i? Li ■ L2 (i? U {e}) -co-i? = E* i?i? LI (co-i?)* = E* i?* 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) — #&(w)} b) Jazyk se nedá moc rozumně popsat. 6.4 Ano. (Právě všechny reg. jazyky.) 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) {aW \ 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 11.3 a) Neplatí. Stačí vzít libovolný neregulární rekurzivně spočetný L na abecedou Eafí = E*. b) Platí (viz. skripta), c) Platí (viz. skripta), d) Platí, e) Platí, f) Neplatí. Stačí vzít fiDL. g) Platí. Plyne z uzavřenosti rekurzivních jazyků na sjednocení. 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 n0 platí definiční nerovnost, nebo ukážeme (většinou sporem), že takové konstanty neexistují, a) Volíme například uq — 1, c — 3. Pro všechna n > uq platí 2n < 3n — cn a proto 2n G O (n), b) Předpokládejme, že existují no a c takové, že pro všechna n > no platí n2 < cn. Položme m — max{c, no} + 1. Zjevně m > no, ale m2 > cm. To je spor a proto n2 ^ O(n). c) Platí, d) Neplatí, e) Nejprve připomeňme definici. Píšeme /(n) G 2°^9ÍJl^\ pokud existují no, c G N takové, že pro všechna n > uq platí /(n) < 2c'9ÍJl\ Analogicky se definuje i význam dalších aritmetických výrazů obsahujících 0(g(n)), jako například 22 uq splňující g (n) > c • /(n) — c. Vztah /(n) G o(g(n)) ovšem neplatí, protože funkce nemá pro n jdoucí do nekonečna limitu. 13.3 Nechť Ma, M-q jsou jednopáskové deterministické Turingovy stroje pracující s časovou složitostí 0(pa), O (p b) (kde p a a pb jsou polynomy), které akceptují jazyky A, B. Nejprve ukážeme, že třída P je uzavřená na všechny tři operace. Popíšeme dvoupáskový deterministický Turingův stroj M akceptující jazyk AU B. Stroj M pro vstup x nejprve zkopíruje vstup na druhou pásku (v čase 0(n)), pak na druhé pásce simuluje výpočet stroje Ma-Je-li v této simulaci dosažen akceptující stav stroje M a, pak i stroj M akceptuje. V opačném případě stroj M simuluje na první pásce výpočet stroje Mg. Je-li v této simulaci dosažen akceptující stav stroje Mb, pak i stroj M akceptuje, jinak zamítá. Je zřejmé, že stroj M akceptuje jazyk A U B a že pracuje v čase 0(n +pa(n) +ps(n)), tedy v polyniálním čase. Stroj akceptující komplement jazyka A získáme ze stroje M a záměnou akceptujícího a zamítajícího stavu. Takto získaný stroj pracuje se stejnou časovou složitostí jako Ma- Popíšeme třípáskový Turingův stroj M akceptující jazyk A.B. Stroj postupně zkouší rozdělit vstupní slovo x — x\x2 ■ ■ ■ xn na všechny možné dvojice podslov (nejprve s a x, pak x\ a x2 ■ ■ ■ xn, pak xix2 a x$ .. .xn, ..., nakonec x a e). První podslovo vždy zkopíruje na druhou pásku a simuluje na něm výpočet stroje M a- Druhé podslovo zkopíruje na třetí pásku a simuluje na něm výpočet stroje Mg. Pokud obě simulace dospějí do akceptujících stavu, stroj M akceptuje. V opačné situaci postup opakujeme pro další dvojici podslov. Pokud už byly vyzkoušeny všechny dvojice, stroj M zamítne. Stroj M pracuje v čase 0(n ■ (n + pa(ti) + PbÍp))), tedy v polyniálním čase. Třída N P je uzavřená na sjednocení i na zřetězení. V obou případech lze použít stejnou argumentaci jako u třídy P. V případě zřetězení lze algoritmus stroje M vylepšit tak, že neprochází všechny dvojice podslov, ale nedeterministicky uhodne správné rozdělení na podslova. Uzavřenost třídy N P na komplement je otevřený problém (známý jako N P — coNP?). Výše uvedená argumentace pro P v tomto případě nefunguje: záměnou akceptujícího a zamítajícího stavu u nedeterministického stroje získáme stroj, který akceptuje slovo w pokud existuje zamítající výpočet původního stroje nad tímto slovem. Žádoucí by ovšem bylo, aby zkonstruovaný stroj akceptoval slovo w pokud jsou všechny výpočty původního stroje nad tímto slovem zamítající. 13.4 a) Neplatí. Stačí uvážit libovolný jazyk L G P C N P. Jelikož třída P je uzavřená na doplněk, tak i co-L G P C NP. Tedy co-L co-NP, ale přitom co-L G coNP. b) Platí. Jelikož co-L1; co-L2 G NP a NP je uzavřené na sjednocení, tak co—L\ U co—L2 G NP. Tedy L\ n L2 G coNP. c) Platí. Jelikož co—L2 G NP a NP je uzavřené na průnik (lze lehce dokázat), tak L\ n co—L2 — L\ \ L2 G N P. 41 13.6 Příslušnost do N P lze dokázat snadno. NP-těžkost lze dokázat redukcí: a) z problému 3SAT (viz Sipser: Theorem 7.35 v 1. vydání, Theorem 7.46 ve 3. vydání) b) z problému 3SAT (viz Sipser: Theorem 7.26 v 1. vydání, Theorem 7.32 ve 3. vydání) c) z problému CLIQUE. pro danou instanci (G,k) problému CLIQUE lze v polynomiálním čase vytvořit dvojici (Hk, G), kde Hk je úplný graf s k vrcholy. Je zřejmé, že (G, k) G CLIQUE právě tehdy, když (Hk, G) G SGL Abychom se ujistili, že redukce CLIQUE