Faculty of Informatics Masaryk University Brno Cvičení k předmětu IA006 Vybrané kapitoly z teorie automatů poslední modifikace 9. ledna 2021 Tato sbírka byla vytvořena z příkladů ke cvičení z předmětu Teorie automatů a formálních jazyků II, které byly původně připraveny Ivanou Černou. Na opravě nesčetných chyb a doplnění příkladů se podílelo mnoho studentů a cvičící předmětu IA006 Vybrané kapitoly teorie automatů Jiří Barnat, Vojtěch Řehák a Jan Strejček. Funkce FIRST a FOLLOW Opakování a motivace 1.1 Je dána následující gramatika G. Navrhněte PDA (zásobníkový automat), který analyzuje slova nad abecedou {a, b, c} metodou shora dolů. G=({S,A},{a,b,c},P,S), kde P = { S —> aSa | bSc \ aA, A bbAb j e } Operace k:w a L\ ®k L2 Nechť k g N je přirozené číslo, w je slovo a L\,L2 jsou jazyky. Operace k:w a L\ <3)k L2 definujeme následovně: {w pokud |w| < k u, kde \u\ = k a w = u.v pro nějaké v pokud \w\ > k L\®kL2 = {k:w \ w e Li.L2} Tedy k:w je prvních k písmen slova w (případně celé slovo w, je-li jeho délka kratší než k) a L\ <3)k L2 je jazyk všech slov z L1.L2 zkrácený stejným způsobem na prvních k písmen. FIRST a FOLLOW Nechť G = (N, S, P, S) je bezkontextová gramatika. Pro každé keN jsou funkce FIRSTS a FOLLOW^ definovány následovně: FIRST^ : (S U N)* —> 2S* FIRST^(a) = {k:w\a=>*w, w g S*} FOLLOW% : N —> 2S* FOLLOW^(A) = {w I S =^>* jAa, w e FIRST%(a) ; 7, a e (S U N)*} Pozor na typ argumentu u jednotlivých funkcí. Argumentem funkce FIRST1^(a) je řetězec terminálů a neterminálů (a g (S U N)*), na rozdíl od funkce FOLLOWf„ (A), jejíž argumentem je vždy právě jeden neterminál (A E N). Definice funkcí FIRST1^ a FOLLOW1^ lze přirozeně rozšířit také na množiny odpovídajících argumentů, což je užitečné zejména pro funkci FIRST1^. FIRST1;: : 2(SUAr)* —> 2S* FOLLOW^ : 2N —> 2S* FIRST^(M) = \JaeM FIRST^(a) FOLLOW^(M) = \JAeM FOLLOW^(A) Dále budeme používat zkrácené zápisy funkcí, Flk(a) pro FIRST1^(a) a FOk(Ä) pro FOLLOW1^(A) (G je zřejmé z kontextu a typicky se neuvádí). 1 Algoritmus pro výpočet funkce FIRST Je dána gramatika G = (N, £, P, S) a řetězec a = Y{Y2 .. .Yi, kde každé Yí e N U S U {e}. 1) F/fe(x) = {x} pro x e E, FJfeOO = {e} 2) Výpočet FIk(x) pro x e iV: Nechť = {Xi, X2,..., Xn}. Budeme počítat hodnotu FIk(Xl) současně pro všechny neterminály (i = 1,..., n). Nejprve sestavíme pro každý neterminál Xi příslušnou rovnici. Nechť všechna pravidla pro neterminál Xi jsou tato: Potom FIk(Xi) = (FIk(Y?) ffife FIk(YÍ) @k ... ffife Fhtä)) U U (FhOr?) ffife FIk(YÍ) ®k ... ffife FIk(Yg)) U U {FIk{Y() ffife F/fe(y2J) ©fe ... ®fe FIk(YQ) Hodnoty FIk(Xi) jsou nejmenším pevným bodem uvedené soustavy rekurzivních rovnic. Nejmenší pevný bod spočítáme tak, že nejprve nastavíme všechna FIk(Xi) na hodnotu FIk(Xi) = 0. V první iteraci dosadíme tyto hodnoty do pravých stran rovnic. Vyhodnocením rovnic získáme nové hodnoty pro všechna FIk(Xi). Tyto nové hodnoty v další iteraci opět dosadíme do pravých stran rovnic. Tento postup opakujeme tak dlouho, dokud nám ve dvou po sobě jdoucích iteracích nevyjdou stejné hodnoty pro všechna FIk(Xi). Takto získané hodnoty jsou nejmenším pevným bodem a tedy i hledanými množinami FIk(Xi). Chceme-li výpočet nejmenšího pevného bodu urychlit, můžeme při dosazování do pravých stran rovnic použít namísto hodnot z předchozí iterace již známé hodnoty z aktuální iterace. 3) FIk(a) = FJfe(yi) ffife FIk(Y2) ffife • • • ffife FIk(Yt) Algoritmus pro výpočet funkce FOLLOW Je dána gramatika G = (N, S, P, S). Funkce FOk je definována pouze pro neterminály. Opět budeme počítat hodnotu FOk(Xi) pro všechny neterminály Xi současně. Nejprve opět sestavíme příslušné rovnice. Pro každý neterminál A, který není kořenový, klademe: FOk(A) = (J FIk(ß) ffife FOk(B) {B^>uAß)eP Pro kořenový neterminál S klademe: FOk(S) = {e} U U FIk(ß) ffife FOk(B) (B^aSß)eP Hodnoty tvaru FIk(ß) spočítáme dle předchozího algoritmu a dosadíme do rovnic. Následně spočítáme všechny hodnoty FOk(Xi) jako nejmenší pevný bod rovnic (použijeme stejný postup výpočtu jako u předchozího algoritmu). Hodnoty výrazu FIk{a) i FOk(A) lze často určit intuitivně, buď přímo z definice funkcí nebo s využitím příslušných rovnic (zejména pokud nejsou rekurzivní). Uvedené rovnice se často dají zjednodušit s využitím následujícího pozorování. Pokud víme, že délka nejkratšího řetězce v jazyku L\ je alespoň n, pak platí: (Li ffife FIk_n(L2) pokud n < k {k:w I w g Li} pokud n > k a L2 7^ 0 0 pokud n > k a L2 = 0 2 S využitím tohoto principu snadno můžeme například nahradit výraz FI3(aBcD) ®3 F03(P) ekvivalentním výrazem FI3(aBcD)ffi3FO\(E). Z podobných důvodů lze například výraz FI2(aBcDeF) nahradit ekvivalentním výrazem FI2(aBc), ovšem pouze za předpokladu, že neterminály D, F jsou normované (tj. lze z nich odvodit nějaký řetězec terminálů). 1.2 Podle algoritmu řešte FI2(A) a FI^(Ae) pro gramatiku G = ({A, B, C, P},{c, a, d, e},P, A), kde P = { A ->• Bc | a, B -> A \ C \ d, C B I d, D e } 1.3 Podle algoritmu řešte FI2(Ä) a FI3(A) pro gramatiku G = ({A},{a,b},P,A),kde P = { A ->• Aa, A -> 6 } 1.4 Vypočítejte Fh(BBb), FI2(BBb), FO^A), FO^S), FOi(P), FOi(C), P03(A), ^(5), F03(C), FIi(SAcB), FIi(SAcB) pro následující gramatiku: G = ({S, A, B, C},{a, c, b, e, d},P, S), kde P = { S aAc | S, A aA j 65Ce | e, P —>• oC j e, C ^ d \ e } 1.5 Podle algoritmu řešte FOk(X), kde = 1, 2, 3, 4 a X G {S1, A, P, C, D} pro následující gramatiku: G = ({S,A,B,C,D},{a,b,d,c,x,y,z},P,S), kde {S ■> aABbCD £, A - £, B - xC e C - + % Cz e D - ■> aPD e} 1.6 Vypočítejte FOk{X), kde k = l,2,3,4aX e {S, A, B,C, D} pro následující gramatiku: G = ({S, B, A, D, C*},{a, c, b, d},P, S), kde {S ■> aBcB, A - ■> B - ■> PAc b A, C - ■> cPc aaB, D - -> d dC} 1.7 Zamyslete se, v jakých případech platí následující vztahy: a) FIk(A) = 0 f) FOk(A) = 0 b) e G FIk{Ä) g) e e POfe(A) c) FIk(A) C PP,+i(A) h) POfe(A) c FOk+1(A) d) f/fc+iíA) C F/t(A) i) FOk+1(A) C FOt(A) e) F4(a-FOt(X)) = f4(Q )®fePOfc(X) j) POfe(A) c POfc(P) k) (L1 ®fe L2) ®fc L3 = Li ®fe (i2 efc L3) 3 SLL(k) gramatiky a analyzátory Intuitivně řečeno, gramatika G je SLL(k), právě když se odpovídající nedeterministický syntaktický analyzátor pro analýzu shora dolů dokáže vždy jednoznačně rozhodnout pouze na základě neterminálu na vrcholu zásobníku a prvních k písmen z dosud nepřečteného vstupu. Formálně, gramatika G je SLL(k), právě když pro všechny neterminály ieJVa pro každá dvě různá pravidla A —> j3, A —> 7 platí: FIk(f3)®kFOk(A) n ŕ7fe(7) ®fe FOk(A) = 0 2.1 Ověřte, zda následující gramatika je SLL(2): G = ({S, X, Y},{b, a},P, S), kde P = {S -> X, X Y I bYa, Y a je} 2.2 Ověřte, zda gramatika je SLL(3): G = ({S, A, B},{a, b},P, S), kde P = { S aAaS I A —> a I a&, B ^ aB \ a } 2.3 Navrhněte SLL(2) analyzátor pro následující gramatiku a analyzujte slovo acaac a slovo abaac. G = ({S, A, B, D},{a, c, b},P, S), kde P = { S aAaA, S1 —> aBaB, A ->• aA, A ->• c, D ^ e } 2.4 Navrhněte SLL(3) analyzátor pro gramatiku a analyzujte slovo bababab. G = ({S, A, B},{b, a},P, S), kde P = { S ĎaAa, S1 —> baBb, A ->• aA, A ->• aS, S e } 4 LL(k) gramatiky a analyzátory Gramatika je LL(k) , právě když pro dvě libovolná různá pravidla gramatiky A —> j3, A —> 7 a pro všechny nejlevější větné formy tvaru wAa platí: FIk{j3 ■ a) n FIkij ■ a) = 0 Gramatika je LL{\) právě když je SLL(Í). Je-li gramatika G SLL(k), pak je také LL(k). 3.1 Ověřte, zda je následující gramatika L L (2): G = ({S, X, Y},{b, a},P, S), kde P = {S -> X, X Y I bYa, Y a je} 3.2 Ověřte, zdaje následující gramatika LL(3): G = ({S1, A, S},{a, 6},P, S), kde P = { S aAaP I ĎAĎP, A —> a I a&, S ->• aB j a } 3.3 Ukažte, že gramatika není L L (k) pro žádné /j: G = ({S, A, B},{a, b, 0, í},P, S), kde P = { S -> A I S, A ->• aAĎ j 0, S aPĎĎ j 1 } 3.4 Ukažte, že gramatika je LL(k): G = ({S, T, A, B}, {a, b, c}, P, S), kde P = {S ^ aT T ^ SA I A A^bB j c P^ Ď^d j e 3.5 Zkonstruujte LL(2) analyzátor pro gramatiku G: G= ({S, A},{a, b},P, S), kde P = {S -í- e, S —> abA, A —> Saa, A -> b } 3.6 Zkonstruujte LL(3) analyzátor pro gramatiku G: G = ({S, A, B},{a, b},P, S), kde P = { S ^ aAaB, S 6A6P, A —> a, A —> ba, B ->• aP, P ->• a } 5 3.7 Najděte LL(1) analyzátor pro jazyk generovaný následující gramatikou: G = ({STAT, VAR, IDLIST}, {if, id, then, else, fi, while, do, od, (,), :=}, P, STAT) P = { STAT -> if id then STAT else STAT fi STAT while id do STAT od STAT VAR := VAR STAT id I (IDLIST) VAR -^id\id (IDLIST) IDLIST -^id\id (IDLIST) 3.8 Navrhněte gramatiku, která je LL(2) a není SLL(2). 3.9 Navrhněte gramatiku, která a) je SLL(3) a není LL(2) b) je SLL(2) a není LL(3) c) je LL(2) a není SLL(3) cl) je LL(3) a není SLL(2) 3.10 Navrhněte gramatiku, která není LL(k) pro žádné k. 6 Transformace LL(k) gramatik Motivace: • Gramatika je LL(1), právě když je SLL(Í). • Pro gramatiky, které jsou SLL(Í), se snadno konstruuje analyzátor. Platí: • Pro danou bezkontextovou gramatiku G je nerozhodnutelné, zda je LL(k) pro nějaké k > 0. • Je-li dána bezkontextová gramatika G a pevné k takové, že G není LL(k), pak je nerozhodnutelné určit, zda G má ekvivaletní gramatiku, která je LL(k). Navzdory výše uvedeným faktům existuje několik transformací, které zachovávají jazykovou ekvivalenci a které někdy vedou k LL(1) gramatice. Gramatika není LL(1) principielně ze dvou důvodů. Těmi jsou konflikt „first-first" a konflikt „first-follow". Správný postup řešení příkladu „převod na LL(1) gramatiku" obsahuje tyto tři kroky: nalezení konfliktů v transformované gramatice (pomocí ověření na LL(1)), odstranění konfliktů níže uvedenými postupy, ověření výsledné gramatiky na LL(1) (při nalezení konfliktů opakování předchozího kroku). V jednoduché L L {V) gramatice začínají všechny pravé strany pravidel terminálem, pravidla se stejnou levou stranou začínají různým terminálem. Odstranění levé rekurze 4.1 Odstraňte levou rekurzi v následující gramatice: G = ({S, A, B},{b, a, c},P, S), kde P = {S SAb I SBa I Sec \ AaB \ bc, A —> aAa \ e, B BbB j b } Rohová substituce Nechť G = (N, S, P, S) je bezkontextová gramatika s pravidlem A —>• Ba, a nechť všechny S—pravidla jsou B —> a\ I ci2 I • • • I am. Nechť G\ = (N', S, P', S) je gramatika, která vznikla z G vyloučením pravidla A —> Ba a přidáním pravidel A —> a±a \ a2a | ... | ama. Tato transformace nese název rohová substituce. Je zvláštní tím, že její opakovanou aplikací je možné z gramatiky, která je LL{\) a nemá e-pravidla, udělat jednoduchou LL{\) gramatiku. 4.2 Aplikujte rohovou substituci na následující gramatiku: G = ({S, A, B},{a, b, c, d},P, S), kde P = {S -> AB, A —> ab I Ba, B c j dB } 7 4.3 Aplikujte rohovou substituci na následující gramatiku: G = ({S, A, B},{a, b},P, S), kde P = {S -> AB, A ->• aA | e, B b A je} Levá faktorizace Pro LL(1) gramatiku musí platit: A a, A P => FIRST^a) n FIRST^/3) = 0 nesplnění této podmínky se označuje jako konflikt FIRST-FIRST. Kolizi může způsobit přítomnost pravidel tvaru A —> aa± \ aa2 \ ■ ■ ■ \ o:an, kde a =/= e. Kolizi odstraníme jestliže uvedená pravidla nahradíme pravidly tvaru A —> a A', A' —> a\ \ \ ■ ■ ■ \ OLn. Této transformaci se říká levá faktorizace. Většinou je nutné před touto transformací aplikovat na gramatiku rohovou substituci, aby konflikty uvedeného typu byly v požadované formě. 4.4 Opakovaně aplikujte levou faktorizaci na gramatiku: G = ({A, B, C},{a, b, c, d},P, A), kde P = { A —>• abB | acC \ acdB \ bBb, B bbaB j bbadC j cBC, C ^ aA j b } 4.5 Aplikujte levou faktorizaci na gramatiku: G = ({A,B,C},{a,x,y,z},P,A), kde P = { A —> aBxx | aCyy \ zy \ zx, B —> aBx | z, G ->• yCy | z } 4.6 Odstraňte konflikt FIRST-FIRST v následující gramatice. G = ({S, A, B},{c, a, b},P, S), kde P = {S -> A | B, A ->• cA \ a, B cB j b} 4.7 Odstraňte konflikt FIRST-FIRST v následující gramatice. G = ({A, B, C},{a, b, c, d},P, A), kde P = { A aB | CB, C aC j bB, B cB j d } 4.8 Odstraňte konflikt FIRST-FIRST v následující gramatice. G = ({A, B, D},{c, d, b, x, y, z},P, A), kde P = { A Bc \ Dd, B -)■ bx | y, D Bz} 4.9 Odstraňte konflikt FIRST-FIRST v následující gramatice. G = ({S, A, B},{b, c, a, d},P, S), kde P = {S A | AbcB | 6c, A —> a, B ^ A \ dd } 4.10 Odstraňte konflikt FIRST-FIRST v následující gramatice. G = ({S, A, B},{a, b, c},P, S), kde P = {S -> A | B, A ->• aA6 j e, S -)• aSc j e } 8 Pohlcení terminálního symbolu Pro LL(Í) gramatiku musí platit: A a, A s => FIRSTi(a) n FOLLOWi(A) = 0 nesplnění této podmínky se označuje jako konflikt FIRST-FOLLOW. Nechť {a} C FIRSTi^i) n FOLLOWi(A). Může to být způsobeno tím, že v gramatice je pravidlo následujícího tvaru: X —> aAaj3 a přitom A—pravidla jsou tyto: A —> 71 | ... | 7„. Konflikt se můžeme pokusit odstranit tak, že pravidlo X —> aAaj3 nahradíme pravidlem X —> a[Aa]/3 a pro nový neterminál [Aa] přidáme pravidla [Aa] —> 71a | .. . | 7na. Tím jsme z množiny FOLLOWi(A) vyloučili symbol a (za předpokladu, že tam není z jiného důvodu). 4.11 Řešte kolizi FIRST-FOLLOW v následující gramatice: G = ({A, B, C},{a, c, b},P, A), kde P = { A —>• BaC, B —> s I aaC, C -> c j bC } 4.12 Řešte kolizi FIRST-FOLLOW v následující gramatice: G = ({A, B, C},{a, c},P, A), kde P = { A —>• BaC", B -)• aS I e, C* -> c } Extrakce pravého kontextu Pohlcení terminálního symbolu je možné udělat pouze tehdy, vyskytuje-li se přímo za problematickým neterminálem. Situce ale může vypadat například takto: X —> aAYj3 a Yj3 =>+ aj. V tomto případě nelze přímo použít transformaci pohlcení terminálního symbolu, můžeme se však pokusit (opakovaně) substituovat za neterminál bezprostředně vpravo od neterminálu A a obdržet tak konflikt v požadované formě. Této transformaci říkáme extrakce pravého kontextu. 4.13 Pokuste se provést extrakci pravého kontextu a zamyslete se: G = ({S, A, B},{d, a, b, c},P, S), kde P = {S -> Ad, A -)• aAB I b I bbc \ s, B -> A } 4.14 Řešte kolizi FIRST-FOLLOW v následující gramatice: G = ({S, B, A, C},{a, b, d, c},P, S), kde P = { S aBAa \ bABb, A e j aC I BCd, B bB j CdC, C -> cC* I d } 4.15 Transformujte na LL(Í) následující gramatiku: G = ({E, T, F, S},{o, n, a, (, )},P, E), kde P = { E —>• £oT I T, T ToF j F, Ä -í- a I (F) } 4.16 Ověřte, zda je následující gramatika LL{\) gramatika. Pokud není, použijte standardní transformace na úpravu gramatiky na LL{\) a o výsledné gramatice dokažte, že je LL{\) gramatikou. G = ({S, A},{b, c, a},P, S), kde P = { S bcAa I bb, A ->• e j acAb } 9 LR(O) a SLR(k) analyzátory Poznámka ke konstrukci analyzátorů LR: Pro gramatiky, ve kterých se kořen gramatiky (nejčastěji neterminál S) vyskytuje na pravé straně nějakého pravidla zavádíme nový neterminál (nejčastěji označen X) a pravidlo X —> S, který se stává novým kořenem gramatiky. Tato modifikace je nutná pro korektní identifikaci situace, ve které má analyzátor úspěšně akceptovat. Pro gramatiky, ve kterých se kořen gramatiky nevyskytuje na žádné pravé straně pravidla gramatiky, není výše uvedená modifikace nutná. Přispívá však k čitelnosti výsledného analyzátoru. (K akceptování dojde vždy právě v jednom stavu položkového automatu, který je navíc při systematikcé konstrukci vždy druhým stavem položkového automatu.) LR(0) analyzátor 5.1 Zkonstruujte LR(0) analyzátor G=({S,A},{a,b,c},P,S), kde P = { S —> aAa, S —> aAb, A ->• abA, A b A, A —> ac } a analyzujte slovo aabbacb 5.2 Dokažte, nebo vyvraťte, že následující gramatika je LR(0). G = ({S, A, B, C},{a, b, c, d},P, S), kde P = { S —> aAa, S -> bBb, S —>• cCc, S —> dCd, A —> a | aA, B bA j Cc, C -> cA} 5.3 Zkonstruujte LR(0) analyzátor a analyzujte libovolné slovo G = ({S,A,C,B,D},{a,b,c, d},P, S), kde {S -> aAa, s - -> bAb, s - -> cCc, s - -> dCd, A - ■> B, B - ■> b, C - ■> D, D - -> d } SLR(k) analyzátor 5.4 Zkonstruujte SLR(Í) a SLR(2) analyzátor 10 G = ({S, A, B},{a, b},P, S), kde P = {S -> AB, A ->• aAb, A ->• e, S Ď } a analyzujte slovo aabbbb a aaabbb 5.5 Najděte všechny SLR(2) konflikty G = ({S, P, R},{a, b, c, d},P, S), kde P = {S PP, P ->• Ra, P ->• Ďižc, P ->• de, P —> 6da, R d } 5.6 Dokažte, že gramatika z příkladu 5.5 není SLR(k) pro žádné k. 5.7 Rozhodněte, zda následující gramatika je SLR(k) G = {{X, S, L, R},{=, i, d, *},P, X), kde P = {X -> S1, S1 —>• L = R, S —> R, L —> id, L *P, R L } 5.8 Zkonstruujte SLR(Í) analyzátor: G=({X, S,A},{+,(,),a},P,X),kde P = {X -> S1, S1 ->• S + A, S -> A, A -j. (5), A -> a(S), A ->• a } Liž(O) a SLR{k) gramatiky 5.9 Zkonstruujte LR(0) gramatiky Li = {1™ a 0™ | n > 0} U {1™ Ď O2™ | n > 0} L2 = {a 1™ 0™ j n > 0} U {6 1™ 02™ j n > 0} L3 = {1™ 0m | m > n > 0} L4 = Hwfl|iue{0, i}*} 5.10 Dokažte, že následující gramatika není LR(0) ale je SLR(Í) G=({X, S,A},{+,(,),a},P,X),kde P = {X -> S1, S1 ->• S + A, S -> A, A -j. (5), A -> a(S), A ->• a } 5.11 Nalezněte co možná nejjednoduší gramatiku takovou, že 11 a) není LR(0). b) není SLR(Í) protože má konflikt čtení-redukce. c) není SLR(Í) protože má konflikt redukce-redukce. 5.12 Ověřte, zdaje následující gramatika SLR(Í) či SLR(2) gramatika. G = ({X, S, B},{a, b},P, X), kde P = {X -> S, S —>• aB, S —> a, B -> bSb} 12 LR(k) a LALR(k) analyzátory 6.1 Rozhodněte, zda je gramatika LR(0), SLR(Í), LALR(l), LR(Í) G = {{X, S, A, B},{a, d, 6, e, c},P, X), kde P = {X -> S, S —> aAd, S bBd, S —> aBe, S -> bAe, A ->• c, B c } 6.2 Rozhodněte, zda je gramatika LR(0), SLR(Í), LALR(Í), LR(Í) G = ({X, S, A, B, C, D, E},{a, b},P, X), kde {x ■> S, s - -> AB, A - -> a, B - ■> CD, B - -> aE, C - -> ab, D - -> bb, E - -> bba } 6.3 Zkonstruujte LALií(l) analyzátor G = ({X, S, A, B},{a, b, c},P, X), kde P = {X -> S1, S1 —> aAb, S —>• c, S1 oB, A -> 6S1, A ->• Sc, B c } 6.4 Zkonstruujte iniciální stav LR(2) automatu G = ({S1, E},{+,a},P,5), kde P = {S R, R —>■ RR, R —>■ R + R, R ->• a } 6.5 Proveďte LR(Í) analýzu G = ({X, S1, A},{a, b},P, X), kde P = {X -> S1, S1 —>• aAS1, S1 -> e, A 66 } 13 6.6 Zkonstruujte analyzátor a analyzujte slova 00111 a 11110. G=({S,A,B},{0,l},P,S),kde P = {S -> AB, A 0A1, A ->• e, B LB, S ^ 1 } 14 Bisimulace 7.1 Pro daný přechodový systém najděte všechny dvojice bisimulačně ekvivalentních stavů metodou hry. Pomocí bisimulačního kolapsu k němu zkonstruujte ekvivalentní přechodový systém. 7.2 Pro daný přechodový systém najděte maximální bisimulaci metodou postupných aproximací. 7.3 Je dán přechodový systém Pi (nekonečně stavový). Zkonstruujte přechodový systém P2 takový, aby platilo: (i) P2 má stav I takový, že J ~ 1 (ii) P2 je konečně stavový Jaká je maximální bisimulace pro P\l Pv. 7.4 Najděte konečné automaty A\, A2 bez e-přechodů takové, aby splňovaly všechny tři následující podmínky: (i) C(A{) = C(A2) (ii) C{A\) je nekonečný (iii) Počáteční stavy automatů A\, A2 nejsou bisimulačně ekvivalentní 15 7.5 Dokažte nebo vyvraťte: 2 ~ 8. Najděte maximální bisimulaci. 7.6 Najděte nejmenší n, takové aby platilo 3 4, ale 3 4. Najděte maximální bisimulaci. Faktorizujte podle relace bisimulace. 7.7 Najděte nejmenší n, takové aby platilo 3 ^n 4, ale 3 4. Najděte maximální bisimulaci. Faktorizujte podle relace bisimulace. © a O a O 16 Přechodové systémy BPA a BPP 8.1 Otázky: • Je daný proces popsaný deterministickým konečným automatem. Jak zjistím, které stavy jsou bisimulačně ekvivalentní? • Najděte postačující podmínku na to, aby pro normovaný přechodový systém, byla jazyková ekvivalence shodná s bisimulací. • Pro normované BPA ověřte: ABC ~ DBC A ~ D • Najděte nutnou podmínku, aby pro BPA platilo A A ~ A. 8.2 Najděte přechodový systém, který je určen následující BPA algebrou. X A XBB I4e B A BBB BAs 8.3 Jaký jazyk generuje následující BPA (z proměnné X)l X A XA X A XB I4e A Ae BAs 8.4 Nakreslete přechodový systém určený BPP algebrou X A X\B X A X\D B As D A e (xAe) 17 8.6 Vyjádřete daný přechodový systém BPA syntaxí: Q> Q> C 8.7 Vyjádřete daný přechodový systém BPP syntaxí: C>T<>l-0 8.8 Vyjádřete daný přechodový systém BPA syntaxí: b s—n b 8.9 Vyjádřete daný přechodový systém BPP syntaxí: 18 Konstrukce tabel pro BPA Tablo pro 7 = ô se skládá z podtabel. Každé podtablo je strom. Podtablo s kořenem Xa = Y/3 vytvoříme následovně. Nechť k = mín{\\X\\, Na uzel Xa = Y/3 aplikujeme fc-krát trojici pravidel (REC, SUM, PREFIX). Po /j-aplikacích jsou některé uzly reziduály, jeden z nich označíme jako vytčený a podle něj aplikujeme na ostatní uzly v aktuálním patře pravidlo SUB (respektive SUBL, nebo SUBR). Reziduálem je uzel ve tvaru a = 7/? (použijeme pravdilo SUBL) nebo 7a = j3 (použijeme pravdilo SUBR), případně a = j3 (použijeme pravdilo SUB (tj. SUBL, nebo SUBR, na straně nezáleží)). Po aplikaci odpovídajícího pravidla SUB (a jen tehdy) obdržíme listy podtabla. Po dokončení podtabla, zkontrolujeme všechny jeho listy. U každého listu nastává jeden z následujících případů: • List je úspěšný. (Netřeba pro něj budovat podtablo.) • List je neúspěšný. Pak je celé tablo neúspěšné. • List není ani úspěšný ani neúspěšný, stává se kořenem nového podtabla. Jestliže v průběhu tvorby kteréhokoliv podtabla se některý uzel (nemusí to být nutně list) ukáže být neúspěšným podle níže uvedených kritérií, je neúspěšné celé tablo. Každé podtablo je téměř vyvážený strom. Všechny cesty v něm jsou stejně dlouhé, liší se maximálně o jedna (po aplikaci pravidla SUB,SUBL nebo SUBR se pod vytčeným reziduálem cesta neprodlouží, sám reziduál slouží jako list, a tedy případně i jako kořen dalšího podtabla, zatímco pod ostatními uzly na stejném patře se cesta prodlouží o jedna (díky aplikaci odpovídajícího pravidla SUB) , a teprve tyto uzly (o patro níž než je reziduál) tvoří listy daného podtabla). Kritéria úspěšnosti: 2. a = j3 a na cestě od tohoto listu do kořene celého tabla se vyskytuje uzel se stejným označením a = j3 a mezi nimi je alespoň jednou použito pravidlo PREFIX (uzel j3 = a se nepočítá!) Kritéria neúspěšnosti : 1. a.a = b.j3 ,kde a je různé od b 2. a = j3 ,kde \a\ je různá od \j3\ Poznámka: 1. Výše uvedená metoda funguje pouze pro NORMOVANÉ BPA !!! 2. Poznámka o zápisu: XY = X.Y 1. a a Pravidla Xa = Y/3 Ea = F P REC kde X dej E&Y dej F aa = aj3 PREFIX a = j3 19 (E™ i atat)a = (ELi bjPj)P {a,a,a = &/(í)/3/(í)/?}™ iWg(j)agU)a = bjí3jí3}]=i SUM kde / : {1,... g:{l,... m,n> 1 to} -)■ {1, ,n} ,to} gto; = /3j/3 a* 7 = A QijOi = /3i/3 &l = Pll 9.1 Zkonstruujte důkaz PQQ = SU SUBL SUBR p = aPQQ + bRQQ + c Q = c R = bP S = aSU + bT + c T = bSU U = cV V = c kde a = 7/3 je vytčený residual kde 7a = P je vytčený residual 9.2 Zkonstruujte důkaz FX = A, XCB = BCX, FBX = AB, CXB = XBB A = aBCX + aB B = aC C = aD D=bD + c F = a + aXC X= aY Y = aD 9.3 Dokažte DH - DFG, AH - AGF, EF ^ D, BA^ DG A = aBC + aD + aEF B = b C = c D=bH + bC E = bG F = c G = bA H= cBA 9.4 Zkonstruujte důkaz Y = C X = aYX + b Y = bX A = aC + b C = bAA 9.5 Zkonstruujte důkaz X = A X= aXX+ b + cY Y = aYX +b + cX A = aAA + b + cA 20 9.6 Zkonstruujte důkaz A = E A = aBC + aH B = b C = d + aDE D = bF F = c E = aC + aGH G = b H = d + al I = bK K = cA 9.7 Zkonstruujte důkaz A = X X = d + aXX + bY + cZ Y = bX + aYY + cZ + d Z = bX A = d + aAA + bA + cB B = bA 9.8 Zkonstruujte důkaz AB = XYB A = aB + aC X = a + aZ B = aB + a Y = aY + a Z = bZ + bX C = bC + bA 9.9 Zkonstruujte důkaz FBI = AB A = aBCI + aB B = aC C = aD D=bD + c F = a + alC I = aK K= aD Bůchiho automaty 10.1 Navrhněte nedeterministický BA pro jazyk všech w-slov nad abecedou £ = {a, b, c}, která obsahují nekonečný počet symbolů a. 10.2 Navrhněte nedeterministický BA pro jazyk všech w-slov nad abecedou £ = {a, b, c}, která obsahují nekonečný počet symbolů bac. 10.3 Navrhněte nedeterministický BA pro jazyk všech w-slov nad abecedou £ = {a, b, c}, která obsahují nekonečný počet symbolů b a c a pro která platí, že pokud libovolný konečný prefix slova obsahuje lichý počet symbolů b, pak obsahuje také sudý počet symbolů c. 10.4 Navrhněte nedeterministický BA pro jazyk L = {w = W1ÍÍJ2ÍIJ3 . .. I Wi G {a, b} pro i > 1, 3 nekonečně mnoho j G N takových, že Wj = Wj+4} 10.5 Nechť S = {0,1, Pro slovo w = a^aiciz ... G a dvě čísla i, j G N, 0 < i < j označme w[i, j] podslovo a>i ... cij. Pro pevně zvolené n G N definujme jazyk: Ln ={w I w G ((0 + a pro nekonečně mnoho i > 0 platí: w[2in, (2i + l)n - 1] ^ w[(2z + l)n, (2z + 2)n - 1]}. Popište dva nedeterministické BA A\, A2 velikosti 0(n) takové, aby Ln = L{A{) n L(Ä2). 10.6 Dokažte, nebo vyvraťte: Ke každému NBA A lze zkonstruovat NBA A' s jediným počátečním stavem. 10.7 Nechť jazyk L = {w G {0, 1}" | buď 0 £ inf(w), nebo 1 £ inf(w)}. a) Zkonstruujte nedeterministický BA. b) Diskutujte, zda je možné sestrojit pro daný jazyk NBA s jedním akceptujícím stavem. c) Dokažte, že pro daný jazyk nelze sestrojit NBA s jedním akceptujícím stavem. 10.8 Konstruujte NBA pro následující jazyky L nad abecedou {a, b, c, d}. a) L = {w inf(w) = {a}} b) L = {w inf(w) = {a,b}} c) L = {w a G inf(w)} d) L = {w a G inf(w) A c ^ inf(w)} e) L = {w {a, b} C inf(w) A d ^ inf(w)} f) L = {w {a, b} C inf(w)} 10.9 Buď A konečný automat. Označme L(-A) množinu slov, kterou akceptuje konečný automat A. Označme LUJ(A) množinu w-slov, kterou akceptuje Bůchiho automat A. Najděte automat A tak, aby platilo a) (L(A)r = LU(A) b) (L(A)r ŕ L„(A) 10.10 Pro jazyk L = {w G {a, b}" \ inf(w) = {a, b}} navrhněte deterministický Mullerův automat, deterministický zobecněný Bůchiho automat a deterministický Bůchiho automat. 22 Logika MSO 11.1 Definujte základní syntax logiky MSO. 11.2 Buď S abeceda a w G S* konečné slovo, buď p sentence (formule bez volných proměnných) logiky MSO. Definujte, kdy w \= p. 11.3 Definujte následující syntaktické zkratky: a) x < y, x>y, x = y b) Vx e X : p c) 3x e X : p d) first(x) — x je první pozice v neprázdném slově. e) last(x) — x je poslední pozice v neprázdném slově. f) succ(x,y) — x < y a pozice x a y bezprostředně sousedí (též značeno jako x 0} 11.6 Popište jazyky nad abecedou {a, b}, které jsou dány následujícími sentencemi logiky MSO: a) 3x3y\fz : (x < z A x < y A (z < y x = z) A Qa(y)) b) 3X : [Vx, y : (succ(x, y) => (x G X ^> y ^ X)) A AVi:(i£l^> (Qa(x) A ^first(x)))} 11.7 Jaká třída jazyků je popsatelná logikou MSO? 11.8 Jaká třída jazyků je popsatelná logikou prvního řádu? 23 Plán cvičení Cvičení 1 — FIRST, FOLLOW, SLL(k) • Zopakujte, jak funguje nedeterministická analýza metodou shora dolů; v čem tkví nedeterminismus metody, jak ho lze řešit. (Motivace pro FIRST a FOLLOW.) • Definujte funkci FIRST a na jednoduchých příkladech ukažte, co počítá. — Ukažte intuitivní výpočet hodnoty funkce FIRST " rozbalováním". — Vysvětlete operátor ffife a uveďte, že FIRSTk(ABC) = FIRSTk(A) ®fe FIRSTk(B) ®fe FIRSTk{C). — Pozor na A —> aA \ b versus A —> aA • Definujte funkce FOLLOW a na jednoduchých příkladech ukažte, co počítá. — Ukažte problém, kdy pravá strana pravidla není dostatečně "dlouhá"pro výpočet hodnoty FOLLOW. — Vysvětlete, jak se sestavují rovnice definující hodnoty FOLLOW. — Připomeňte, že e e FOLLOWk(S) • Procvičujte funkce FIRST a FOLLOW na příkladu 1.4 • Definujte SLL(k) • Řešte příklad 2.1 • Řešte příklad 2.3 Cvičení 2 — LL(k) a Transformace na SLL(l) • Připomenutí definice LL(k). • Demonstrace rozdílu mezi LL(k) a SLL(k) na příkladu 3.1 • Příklad 3.2 • Sestrojte analyzátor ke gramatice z příkladu 3.2, nebo řešte příklad 3.6 • Vysvětlete konflikty FI-FI a FI-FO. • Zmínit odstranění levé rekurze (konflikt FI-FI) a odkázat na předchozí kurz. • Odstranění konfliktu FI-FI — Rohová substituce (Vysvětlete rozdíl rohová versus obecná substituce.) — Levá faktorizace 24 — Vymyslete příklad gramatiky, na které demonstrujete výše uvedené. • Převod FI-FO na FI-FI — Pohlcení terminálního symbolu — Extrakce pravého kontextu — Vymyslete příklad gramatiky, na které demonstrujete výše uvedené. • Demonstrujte, že algoritmické řešení nevede vždy k cíli. • Příklad 4.6 • D.Ú. Příklad 3.9 Cvičení 3 — LR(0) a SLR(k) • Připomenutí principu analýzy zdola nahoru. — V čem je tato analýza nedeterministická? — Nástroje pro řešení nedeterminismu: * Nahlížení na k-symbolů na vstupu. * Analýza zásobníku (Charakteristický automat) • Příklad 5.1 — Sestrojení charakteristického automatu — Definice akcí automatu dle jednotlivých položek * čtení: položka s terminálem za tečkou * redukce: položka s tečkou na konci — LR(0) konflikty — Přepis do tabulky nalyzátoru (striktně oddělujte GOTO a ACTION část tabulky!) — Analýza vybraného slova. • Příklad 5.4 — Konstruujte přímo SLR(2) — Po úspěšné konstrukci rozhodněte a odůvodněte SLR(l) a LR(0) • Ve zbývajícím čase nebo na doma řešte příklad 5.11 Cvičení 4 — LR(k) a LALR(k) • Příklad 6.1 — Počítejte jako LR(1) — Poté diskutujte LR(0) a SLR(l) (zde je demonstrován rozdíl SLR(k) a LR(k)) — Motivace pro LALR(k) • Příklad 6.3 — Diskutujte, jaké LALR konflikty mohou vzniknout pro k = 1. — LALR není to, že sloučím stavy, které nevytvoří sloučením konflikt. 25 • Příklad 6.4 — Demontrace, že je třeba poctivě počítat uzávěr z každé položky. • Diskuze o vztazích SLR(k) => LALR(k) LR(k). • Obměna předchozího. Cvičení 5 • Připomňte se definici relace bisimulace • Příklad 7.1 — Bisimulační hrou určete ekvivalentní stavy. • Příklad 7.2 • Příklad 7.3 — různé relace bisimulace. — relace bisimulace, které nejsou relacemi ekvivalence. — Ukažte, jak intuitivně počítat bisimulační uzávěr pro vybranou dvojici (např. (1,2)). • Příklad 8.2 • Příklad 8.4 • Příklad 8.5 • D.U.: Ostatní příklady z kapitoly 8. Cvičení 6 — Bůchi automaty a MSO Logika • Na příkladu {w G {a, b}^ \ w má nekonečně mnoho a} vysvětlete princip Bůchi automatů. • Příklad 10.1 • Příklad 10.2 • Příklad 10.8 • Příklad 10.7 — čárka před nebo indikuje vylučovací poměr! • Příklad 11.1 • Příklad 11.2 • Příklad 11.3 • Příklad 11.4 • Příklad 11.5 • Příklad 11.6 • Příklad 11.7 • Příklad 11.8 Na systému 26 Řešení některých příkladů 1.2 Výpočet Fl2(A) provedeme z pedagogických důvodů zcela algoritmicky. Nej prve sestavíme příslušné rovnice: FI2(A) = FI2(B)®2{c} U {a} FI2(B) = FI2(A) U FI2(C) U {d} f/2 (C) = FI2(B) U {d} Nyní spočítáme pevný bod rovnic tak,že v každé iteraci používáme striktně hodnoty z předchozí iterace. Poslední sloupec obsahuje výsledné hodnoty. 0 1 2 3 4 5 6 A 0 {a} {dc, a} {dc, ac, a} {dc, ac, a} {dc, ac, a} {dc, ac, a} B 0 {d} {a, d} {dc, a, d} {dc, ac, a, d} {dc, ac, a, d} {dc, ac, a, d} C 0 {d} {d} {a, d} {dc, a, d} {dc, ac, a, d} {dc, ac, a, d} Pro zajímavost ukážeme, že pokud použijeme v každé iteraci nejnovější známe hodnoty, výpočet se může výrazně urychlit. Výsledek je však shodný. 0 1 2 3 A 0 {a} {ac, dc, a} {ac, dc, a} B 0 {a, d} {ac, dc, a, d} {ac, dc, a, d} C 0 {a, d} {ac, dc, a, d} {ac, dc, a, d} FI2(A) = {ac, dc, a} FI^(Ae) = {ae, dce, ace, dcc, acc} 1.3 FI2(A) = {b,ba}, FI3(A) = {b,ba,baa} 1.4 FIi(BBb) = {a,b} FI2(BBb) = {ad, aa, ab, b} FOi(A) = {c} FO^S) = FOi(S) = FOi(C*) = {e,d,e} F03(A) = {cde, cec, c} FC>3(S) = FO^(C) = {ecd, ece, dec, ec, e} Fh(SAcB) = {a,b,c} FI^SAcB) = {aaaa, aaab, aaac, aaba, aabd, aabe, aac, aaca, aacb, aacc, abaa, abab, abac, abad, abae, abde, abec, ac, aca, acaa, acab, acac, acad, acba, acbd, acbe, acc, acca, adaa, adab, adac, adba, adbd, adbe, adc, adca, baaa, baab, baac, baba, babd, babe, bacd, bace, badd, bade, baec, bdec, bec, beca, c, ca, cad} 1.5 F01{S) = F01[D) = {e,a,c,d,y} FO^A) = {a,b,c, d, x} FOi(S) = {e, a, b, c, d, y} FOi(C) = {e, a, b, c, d, y, z} F02(S) = {e, da, db, dc, dd, dx, c, ca, cb, cc, cd, cy, aa, ab, ac, ad, ax, y, ya, yb, yc, yd, yy, yz} 1.6 Pozor, gramatika není normovaná, a tudíž generuje prázdný jazyk. 27 2.1 Není SLL(2), konflikt nastává na pravidlech Y —>• a | e. 2.2 Není SLL(3), konflikt nastává na pravidlech A —>• a \ ab. 2.3 Nejprve pro každé pravidlo tvaru A —> a spočítáme množinu FI2(a) ©2 F02(A): 1 S- > aAaA F72(aAaA) ffi2 ^(S1) = {aa, ac} 2 S- > aBaB FI2(aBaB) ®2 F02(5) = {aĎ} 3 A- ■> r72(aA) ®2 F02(A) = {aa, ac} 4 A- ■> c r72(c) ®2 F02(A) = {ca, c} 5 B - -> 6D FI2(bD) ffi2 F02(S) = {bb, ba, b} 6 D - -> 6D r72(6£>) ffi2 F02(D) = {bb, ba, b} 7 D - -> e FI2(e) ffi2 F02(C) = {ab, e} Nyní snadno zkonstruujeme tabulku přechodové funkce analyzátoru. Prázdná políčka znamenají, že analyzátor v odpovídající situaci vrátí chybu, protože analyzované slovo není generováno gramatikou G. aa ab ac ba bb bc ca cb cc a b c e S A B D aAaA, 1 aA,3 aBaB, 2 e, 7 aAaA, 1 aA,3 bD,5 bD, 6 bD,5 bD, 6 c,4 bD,5 bD, 6 c, 4 e, 7 a b c ČTI ČTI ČTI ČTI ČTI ČTI ČTI ČTI ČTI ČTI ČTI ČTI $ Zpravidla se uvádí pouze „zajímavá" část tabulky, t.j. bez řádků pro terminály a pro $ a bez sloupců, které by následně zůstaly prázdné: aa ab ac ba bb ca b c e S aAaA, 1 aBaB, 2 aAaA, 1 A aA, 3 aA, 3 c,4 c, A B bD,b bD,b bD,b D e,7 bD,6 bD,6 bD,6 e,7 Analýza slova acaac: (acaac,S$,e) |— (acaac,aAaA%,\) (caac, AaA%, 1) |— |- (caac, caA%, 14) |^ (aac, aA%, 14) |-^ (ac,A$, 14) |- |- (ac,aA$, 143) |^ (c,A$, 143) |- (c,c$, 1434) \^ Y~ (e, $, 1434) =>• akceptuje Analýza slova abaac: (abaac, S$,e) \— (abaac, aBaB%,2) (baac, BaB%,2) |— |— (baac, bDaB%, 25) (aac, DaB%, 25) =>■ zamítá 2.4 Zajímavá část tabulky SLL(3) analyzároru vypadá takto: baa bab aaa aab aba aa ab a b S baAa, 1 baBb, 2 A aA, 3 aA, 3 aB,4 aB,4 aB,4 B bA,b bA,b e, 6 e, 6 28 3.6 Nejprve zkonstruujeme pomocné LL(3) tabulky: T0 = (S,{e}) S- ■> aAaB aaa, aba {aa,aaa},{e} S - * bAbB bab, bba {ba, baa}, {s} Ti = (A, {aa,aaa}) A - ■> a aaa — A - ■> ba baa — T2 = (B,{e}) B - -> aS aa,aaa {e} B - -> a a — = (A, {ba, baa}) A - ■> a aba — A - ■> 6a bab — Nyní zapíšeme tabulku přechodové funkce analyzátoru. Uvádíme pouze zajímavou část tabulky, tj. řádky popisující situaci, kdy je na vrchovu zásobníku nějaké Ti, a sloupce, které jsou v těchto řádcích tabulky neprázdné. Zbytek tabulky obsahuje pokyn CTI, je-li na vrcholu zásobníku terminál shodný s terminálem na vstupu, a AKCEPTUJ, je-li na vrcholu zásobníku jeho dno $ a celý vstup je přečtený (na vstupu je e). Ve všech ostatních případech (včetně prázdných buněk uvedené části tabulky) analyzátor vrátí chybu, protože analyzované slovo není generováno gramatikou G. aaa aba bab bba baa aa a T0 aT\aT2, 1 aT\aT2, 1 bT3bT2,2 bT3bT2,2 Ti a, 3 ba, A T2 aT2, 5 aT2,5 a, 6 T3 a, 3 ba, 4 4.6 Levá faktorizace na tomto příkladu „cyklí". Jazykově ekvivalentní jednoduchá LL(1) gramatika je například ({S}, {a, b,c},{S —>• a \ b \ cS}, S). 4.10 V této gramatice nelze požadovanou transformací odstranit konflikt. Samozřejmě existuje jiná gramatika, která je s touto jazykově ekvivalentní a je LL(1). 4.12 A -)• [Ba]C, [Ba] ->• a[Ba] \ a, C c 6.3 LR(1): 29 0 X - -> .s e S 1 S - -> .aAb e a 2 s - -> .c e c 3 s - -> .cB e c 3 1 x - -> S. e Accept 2 s - -> aAb e A 4 A - -> .bS h b 5 A - .Bc h B 6 B - ->• .c c c 7 3 S - -> c. e r(S —►c) S - -> c.B e B 8 B - ->• .c e c 9 4 S - -> aA.b e b 10 5 A - -> b.S h S 11 S - -> .aAb h a 12 S - -> .c h c 13 S - -> .cB h c 13 6 A - B.c h c 14 7 B - ->• c. c r(B c) 8 S - -> cB. e r(S —> cB) 9 B - ->• c. e r(B c) 10 S - -> aAb. e r(S —> aAb) 11 A - -> bS. b r(A bS) 12 S - -> a.Ab b A 15 A - -> .bS b b 5 A - .Bc b B 6 B - ->• .c c c 7 13 S - -> c. b r(S —> c) S - -> c.B b B 16 B - ->• .c b c 17 14 A - Bc. b r(A Bc) 15 S - -> aA.b b b 18 16 S - -> cB. b r(S —> cB) 17 B - ->• c. b r(B c) 18 S - -> aAb. b r(S —> aAb) LALR(l): Položkový automat LALR(l) analyzátoru vznikne z položkového automatu LR(1) analyzátoru spojením stavů 2,12 a 3,13 a 4,15 a 7,9,17 a 8,16 a 10,18. Každý nové vzniklý stav jsme označili nejnižším číslem z původních stavů. Položkový automatu tedy bude vypadat takto: 0 X —> .S e S i S —>■ .aAb e a 2 S —>■ .c e c 3 S —>■ .cB e c 3 1 X —> S. e Accept 2 S —>■ a.Ab e, b A 4 A —>■ .bS h b 5 A —>■ .Bc h B 6 B —> .c c c 7 3 S —>■ c. e,b r(S —►c) S —>■ c.B e,b B 8 B —> .c e,b c 7 ::= Qa(x) \ x aA.b e,b b 10 5 A - -> b.S b S 11 S - -> .aAb b a 2 S - -> .c b c 3 S - -> .cB b c 3 6 A - B.c b c 14 7 B - ->• c. e,b,c r(B—> c) 8 S - -> cB. e,b r(S^ cB) 10 S - -> aAb. e,b r(S^ aAb) 11 A - -> bS. b r(A — > bS) 14 A - Bc. b r(A — * Bc) (p ::= LJa(x) | x < y \ x g A | ^• (p), kde \/xip = ^(3x —iip) c) 3x (x g X A y) d) Vy (x < y) e) Vy (y < x) f) (x < y) A (x < z A z < y) a) 3 x b) y x c) Vx d) y x e) Vx (Qa(x) A Qb(x)) —ifirst(x) (first(x) A Qa(x)) A 3y : first(y) Qa(x) Qa{x) A 3y : Qa(y) 30 f) 3x : (Qb(x) A last(x) A Vz : (z < x =^> Qa(z))) g) 3X : (i x : (first(x) =^i£l)A A Vx g X : 3y, z ^ X : (succ(x, y) A succ(y, z) A (last(z) V 3v g X : succ(z, f)))) 11.6 a) {a, b}.{a}.{a, b}*, tj. na druhé pozici je a; b) {w g S* | w má na každé sudé pozici písmeno a} 31