Faculty of Informatics Masaryk University Brno Cvičení k předmětu IA006 Vybrané kapitoly z teorie automatů poslední modifikace 4. listopadu 2015 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 a A, A -> bbAb | e } Operace k:w a L\ (Bk L2 Nechť k € N je přirozené číslo, w je slovo a L\,Ľ2 jsou jazyky. Operace k:w a L\ (Bk L 2 definujeme následovně: f w pokud \w\ < k I u, kde \u\ = k a w = u.v pro nějaké v pokud \w\ > k L\ (Bk L-2 = {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\ (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 e N jsou funkce FIRSTf a FOLLOWf definovány následovně: FIRSTfr : (Ľ U -/V)* —> 2E* FIRST f (a) = {k:w\a^*w, w G £*} FOLLOWf : N —> 2E* FOLLOW^(A) = {w I 5 =>* ^Aa, w e FIRST^(a) ; 7,« e (E U TV)*} Pozor na typ argumentu u jednotlivých funkcí. Argumentem funkce FIRST % (a) je řetězec terminálů a neterminálů (a 6 (E U N)*), na rozdíl od funkce FOLLOW^ (A), jejíž argumentem je vždy právě jeden neterminál (A € N). Definice funkcí FIRST^ a FOLLOW^ lze přirozeně rozšířit také na množiny odpovídajících argumentů, což je užitečné zejména pro funkci FIRST^ . FIRST f : 2(EUAr)* —>• 2E* FOLLOWf : 2N —> 2E* FIRSTC*(M) = U«eM FIRSTc*(a) FOLLOW^M) = UAeM FOLLOWf (A) Dále budeme používat zkrácené zápisy funkcí, Flk(a) pro FIRST f (a) a FOfc(A) pro FOLLOWf(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, E, P, S) a řetězec a = YXY2 ... Y, kde každé Y e N U E U {e}. 1) FJfc(aO = {a;} pro FJ*(e) = {e} 2) Výpočet FIk(x) pro x e N: Nechť TV = {Xi, X'2, • • •, Xn}. Budeme počítat hodnotu FIk(Xi) současně pro všechny neterminály (i = 1,..., n). Nejprve sestavíme pro každý neterminál Xt příslušnou rovnici. Nechť všechna pravidla pro neterminál Xt jsou tato: Xt^Yl...Y^ \ YÍ2...Yk22 ... | Y(... YÍ. Potom FIk(Xi) = {FIk{Yl) ®k FIk{YJ) ®k ... ffifc FIk(Yk\)) U U (FIk(Y;2) (Bk Fh{Y2)®k ... ffifc FIk{Yk\)) U U {FIk{YD ®k FIk(XÍ)@k ... ffifc FIk k a L2 ^ 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) ffi3 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 FF2(A) a FI3(Ae) pro gramatiku G = ({A, B, C, D},{c, a, d, e},P, A), kde P = { A —> Bc I a, B ->• A I C I d, C B d, D -> e } 1.3 Podle algoritmu řešte P/2(^4) a P/3 (A) pro gramatiku G= ({A},{a, b},P, A), kde P = { A -> Aa, A -> 6 } 1.4 VypočítejteFI\(BBb), FI2(BBb), FOi{Ä), FOi(S), FOi(B), POi(C), PC3(A), F03(S), F03(C), FIi(SAcB), FIi(SAcB) pro následující gramatiku: G = ({S, A, B, C},{a, c, b, e, d},P, 5), kde P = { S - ■> aAc S, A - ■» aA 6SGe B - ■> aG C - e } 1.5 Podle algoritmu řešte FOk{X), kde fc = 1,2, 3,4 a X e {5, A, P, G, Ľ} pro následující gramatiku: G = ({S, A, B, G, P},{a, b, d, c, z, y, z},P, 5), kde {5 - ■> aABbCD A - -}• ASd B - SAc xC C - + 5y Cz D - -» aBP e} 1.6 Vypočítejte POfc(X), kde fe = l,2,3,4aX e {5, ,4, P, G, P} pro následující gramatiku: G = ({5, B, A, D, G},{a, c, Ď, d},P, S), kde {5 -A - -> cíBcB, ,4a. B - -» PAc 6,4, C - -» cBc aaB, D - -» d dG } 1.7 Zamyslete se, v jakých případech platí následující vztahy: a) FIk(Ä) = V) 0 FOk(A) = 0 b) e e FIk(A) g) e G POfc(A) c) FIk {A) C FIk+1(A) h) POfc(,4) C FOk+1(A) d) FIk+1(A) C F/fc(A) i) FOk+1(A) C FOk(A) e) FIk(a-FOk(X)) = FIk(a )®fc POfc(X) j) FOk(A) C POfc(P) k) {Li ®fe L2) ffifc P3 = £1 ®fc (L2 ®k 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 A € -/V a pro každá dvě různá pravidla A —> /3, A —> 7 platí: FIk(l3)®kFOk(A) n FIk{~f)®kFOk{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 bYa, Y a j e } 2.2 Ověřte, zda gramatika je SLL('í): G = ({S, A, B},{a, b},P, S), kde P = { S -> aAaB \ bAbB, A —> a \ ob, 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 {S - -» aAaA, s - -» aBaB A - -» aA, A - -> c, B - -» 6L>, D - -» 6L>, D - 2.4 Navrhněte SLL('í) analyzátor pro gramatiku a analyzujte slovo bababab. G = ({S, A, B},{b, a},P, S), kde P = { S -> baAa, S -> 6aB6, A aB, B 6A, £> —> e } 4 LL(k) gramatiky a analyzátory Gramatika je LL(k) , právě když pro dvě libovolná různá pravidla gramatiky A —> /3,A —> 7 a pro všechny nejlevější větné formy tvaru wAa platí: FIkifi ■ a) n FIjďy ■ a) = 0 Gramatika je LL(1) právě když je SLL(l). Je-li gramatika G SLL(k), pak je také LL(k). 3.1 Ověřte, zdaje následující gramatika LL(2): G = ({S, X, Y},{b, a},P, S), kde P = { S —> X, X Y bYa, Y a j e } 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 \ ob, B aB a } 3.3 Ukažte, že gramatika není L L (k) pro žádné fc: G = ({S, A, B},{a, b, 0,5), kde P = { S -> A j B, A aA6 I 0, B aB66 j 1 } 3.4 Ukažte, že gramatika je L L (k): G = ({S, T, A, B}, {a, b, c}, P, S), kde P={S -> aT T -> j A A^rbB I c B —> 6fc_1d j e 3.5 Zkonstruujte LL(2) analyzátor pro gramatiku G: G= ({5,A},{a,6},P,5), kde P= { S -> e, 5 -> a6A, A 6 } 3.6 Zkonstruujte LL(3) analyzátor pro gramatiku G: G = ({5, A, B},{a, b},P, S), kde P = { S -> aAaB, 5 -> 6A6B, A a, A 6a, B aB, B 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 | *cř {IDLIST) 3.8 Navrhněte gramatiku, která je LL{2) a není SLL{2). 3.9 Navrhněte gramatiku, která a) je 5LL(3) a není LL(2) b) je SLL{2) a není LL(3) c) je LL{2) a není SLL{3) ď) 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(l). • Pro gramatiky, které jsou SLL(l), se snadno konstruuje analyzátor. Platí: • Pro danou bezkontextovou gramatiku G je nerozliodnutelné, zdaje 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 nerozliodnutelné 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é LL(1) 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 j SBa \ 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 —> ai I «2 I ... am. Nechť G\ = {N',T,,P',S) je gramatika, která vznikla z G vyloučením pravidla A —> Ba a přidáním pravidel A —> ol\ol \ 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(1) a nemá e-pravidla, udělat jednoduchou LL(1) 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 -t ab I Ba, B c 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 -t aA | e, B b A | e } Levá faktorizace Pro LL(1) gramatiku musí platit: A a, A /3 => FIRSTi(a) íl FIRST^P) = 0 nesplnění této podmínky se označuje jako konflikt FIRST-FIRST. Kolizi může způsobit přítomnost pravidel tvaru A —> olol\ \ aa2 | • • • | oian, kde a ^ e. Kolizi odstraníme jestliže uvedená pravidla nahradíme pravidly tvaru A —> a A1, A1 —> «i | «2 | ... | an. 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 \ bbadC \ cBC, C -> aA 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, C -í- 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 -t cA | a, B -> cB | 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 6B, B ^ cB 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 | bc, 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 -t aAb I e, B aBc I e } Pohlcení terminálního symbolu Pro LL(1) gramatiku musí platit: A a, A e => FIRSTx (a) íl FOLLOW! (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 —> aAa/3 a přitom A—pravidla jsou tyto: A —> 71 | ... | jn. Konflikt se můžeme pokusit odstranit tak, že pravidlo X —> aAa/3 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 —> e I aaC, C -> c j 6(7 } 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 ^ aB 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 —> aAY/3 a Y/3 =>+ 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 -t aAB b I bbc \ e, 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 aC B - ■» bB CdC, C - ■» cC d } 4.15 Transformujte na LL(1) následující gramatiku: G = ({E, T, F, S},{o, n, a, (, )},P, E), kde P = { E EoT j T, T ToF j F, F nS* j 5, 5 -> a (B) } 9 4.16 Ověřte, zda je následující gramatika LL(1) gramatika. Pokud není, použijte standardní transformace na úpravu gramatiky na LL(l) a o výsledné gramatice dokažte, že je LL(1) gramatikou. G=({S,A},{b,c,a},P,S), kde P = { S —> bcAa | bb, A -¥ e | acAb } 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 -t a | aA, B ^ bA | 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(1) a SLR(2) analyzátor 11 G = ({S, A, B},{a, b},P, S), kde P = { S -> AB, A -t aAb, A -»• e, B 6P, B 6 } 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 -> PF, P Ra, P 6Pc, P dc, P 6da, R -t d } 5.6 Dokažte, že gramatika z príkladu 5.5 není SLR(k) pro žádné fc. 5.7 Rozhodněte, zda následující gramatika je SLR(k) G = ({X, S, L, R},{=, i, d, *},P, X), kde P = { X -> S, S -> L = P, 5 -> P, L —> id, L *P, P —> L } 5.8 Zkonstruujte SLR(l) 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?(0) a SLR(k) gramatiky 5.9 Zkonstruujte LP(0) gramatiky Li = {1™ a 0™ | n > 0} U {1™ 6 O2™ | n > 0} L2 = {a 1™ 0™ | n > 0} U {6 1™ O2™ | n > 0} L3 = {1™ 01™ | m > n > 0} L4 = {w#wR w e {0,1}*} 5.10 Dokažte, že následující gramatika není LP(0) aleje SLR(1) G = ({X, S, A},{+, (,), a},P, X), kde P = { X S, S S + A, S ^ A, A -í- (5), A a(5), A a } 5.11 Nalezněte co možná nejjednoduší gramatiku takovou, že 12 a) není LR(O). b) není SLR(l) protože má konflikt čtení-redukce. c) není SLR(l) protože má konflikt redukce-redukce. 5.12 Ověřte, zdaje následující gramatika SLR(1) či SLR(2) gramatika. G = ({X, S, B},{a, b},P, X), kde P = { X S, S -> aB, S -> a, B 656 } 13 LR(k) a LALR(k) analyzátory 6.1 Rozhodněte, zdaje gramatika LR(0), SLR(1), LALR(1), LR(1) G = ({X, S, A, B},{a, d, Ď, e, c},P, X), kde P = { X -> S, S -> aAd, S -> bBd, S -> aBe, S -> 6Ae, A -> c, B —> c } 6.2 Rozhodněte, zdaje gramatika LR(0), SLR(1), LALR(1), LR(l) G = ({X, S, A, B, C, D, E},{a, b},P, X), kde {X - -» S, s - -» AB, A - -> a, B - -» CD, B - -» a£, C - -> a6, D - -» 66, E - + ĎĎŕl } 6.3 Zkonstruujte LALR(l) analyzátor G = ({X, S, A, B},{a, b, c},P, X), kde P = { X S, S -> aAĎ, S -> c, 5 -> cB, A 65, A Bc, B —> c } 6.4 Zkonstruujte iniciální stav LR(2) automatu G= ({S,R},{+,a},P,S), kde P = { S -> i?, —>■ iľiľ, i? -> iž + iž, i? a } 6.5 Proveďte LR(1) analýzu G = ({X, S, A},{a, b},P, X), kde P = { X 5, 5 -> 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 -> AB, A -> 0A1, A e, B -> 1B, B 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) P'2 má stav / takový, že / ~ 1 (ii) P'2 je konečně stavový Jaká je maximální bisimulace pro P\l 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 ^„ 4, ale 3 4. Najděte maximální bisimulaci. Faktorizujte podle relace bisimulace. 7.7 Najděte nejmenší n, takové aby platilo 3 ^„ 4, ale 3 ~„_i 4. Najděte maximální bisimulaci. Faktorizujte podle relace bisimulace. © a O a O a 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 XAe B A BBB B As 8.3 Jaký jazyk generuje následující BPA (z proměnné X)? X A XA X A XB XAs A As B As 8.4 Nakreslete přechodový systém určený BPP algebrou X A X\B X A X\D B As D As (xAs) 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í: a a Ó 19 Konstrukce tabel pro BPA Tablo pro 7 = 5 se skládá z podtabel. Každé podtablo je strom. Podtablo s kořenem Xa = Y/3 vytvoříme následovně. Nechť k = min{\\X\\, Na uzel Xa = Y/3 aplikujeme fc-krát trojici pravidel (REC, SUM, PREFIX). Po fc-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 = /3 (použijeme pravdilo SUBR), případně a = /3 (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 = p a na cestě od tohoto listu do kořene celého tabla se vyskytuje uzel se stejným označením a = /3 & mezi nimi je alespoň jednou použito pravidlo PREFIX (uzel /3 = a se nepočítá!) Kritéria neúspěšnosti : 1. a.a = b./3 ,kde a je různé od b 2. a = p ,kde \a\ je různá od \P\ Poznámka: 1. Výše uvedená metoda funguje pouze pro NORMOVANE BPA !!! 2. Poznámka o zápisu: XY = X.Y 1. a a Pravidla Xa = Y P Ea = F P REC aa = aP PREFIX a = P 20 _(S£i a*a*)a = (EJ=i bjßj)ß_ {a^a = Ď/(l)/3/(l)/3}^l1{aí,(J)aí,(J)a = b}ß}ßY3=1 kde / : {1,..., m} —> {1,..., n} g : {1,..., n} —> {1,..., m} m, n > 1 "i7 = ßi aia = ßiß OLi = ßij 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 = ß 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^C 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 21 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 E = {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 E = {a, b, c}, která obsahují nekonečný počet symbolů b a c. 10.3 Navrhněte nedeterministický BA pro jazyk všech w-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 ... Wi G {a, b} pro i > 1, 3 nekonečně mnoho j € N takových, že Wj = wJ+4J 10.5 Nechť E = {0,1, #}. Pro slovo w = ŕioŕiiŕig • • • € S" a dvě čísla i, j G N, 0 < i < j označme w[i, j] podslovo cii... cij. Pro pevně zvolené n € N definujme jazyk: Ln ={w w G ((0 + a pro nekonečně mnoho i > 0 platí: w[2m, (2i + l)n - 1] ± w[(2i + l)n, (2i + 2)n - 1]}. Popište dva nedeterministické BA Ai,A'2 velikosti O (n) takové, aby Ln = L(Ai) 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 e {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 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 10.9 Buď A konečný automat. Označme L (A) množinu slov, kterou akceptuje konečný automat A. Označme LL0(Ä) množinu w-slov, kterou akceptuje Búchiho automat A. Najděte automat A tak, aby platilo a) (L(A))» = L„(A) b) {L{A))« ŕ L„{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 MS O 11.1 Definujte základní syntax logiky MSO. 11.2 Buď E abeceda aw £ E* konečné slovo, buď p sentence (formule bez volných proměnných) log MSO. Definujte, kdy w \= p. 11.3 Definujte následující syntaktické zkratky: a) x < y, x > y, x = y b) \/x e X : p c) 3x G X : p d) first(x) — a; je první pozice v neprázdném slově. e) last(x) — a; 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\/z : (x < z A x < y A (z < y x = z) A Qa(y)) b) 3X : [\/x, y : (succ(x, y) => (x e X y ^ X)) A A Va; : (x e 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 ©fc 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 vič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 vič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 • Prí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. vič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. vičení 6 — Buchi automaty a MSO Logika • Na příkladu {w G {a, 6}" | 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 27 Řešení některých příkladů 1.2 Výpočet FI2(A) provedeme z pedagogických důvodů zcela algoritmicky.Nejprve sestavíme příslušné rovnice: FI2(A) = FI2(B)®2{c} U {a} FI2(B) = FI2(A) U FI2(C) U {d} FI2(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} FI3(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} F01(A) = {c} FOíiS) = FOi{B) = FOi{C) = {e,d,e} FOz(A) = {cde, cec, c} F03(S) = F03(C) = {ecd, ece, dec, ec, e} FIi(SAcB) = {a, b, c} FI4(5AcB) = {aaaa, aaab, aaac, aaba, aabd, aabe, aac, aaca, aacb, aacc, abaa, abab, abac, abad, abae, abde, obec, 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) = {e, a, c, d, y} FOi(A) = {a,b, c, d,x} FOi(B) = {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, y z} 1.6 Pozor, gramatika není normovaná, a tudíž generuje prázdný jazyk. 2.1 Není SLL{2), konflikt nastává na pravidlech Y —> a \ e. 2.2 Není SLL('í), konflikt nastává na pravidlech A —> a \ ab. 2.3 Nejprve pro každé pravidlo tvaru A —> a spočítáme množinu Fl2(a) ©2 F0'2(A): 1 S- > aAciA FF2{aAaA)®2 F02(S) = {aa, ac} 2 s- > aBaB FF2(aBaB) ©2 F02(S) = « 3 A - ■> aA FF2(aA) e2 F02(A) = {aa, ac} 4 A - ■> c FF2(c) e2 F02(A) = {ca, c} 5 B - -» 6D FF2(bD) e2 F02(B) = {66, Ďa, 6} 6 D - -> 6£> FF2{bD) ©2 F02(D) = {bb, ba, b} 7 D - -> e FF2(e) e2 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 6c ca cb cc a 6 c e S A B D aAaA, 1 aA,3 aBaB, 2 s,7 aAaA, 1 aA, 3 6D,5 6D,6 6D,5 6D,6 c,4 6D,5 6D,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, 4 B bD,5 bD,5 bD, 5 D e,7 bD,6 bD,6 bD, 6 e, 7 Analýza slova acaac: (acaac, S$, e) |— (acaac, aAaA%, 1) p- (caac, AaA%, 1) |— |- {caac, caA%, 14) p (aac, aA$, 14) p- (ac,A$, 14) P |- (ac,aA$, 143) p- (c,A$, 143) P (c, c$, 1434) p P (e, $,1434) akceptuje Analýza slova abaac: (abaac,S$,s) P {abaac,aBaB%,2) p- (baac, BaB$,2) P P (6aac, bDaBt, 25) p (aac, £>aB$, 25) zamítá 2.4 Zajímavá část tabulky SLL('í) analyzároru vypadá takto: baa bab aaa aab aba aa ab a b baAa, 1 baBb, 2 a A, 3 a A, 3 aB,4 aB,4 aB,4 6A,5 bA,5 e,6 e, 6 29 3.6 Nejprve zkonstruujeme pomocné LL(3) tabulky: To = (S,{e}) S - » aAaB aaa, aba {aa, aaa}, {e} S- » bAbB bab, bba {ba, baa}, {e} Ti = (A, {aa,aaa}) A - ■> a aaa — A - ■> ba baa — T2 = (B,{e}) B - -» aB aa, aaa {4 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 aTxaT2,1 aTxaT2,1 bT3bT2,2 bT3bT2,2 Ti a, 3 ba, 4 T2 aT2,5 aT2,5 a, 6 Tz a, 3 ba, 4 4.6 Levá faktorizace na tomto příkladu „cyklí". Jazykově ekvivalentní jednoduchá LL(1) 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: 11.1 p 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 b b 5 A — .Bc b B 6 B —>• .c c c 7 3 S —>• c. e,h r(S —►c) S —>• c.B e,h B 8 B —► .c e,h c 7 ::= Qa(a;) \ x < y \ x e x ""ŕ 1 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) 3x p | 3X p, kde a G E je libovolný znak z abecedy, a;, y reprezentují proměnné prvního řádu a X reprezentuje proměnnou druhého řádu. 11.3 a) < x), y < x, ->{x < y V y < x) b) Vi (s; £ X => p), kde Wxip = ->(3x->ip) c) 3x(x e X A p) d) Vy (z < y) e) Vy (y < x) f) (x < y) A -<3z (x < z A z < y) 11.5 a) 3a; b) Va; c) Va; d) Va; e) Va; (Qa(x) A Qb(x)) -•first (x) (first (x) A Qa(x)) A 3y : first (y) Qa(x) Qa(x) A 3y : Qa(y) 31 f) 3x : (Qb(x) A last(x) A Mz : (z < x ==> Qa(z))) g) 3X : (ix : (first(x) => x e X) A A Vi £ X : 3y, z ^ X : (s«cc(a;, y) A succ(y, z) A (last(z) V 3t) g X : succ(z, v)))) 11.6 a) {a, 6}.{a}.{a, 6}*, tj. na druhé pozici je a; b) {w € E* | w má na každé sudé pozici písmeno a}