Inhoud:
Context-vrije talen: grammatica’s en stapelautomaten;determinisme, parsing. de Turingmachine als algemeen model voor berekenbaarkeid: herkennen, beslissen en rekenen met Turingmachines, niet-determinsime, universele Turingmachines, Church-Turing These. Recursief opsombare talen en de Chomsky hierarchie. Het stopprobleem, berekenbaarkeit, (on)beslisbare problemen
Methode
hoorcollege met werkgroep
Examinering
schriftelijk
Doel
Verwerven van inzicht in de mogelijkheden en beperkingen van computers (algoritmes). Kennismaken met fundamentele inzichten die ten grondslag liggen aan de informatica als wetenschappelijke discipline.
Voorkennis
Fundamentele Informatica 1 en 2
Literatuur
John C. Martin, Introduction to Languages and the Theory of Computation, 3rd edition, McGraw Hill, 2003
Website
Materiaal
John C. Martin, Introduction to Languages and the Theory of Computation, 3rd edition, McGraw Hill, 2003