Faculty of Informatics Masaryk University Brno Cvičení k předmětu IA006 Vybrané kapitoly z teorie automatů poslední modifikace 16. ledna 2014 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 s } Operace k:w a L\ (Bk L2 Nechť k G N je přirozené číslo, w je slovo a L\,L2 jsou jazyky. Operace k:w a L\ (Bk 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 I w G 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\ (Bk 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, E, P, S) je bezkontextová gramatika. Pro každé k G N jsou funkce FIRST^ a FOLLOW^ definovány následovně: FIRSTfr : (X U N)* —> 2S* FIRST^a) = {k : w \ a w, w G S*} FOLLOW^ : N —> 2S* FOLLOW%{A) = {w I 5 =^>* 7A*, w e FIRST%(a) ; 7, a G (EU W)*} Pozor na typ argumentu u jednotlivých funkcí. Argumentem funkce FIRST^(a) je řetězec terminálů a neterminálů (a G (E U N)*), na rozdíl od funkce FOLLOW1^(A), jejíž argumentem je vždy právě jeden neterminál (A G iV). 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^. FIRST% : 2^UNy —> 2S* FOLLOW^ : 2N —> 2S* FIRST^(M) = (JaeM FIRSTf^a) FOLLOW^(M) = UAeM .FOLLOWf (A) Dále budeme používat zkrácené zápisy funkcí, FIk(a) pro FIRST1^(a) a FOfc(A) 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, T,, P, S) a řetězec a — Y1Y2 ■ ■ ■ Y,, kde každé y G N U E U {e}. 1) FIk(x) = {x} pro x G X, f/fc(e) = {e} 2) Výpočet FIk(x) pro x £ N: Nechť iV = {-Xi, -X2, ■ ■ ■, Xn}. Budeme počítat hodnotu Flk(Xi) současně pro všechny neter-miná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: •v, ■y;...y!l v,-...^' ... v/ Potom f/fc(Xi) = (fj^1) efe f/^y,1) ©fc ... efe f/fc(y£)) u U (FIk(Y?) ©fe Fh(YÍ)®k ... ®fc f/fc(y/2)) U U (f/fc(y/) 0fe FIk(YÍ)@k ... ©fc FIk(YÍ.)) 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) = FhiY,) ©fc FIk(Y2) ©fc • • • ©fc f/fc(y,) Algoritmus pro výpočet funkce FOLLOW Je dána gramatika G — (N,~Ľ, 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{ß)®kFOk{B) {B^>uAß)eP Pro kořenový neterminál S klademe: FOk(S) — {e} U (J FIk{ß) ®k 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©feF/fc_„(L2) pokud n < A; {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(E) ekvivalentním výrazem FI3{aBcD)®3FO\{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 FI3(Ae) pro gramatiku G = ({A, B, C, P},{c, a, d, e},P, A), kde P — { A Bc | n, B A \ C \ d, C -> B \ d, D e } 1.3 Podle algoritmu řešte FI2(A) a FI3(A) pro gramatiku G=({A},{a,b},P,A), kde P = { A Aa, A -> 6 } 1.4 Vypočítejte F/i(BBb), FI2(BBb), FO^A), FOi(S), FOi(P), FOi(C), F03(A), F03(S), F03(C), Fh(SAcB), FI±{SAcB) pro následující gramatiku: G= ({S,A£,C},{n,c,&,e,d},P,S), kde P = {5 -> oAc | fl, A -> íM j 6SCe | e, B aC j e, C -> d je} 1.5 Podle algoritmu řešte FOk{X), kde & = 1,2,3,4 a X e {5, A, P, C, P} pro následující gramatiku: G = ({5, A, B,C,D},{a,b,d, c,x,y,z},P,5), kde {5 - -> oABbCD A - ■> ASrf B - ■> SAc xC | e C - -> 5y Cz e D - -> aPP e} 1.6 Vypočítejte F0fe(X), kde fc = 1, 2, 3,4 a X e {5, A, B, C, D} pro následující gramatiku: G = ({5, P, A, P, C},{a, c, b, d},P, S), kde {S - -> aPrP, A - -> B - -> PAc bA, C - -> cPc aaB, D - -> of \ dC} 1.7 Zamyslete se, v jakých případech platí následující vztahy: a) FJfc(A)=0 e) FOk{Ä) = 0 b) eeP/fe(A) c) FA(A)CF/W(A) d) FÍHi(A)CF4(A) f) eeFOk{Ä) g) POfe(A) C POA.+1(A) h) POfc+i(A) C FOk(Ä) 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 A e N a pro každá dvě různá pravidla A —> ß, A —> 7 platí: FIk(ß) ®k FOk(A) n ŕ7fc(7) 0fe FOk{Ä) = 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 aAaß I A —>• a I ad, B ^ aB ja} 2.3 Navrhněte SLL(2) analyzátor pro následující gramatiku a analyzujte slovo acaac a slovo abaac. G = ({5, A, B, Z?},{a, c, 6},P, 5), kde {S -> aAaA, s - -> aBaB, A - -> aA, A - -> c, B - -> Ď£>, D - -> Ď£>, D - ■> ^ } 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 6aAa, S —>• baBb, A ->• aA, A ->• aB, B e } 4 LL(k) gramatiky a analyzátory Gramatika je LL(k) , právě když pro dvě libovolná různá pravidla gramatiky A —> ji, A —> 7 a pro všechny nejlevější větné formy tvaru wAa platí: FIk{j3 ■ a) D Fl^ip/ ■ a) — 0 Gramatika je LL(l) 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 LL(2): G=({S,X,Y},{b,a},P,S), kde P — { S -> X, X Y I bYa, Y a \ s } 3.2 Ověřte, zdaje následující gramatika LL(3): G — ({S, A, B},{a, b},P, S), kde P — { S aAaB \ bAbB, A —>• a I ad, P ^ aP ja} 3.3 Ukažte, že gramatika není LL(k) pro žádné /j: G = ({5, A, B},{a, b, 0,1},P, S), kde P = { 5 -> A I B, A ->• aA6 j 0, B aBbb j 1 } 3.4 Ukažte, že gramatika je L L (k): G = ({5, T, A, P}, {a, 6, c}, P, 5), kde P = {S aT T SA I A A^rbB j c P -> 6*-^ j e 3.5 Zkonstruujte LL(2) analyzátor pro gramatiku G: G — ({S, A},{a, b},P, S), kde P = {S e, 5 —>• afe-A, A —> Saa, A -> 6 } 3.6 Zkonstruujte LL(3) analyzátor pro gramatiku G: G=({S,A,B},{a,b},P,S), kde P = { S aAaB, S bAbB, A —>• a, A —>• 6a, P aP, P a } 5 3.7 Najděte LL(1) analyzátor pro jazyk generovaný následující gramatikou: G = {{ST AT, VAR, IDLIST}, {if, id, then, else, fi, while, do, od, (,), :=}, P, ST AT) P = { ST AT if id then ST AT else ST AT fi ST AT —> while id do ST AT od ST AT VAR := VAR ST AT -> id | (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í 5LL(3) d) je LL(3) a není SLL(2) 3.10 Navrhněte gramatiku, která není LL(k) pro žádné 6 Transformace LL(k) gramatik Motivace: • Gramatika je LL(1), právě když je SLL(Í). • Pro gramatiky, které jsou SLL(1), 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(Í) gramatice. Gramatika není LL(Í) 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(Í) 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(Í) (při nalezení konfliktů opakování předchozího kroku). V jednoduché LL(Í) 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, E, P, S) je bezkontextová gramatika s pravidlem A —>• Ba, a nechť všechny B—pravidla jsou B ->• a± I a2 I ■ ■ ■ I Oím. Nechť G\ — (N',~Ľ,P',S) je gramatika, která vznikla z G vyloučením pravidla A —> Ba a přidáním pravidel A —> a\a \ a^a | ... | 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(l) a nemá e-pravidla, udělat jednoduchou LL(l) 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 L L (í) gramatiku musí platit: A a, A P => FIRSTi (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\ \ aa^ | ■ ■ ■ | aa„, kde a/e. Kolizi odstraníme jestliže uvedená pravidla nahradíme pravidly tvaru A —> a A1, A1 —> a± \ \ ■ ■ ■ | a„. 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, £?, C},{a, x, y, z},P, A), kde P — { A —> aBxx | aCyy \ zy \ zx, B —> aBx | z, C ->• yCy \ z } 4.6 Odstraňte konflikt FIRST-FIRST v následující gramatice. G = ({5, A, 5},{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, £?, C},{a, b, c, d},P, A), kde P — { A aB | OB, C -> aC j 65, B ^ cB \ d } 4.8 Odstraňte konflikt FIRST-FIRST v následující gramatice. G = ({A, £?, £>},{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 = ({5, A, B},{6, c, a, d},P, 5), kde P = { 5 ->• A | AbcB | 6c, A —>• a, B ^ A | dd } 8 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, B aBc j s } Pohlcení terminálního symbolu Pro L L (í) gramatiku musí platit: A a, A e FIRST^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 —> aAafí a přitom A—pravidla jsou tyto: A —> 71 | ... | 7„. Konflikt se můžeme pokusit odstranit tak, že pravidlo X —> aAafí nahradíme pravidlem X —> a[Aa]f3 a pro nový neterminál [Aa] přidáme pravidla [Aa] —> 71a | ... | 7n«- 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 —>• e I aaC, C ->■ c j bC } 4.12 Řešte kolizi FIRST-FOLLOW v následující gramatice: G = ({A, £?, C},{a, c},P, A), kde P = { A PaC, B ^ aB \ 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 =>+ arf. 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 \ e, B -> A } 4.14 Řešte kolizi FIRST-FOLLOW v následující gramatice: G = ({5, P, A, C},{a, b, d, c},P, S), kde P — { S aPAa I A e j aC I PCd, P ->■ bB j CdC, C ->■ cC \ d } 4.15 Transformujte na LL(1) následující gramatiku: G = ({P, T, P, S},{o, n, a, (, )},P, P), kde P = { P PoT I T, T ToF j P, P -> nS \ S, S ^ a I (P) } 9 4.16 Overte, zda je následující gramatika LL(1) 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 | bb, A ->• e j acA6 } 10 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 bA, 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 - ■> 5, B - ■> 6, C - ■> D - ■> d } SLR(k) analyzátor 5.4 Zkonstruujte SLR(Í) a SLR(2) analyzátor 11 G — ({S, A, B},{a, b},P, S), kde P — { S -> AB, A ->• aAb, A ->• e, P> ^ 6 } a analyzujte slovo aabbbb a aaabbb 5.5 Najděte všechny SLR(2) konflikty G = ({5, P, i?},{a, 6, c, ti},P, S), kde P = { S PP, P Ra, P bRc, P cíc, P —>• 6cia, 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, 5, L, iž},{=, i, ti, *},P, X), kde P = {X -> 5, S —>• L — R, S —^ P, L —>• id, L *R, R L } 5.8 Zkonstruujte SLR(Í) analyzátor: G=({X, S,A},{+,(,),a},P,X),kde P = {X -> 5, 5 -> 5 +A, 5 -> A, A (S), A -> a(5), A ->• a } Liž(O) a SLR(k) gramatiky 5.9 Zkonstruujte LR(0) gramatiky L\ — {1™ a 0™ | n > 0} U {1™ 6 O2™ | n > 0} L2 = {a 1™ 0™ j n > 0} U {6 1™ 02™ j n > 0} L3 = {1™ 0m | m > n > 0} L4 = {w#wfl|we{0,l}*} 5.10 Dokažte, že následující gramatika není LR(0) aleje SLR(Í) G=({X, S,A},{+,(,),a},P,X),Me P = {X -> 5, 5 -> 5 +A, S ^ A, A (5), A -> a(5), A ->• a } 5.11 Nalezněte co možná nej jednoduší gramatiku takovou, že 12 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} 13 LR(k) a LALR(k) analyzátory 6.1 Rozhodněte, zdaje gramatika LR(0), SLR(Í), LALR(Í), LR(Í) G = {{X, S, A, B},{a, d, 6, e, c},P, X), kde P = {X -> 5, S —>• aAd, S bBd, S —>• aBe, S -> 6Ae, A ->• c, S c } 6.2 Rozhodněte, zdaje gramatika LP(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 - -> aF, C - -> a6, D - -> 66, E - -> 66a } 6.3 Zkonstruujte LALR(Í) analyzátor G = ({X, S, A, B},{a, 6, c},P, X), kde P = {X -> 5, S —>• aA6, 5 —>• c, 5 cP, A -> 65, A Pc, P c } 6.4 Zkonstruujte iniciální stav LR(2) automatu G = ({5,iž},{+,a},P,5), kde P = { 5 P, P —> PP, P —> R + P, P a } 6.5 Proveďte LR(Í) analýzu G = ({X, S, A},{a, b},P, X), kde P = {X -> 5, íS' ^ aAS, S -> e, A 66 } 14 6.6 Zkonstruujte analyzátor a analyzujte slova 00111 a 11110. G = ({S, A, B},{0,1},P, S), kde P — { S -> AS, A (L41, A ->• e, S 15, 5^1} 15 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 P\ (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 P^ 1 )^-T2T^-T3T^-T4T^-T5^ 6 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{Ai) je nekonečný (iii) Počáteční stavy automatů A\, A2 nejsou bisimulačně ekvivalentní 16 7.5 Dokažte nebo vyvraťte: 2^8. Najděte maximální bisimulaci. 7.6 Najděte nejmenší n, takové aby platilo 3 ^n 4, ale 3 4. Najděte maximální bisimulaci. Faktorizujte podle relace bisimulace. 0^0 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 17 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 aa ~ a. 8.2 Najděte přechodový systém, který je určen následující BPA algebrou. x A xbb b A bbb bAs 8.3 Jaký jazyk generuje následující BPA (z proměnné x)r< x A xa xAxb xAs a As bAs 8.4 Nakreslete přechodový systém určený BPP algebrou x A x\b x A x\d b As d As (xAs) 8.5 Vyjádřete daný přechodový systém BPA i BPP syntaxí: 18 8.6 Vyjádřete daný přechodový systém BPA syntaxí: Q> Q> Q> 8.7 Vyjádřete daný přechodový systém BPP syntaxí: 8.8 Vyjádřete daný přechodový systém BPA syntaxí: 8.9 Vyjádřete daný přechodový systém BPP syntaxí: 19 Konstrukce tabel pro BPA Tablo pro 7 — ô se skládá z podtabel. Každé podtablo je strom. Podtablo s kořenem Xa — Yj3 vytvoříme následovně. Nechť k — mín{\\X\\, ||y||}. 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/3 (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 = Yfi Ea = F P REC kde Xd= E &Y d= F aa — af3 PREFIX a — j3 20 -SUM kde <7 :{!,■■■ to, n > 1 ,m} ->• {1, n}-►{!,. ,n} , to} QtQ = /3t/3 a47 = ft on = ft 7 9.1 Zkonstruujte důkaz PQQ = í>P P = aPQQ + 6PQQ + c 0 = c i? = 6P 5 = aSP + bT + c T = 65t/ P = y = c SUBL SUBR kde a = 7/3 je vytčený residual kde 7a = /3 je vytčený residual 9.2 Zkonstruujte důkaz FX = A, XCP = BCX, FBX = AS, C7XB = IBB A = aPCX + aP P = aC C = aP P = bD + c F = a + aXC x = ay y = aP 9.3 Dokažte PP - DFG, AH ~ AGF, EF ^ D, BA^ DG A = aPC + aP + aPP P = 6 C = c P = &p + bC E — bG F = c G = if = cPA 9.4 Zkonstruujte důkaz y = C X = aYI + 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 21 9.6 Zkonstruujte důkaz A — E A = aBC + aií B = b C = d+aDE Z? = bF f1 = c £ = aC + aGH G = b iř = d+ al J = bK lf = 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 = A = aB + aC X — a + Z? — aB + a Y = oY + a Z — bZ + bX C =bC +bA 9.9 Zkonstruujte důkaz FBI = A = aBCJ + aB 5 = aC C = aD D=bD + c F — a + alC I = aK K= aD Buchiho automaty 10.1 Navrhněte nedeterministický BA pro jazyk všech cj-slov nad abecedou E — {a, b, c}, která obsahují nekonečný počet symbolů a. 10.2 Navrhněte nedeterministický BA pro jazyk všech cj-slov nad abecedou E — {a, b, c}, která obsahují nekonečný počet symbolů bac. 10.3 Navrhněte nedeterministický BA pro jazyk všech cj-slov nad abecedou E — {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 — W1W2W3 ■ ■ ■ I Wi G {a, b} pro i > 1, 3 nekonečně mnoho j G N takových, že Wj — Wj+4} 10.5 Nechť E — {0,1, Pro slovo w — a^aia? ... G E" a dvě čísla i, j1 G N, 0 < i < j označme w[i, j] podslovo en .. .a,j. 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 Ai,A2 velikosti 0(n) takové, aby Ln — L(A{) n L(A2). 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 koncovým stavem c) dokažte, že pro daný jazyk nelze sestrojit NBA s jedním koncovým stavem 10.8 Konstruujte NBA pro následující jazyky L nad abecedou {a, b, c, d}. a) L — {w ínf(w) = {a}} b) L = {w ín/(w) = {a, 6}} c) L = {w a G ínf(w)} d) L = {w a G ínf(w) A c ^ ínf(w)} e) L = {w {a, 6} C ínf(w) A d ^ ínf(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 LU(A) množinu cj-slov, kterou akceptuje Bůchiho automat A. Najděte automat A tak, aby platilo a) (L(A)r = LU(A) b) (L(A)r ŕ LU(A) 10.10 Pro jazyk L — {w G {a, 6}" | inf(w) — {a, b}} navrhněte deterministický Mullerův automat, deterministický zobecněný Bůchiho automat a deterministický Bůchiho automat. 23 Logika MSO 11.1 Definujte základní syntax logiky MSO. 11.2 Buď E abeceda a w G E* konečné slovo, buď (p sentence (formule bez volných proměnných) logiky MSO. Definujte, kdy w \= ip. 11.3 Definujte následující syntaktické zkratky: • x y, x = y • Vx G X : (p • 3x G X : (p • first{x) — x je první pozice v neprázdném slově. • last{x) — x je poslední pozice v neprázdném slově. • 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) =4> (x G X ^> y X)) A A Vx : (x G X => (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? 24 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 0fc a uveďte, že FIRSTk(ABC) = FIRSTk(A) ®k FIRSTk(B) ®k 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 25 — 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. 26 • 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, &}" | w má nekonečně mnoho a} vysvětlete princip Bůchi automatů. • Příklad 10.1 • Příklad 10.2 • Příklad 10.3 • Příklad 10.6 • 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 a 27 Řešení některých příkladů 1.2 Výpočet FI2(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 F/2(C) U {d} f/2 (C) = FJ2(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 {«} {cic, a} {cic, ac, a} {cic, ac, a} {cic, ac, a} {cic, ac, a} B 0 {d} {a, d} {cic, a, ci} {dc, ac, a, d} {cic, ac, a, ci} {dc, ac, a, d} C 0 {d} {d} {a, ci} {cic, a, ci} {cic, 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 {«} {ac, cic, a} {ac, cic, a} B 0 {a, d} {ac, cic, a, ci} {ac, cic, a, ci} C 0 {a, d} {ac, cic, a, ci} {ac, cic, a, d} FI2(Ä) — {ac, dc, a} FI%(Aé) — {ae, cice, ace, cice, acc} 1.3 FJ2(A) = {6,6a}, FJ3(A) = {6, ba, baa} 1.4 FIi(BBb) = {a, 6} FI2(BBb) — {ad, aa, ab, b} FOM) = {c} FOi(S') = FOi(B) = FOi(C) = {e,ci,e} F03(A) = {ccie, cec, c} FOz(S) — FOs(C) — {ecd, ece, ciec, ec, e} Fh(SAcB) = {a, 6, c} FIi(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, bdec, bec, beca, c, ca, cad} 1.5 FOi(S) = FOi(D) = {s, ci, c, a, y} FOi(A) = {a, c, ci, x} FOi(B) = {e, a, 6, c, ci,y} FOi(C) = {e, a, 6, c, ci, y, z} F02(S) — {e, cia, cici, dx, dc, cb, ca, cd, cy, cc, c, aa, ab, ad, ac, ya, yb, yc, yd, yy, yz, y} 1.6 Pozor, gramatika není normovaná, a tudíž generuje prázdný jazyk. 28 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) 02 F02(A): 1 5- > aAaA F/2(aAaA) 02 r102(S') — {aa, ac} 2 5- > aBaB FI2(aBaB) 02 F02(S') = {a6} 3 A- ■> aA r72(aA) 02 ^02 (A) = {aa, ac} 4 A- ■> c r72(c) 02 F02(A) = {ca,c} 5 B - -> 61? FI2(bD) 02 F02(S) = {66, 6a, 6} 6 D - -> 61? FI2{bD) 02 F02(C) — {66, 6a, 6} 7 D - -> e r72(e) 02 F02(D) — {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 6 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 6D,5 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 6 c e 5 aAaA, 1 aBaB, 2 aAaA, 1 A aA, 3 aA, 3 c,4 c, 4 B 6Z?,5 6Z?,5 61?, 5 D e,7 6Z?,6 6Z?,6 61?, 6 e, 7 Analýza slova acaac: (acaac, S%, e) |— (acaac, aAaA%, 1) |-^- (caac, AaA%, 1) |— h (caac, caA$, 14) (aac, aA$, 14) |-^ (ac,A$, 14) |- |- (ac,aA%, 143) |-^ (c,A$,143) |- (c, c$, 1434) |-^- (e, $,1434) =>• akceptuje Analýza slova abaac: (abaac, S%,e) |— (abaac,aBaB%,2) (baac, BaB%,2) |— |— (baac, bDa,B%, 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 6 5 baAa, 1 baBb, 2 A aA, 3 aA, 3 aB, 4 aB,4 aB, 4 B 6,4,5 bA,b e, 6 e, 6 29 3.6 Nejprve zkonstruujeme pomocné LL(3) tabulky: T0 = (S,{e}) S- ■> aAaB aaa, a6a {aa,aaa},{e} S- > bAbB bab, bba {ba, baa}, {e} Ti — (A, {aa,aaa}) A- ■> a aaa, — A- ■> ba baa — T2 B - -> aB aa, aaa, {e} B - -> a a — T3 — (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 vstupuje 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 a,Ti a,T2,1 a,Ti a,T2,1 bT3bT2,2 bT3bT2,2 Ti a, 3 ba, 4 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(Í) gramatika je například ({£}, {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): 30 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 - -> a.Ab e A 4 A - -> .bS b b 5 A - .Bc b 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 b S 11 S - -> .aAb b a 12 S - -> .c b c 13 S - -> .cB b c 13 6 A - B.c b 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 1 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 b b 5 A - .Bc b 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 4 S - -> 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) 5 a) 3x : (Qa(x) A Q b (x)) b) Vx : —tfirst{x) c) Vx : (first(x) A Qa(x)) A 3y : first (y) d) Vx : Qa(x) e) Vx : Qa(x) A 3y : Qa(y) f) 3x : (Qb(x) A last(x) A Vz : (z < x Qa(z))) g) 3X : (Vx : (first(x) => x g X) A A Vx g X : 3y, z ^ X : (succ(x, y) A succ(y, z) A (last(z) V 3w £ X : succ(z, v)))) 6 a) {a, 6}.{a}.{a, 6}*, tj. na druhé pozici je a; b) {w g S* | w má na každé sudé pozici písmeno a} 31