Behandelde stof bij de hoor- en werkcolleges Fundamentele Informatica 3, voorjaar 2020 ============================================ Hoorcollege 1, woensdag 5 februari 2020: * Opzet vak * Herhaling FI2: Hst2-6: - eindige automaten - pomplemma voor reguliere talen, - reguliere expressies / talen, - niet-deterministische eindige automaten - context-vrije grammatica's - reguliere grammatica's - afleidingsbomen - stapelautomaten - deterministische stapelautomaten - pomplemma voor context-vrije talen * Paragraaf 7.1 tot Definitie 7.1 * Extra voorbeeld: FA met meerdere accepterende toestanden * Uit Paragraaf 7.2: Voorbeeld 7.3 en Voorbeeld 7.5 t/m Figuur 7.6 (waar `Figure 7.5' onder staat) Werkcollege 1, donderdag 6 februari 2020: * Opgaven 7.4, 7.5, 7.9 * Opgave 7.6 opgegeven * Extra opgave opgegeven: TM voor AnBnCn * Extra opgave: simuleren DPDA met TM Hoorcollege 2, woensdag 12 februari 2020: * Paragrafen 7.1 en 7.2 afgemaakt * Paragraaf 7.3 * Extra voorbeeld: TM voor f(x)=x/3 * Extra voorbeeld: TM voor { xyx | |x|=|y| } * Extra opgave: TM voor f(x,y)=x mod y (alleen genoemd) Werkcollege 2, donderdag 13 februari 2020: * Opgaven 7.1-7.3, 7.10, 7.12, 7.14, 7.16 * Opgave 7.17abce opgegeven Hoorcollege 3, woensdag 19 februari 2020: * Paragraaf 7.4 * Extra voorbeeld: TM voor f(x)=a^{n_a}(x) * Paragraaf 7.5, behalve - formele definities van delta en configuratie - formele formulering Stelling 7.26 - bewijs van Stelling 7.26 * Extra voorbeeld: 2-tapes TM voor AnBn * Paragraaf 7.7 t/m Voorbeeld 7.30 Werkcollege 3, donderdag 20 februari 2020: * Opgaven 7.13, 7.18-7.20, 7.25, 7.26, 7.28 * Opgave 7.27, 7.29, 7.30 opgegeven Hoorcollege 4, woensdag 26 februari 2020: * formulering Stelling 7.31 (zonder bewijs) * Paragraaf 7.6 * Paragraaf 7.8 t/m Voorbeeld 7.34 * is coderingsfunctie e compleet? * Paragraaf 8.1 * Opgave 8.2 Werkcollege 4, donderdag 27 februari 2020: * Opgaven 7.33-7.35, 8.1, 8.4, 8.8 Hoorcollege 5, woensdag 4 maart 2020: * Paragraaf 8.3 * Extra voorbeeld: unrestricted grammar voor XX * Extra voorbeeld: implementatie constructie van Stelling 8.13 Werkcollege 5, donderdag 5 maart 2020: * Opgaven 8.17, 8.18, 8.19a, 8.21 * Opgave 8.19b-d opgegeven Hoorcollege 6, woensdag 11 maart 2020: * Paragraaf 9.1 * Opgave 9.2 * Bijna heel Paragraaf 9.2 (maar zonder reducties tussen talen) * Paragraaf 9.3 t/m Stelling 9.9(2) Werkcollege 6, donderdag 12 maart 2020: * Opgaven 9.1, 9.5, 9.7-9.9, 9.11 * Opgave 9.12 opgegeven Hoor-/werkcollege 7a, woensdag 27 mei 2020: * Belangrijkste resultaten Paragraaf 8.5 (zonder bewijs) * Paragraaf 9.2 afgemaakt (maar nog steeds zonder reducties tussen talen) * Paragraaf 9.3 vervolgd tot Stelling 9.10 * Opgaven 8.3, 9.10 Hoor-/werkcollege 7b, vrijdag 29 mei 2020: * Paragraaf 9.3 afgemaakt * Opgaven 9.12abejl, 9.23, 9.13a * Opgave 9.13bcd opgegeven