Behandelde stof bij de hoor- en werkcolleges Automata Theory, najaar 2020 ============================================ Hoorcollege 1, dinsdag 1 september 2020: * Paragraaf 1.4, Hfst 2 t/m blz 52 Werkcollege 1, dinsdag 1 september 2020: * Opgaven 1.36, 1.37(a), 2.1(afgg2j), 2.2(d) Hoorcollege 2, dinsdag 8 september 2020: * Paragraaf 2.1 afgemaakt * Paragraaf 2.2 * Paragraaf 2.4 t/m Voorbeeld 2.32 Werkcollege 2, dinsdag 8 september 2020: * Opgaven 2.10, 2.22(abdh), 2.24, 2.26 Hoorcollege 3, dinsdag 15 september 2020: * Paragraaf 2.4 afgemaakt * Paragraaf 2.3 Werkcollege 3, dinsdag 15 september 2020: * Opgaven 2.27(d), 2.13, 2.17, 2.15, 2.21(abdh) Hoorcollege 4, dinsdag 22 september 2020: * Paragraaf 2.5 (details van bewijs Stelling 2.36 niet behandeld, dus geen tentamenstof) * Paragraaf 2.6 Werkcollege 4, dinsdag 22 september 2020: * Opgaven 2.33, 2.36, 2.37, 2.55(c) Hoorcollege 5, dinsdag 29 september 2020: * Paragraaf 3.2 * Paragraaf 3.3, waarbij - inductiebewijzen van Stelling 3.17 en Stelling 3.18 niet behandeld zijn, en ook geen tentamenstof zijn - iets andere constructie dan in het bewijs van Stelling 3.17 behandeld is, voor het elimineren van Lambda-transities. Leer deze, iets andere constructie in plaats van de constructie uit het boek - en leer ook wel de constructie uit Stelling 3.18 Werkcollege 5, dinsdag 29 september 2020: * Opgaven 3.21, 3.22(ef), 3.37(b), 3.40(a) * Extra opgave over `omkering' constructie om Lambda-transities te elimineren Hoorcollege 6, dinsdag 6 oktober 2020: * Paragrafen 3.1, 3.4 * Paragraaf 3.5, waarbij we een iets andere notatie gebruiken dan in het boek: L^k(i,j) en r^k(i,j) ipv L(i,j,k) en r(i,j,k) * Brzozowski & McCluskey (opgave 3.54) * homomorfisme (opgave 3.53) Werkcollege 6, dinsdag 6 oktober 2020: * Opgaven 3.7(cegjkm), 3.1(a), 3.2(ab), 3.10, 3.41(e), 3.42, 3.51(a, maar dan met Brzozowski & McCluskey) Hoorcollege 7, dinsdag 13 oktober 2020: * Paragrafen 4.1 en 4.2 * Intro paragraaf 4.3 Werkcollege 7, dinsdag 13 oktober 2020: * Opgaven 4.10(acdef), 4.1(bcefg), 4.3(bc), 4.4, 4.9 Hoorcollege 8, dinsdag 27 oktober 2020: * Paragraaf 4.3 * Paragraaf 4.4 t/m blz 146 * Opgave 4.45(b) (met inductie) Werkcollege 8, dinsdag 27 oktober 2020: * Opgaven 4.26(a), 4.27, 4.22, 4.28, 4.29(b), 4.36(bef), 4.38(bcd) Hoorcollege 9, dinsdag 3 november 2020: * Paragraaf 4.5 * Opgaven 4.51, 4.52, 4.53 * operations on languages / attribute grammars (allebei geen tentamenstof) * Hoofdstuk 5 tot bovenaan blz 166 * Voorbeeld 5.3: AnBn Werkcollege 9, dinsdag 3 november 2020: * Opgaven 4.53(c_ii), 4.50(a) ChNF, 4.54(a), 4.48 * Extra opgave: PDA voor {a^i b^j c^k | 2i>j} Hoorcollege 10, dinsdag 10 november 2020: * Paragraaf 5.1 afgemaakt * Paragraaf 5.2 * Paragraaf 5.3 t/m blz 177 * Opgave 5.20 Werkcollege 10, dinsdag 10 november 2020: * Opgaven 5.4, 5.5(ab), 5.6(a), 5.18(c) * Extra opgave: DPDA voor {a^i b^j c^k | 2i>j} * Opgaven 5.2, 5.10, 5.12 genoemd Hoorcollege 11, dinsdag 17 november 2020: * Paragraaf 5.3 afgemaakt Bewijs van `L(NT(G)) \subseteq L(G)' bij Stelling 5.18 niet behandeld en is ook geen tentamenstof Bewijs van Stelling 5.23 niet behandeld en is ook geen tentamenstof. * Paragraaf 5.4 t/m Stelling 5.29 Bewijs van Stelling 5.29 niet behandeld en is ook geen tentamenstof * Ook als bewijzen niet (helemaal) behandeld zijn, behoren de constructies zelf en het intuitieve idee daarachter wel tot de tentamenstof. Werkcollege 11, dinsdag 17 november 2020: * Opgaven 5.28(b), 5.34(a), 5.21, 5.19 Hoorcollege 12, dinsdag 24 november 2020: * Paragraaf 5.4 afgemaakt * Paragraaf 5.5 t/m blz 194 * Paragraaf 6.1 t/m formulering Stelling 6.1 * Voorbeeld 6.3 Werkcollege 12, dinsdag 24 november 2020: * Opgaven 5.32, 5.38(a), 5.39, 5.40 * Extra opgave genoemd over generalisatie van Opgave 5.39 * Opgave 5.41 genoemd Hoorcollege 13, dinsdag 1 december 2020: * Paragraaf 6.1 t/m Voorbeeld 6.6 * Paragraaf 6.2. De constructie van Stelling 6.13 behoort wel tot de tentamenstof, het inductiebewijs vervolgens niet. * Paragraaf 6.3 Werkcollege 13, dinsdag 1 december 2020: * Opgaven 6.2(b), 6.5(ad), 6.12, 6.13, 6.8