Toegangseisen
Aanbevolen voorkennis: Foundations of Computer Science
Beschrijving
De theorie van Automaten, Formele Talen en Berekenbaarheid vormt een van de hoekstenen van de Theoretische Informatica, omdat ze ons in staat stelt om precies te kunnen spreken over wat een berekening is, of de complexiteit van een algoritme, of wanneer een probleem op te lossen is. Een automaat is een wiskundig model om (formele) talen vast te leggen. Formele talen op hun beurt kunnen bijvoorbeeld berekeningen, programmeertalen of complexe systemen beschrijven.
Het eenvoudigste type automaat is de eindige automaat, een machine die alleen een toestand bij kan houden, maar verder geen geheugen heeft. Een eindige automaat legt een algoritme vast om te bepalen of een string tot een taal behoort. Talen die geaccepteerd worden door eindige automaten, heten reguliere talen. Reguliere talen kunnen gegenereerd worden door reguliere grammatica's en beschreven worden door reguliere expressies. We behandelen algoritmes om het ene formalisme om te zetten in het andere.
Wanneer we een beperkte vorm van extern geheugen aan de eindige automaat toevoegen, in de vorm van een stapel, ontstaat de stapelautomaat, een krachtiger concept. Stapelautomaten accepteren context-vrije talen. Deze worden gegenereerd door context-vrije grammatica's, die ook een cruciale rol spelen in de definitie van programmeertalen. Stapelautomaten op hun beurt zijn belangrijk in het ontwerp van compilers.
De derde klasse van talen die we bestuderen, zijn de recursief opsombare talen. Die kunnen geaccepteerd worden door Turingmachines. Turingmachines vormen het meest algemene model van berekenbaarheid. Ze maken gebruik van een tape, voor invoer en uitvoer en als werkgeheugen. Ze zijn in staat om alle soorten algoritmes uit te voeren.
Als een beslissingsprobleem niet door een Turingmachine kan worden opgelost, heet dat probleem onbeslisbaar. We behandelen diverse concrete onbeslisbare problemen, en gebruiken reducties om de onbeslisbaarheid van het ene probleem af te leiden uit die van het andere probleem.
Voor de reguliere talen en de context-vrije talen bespreken we pomplemma's, die laten zien dat bepaalde talen juist niet door een automaat kunnen worden herkend. We vergelijken voor alle types automaten en machines de deterministische en niet-deterministische varianten. Verder verkennen we algoritmes die van beschrijvingen van eenvoudige talen meer complexe talen maken, de zogenaamde afsluitingseigenschappen.
Leerdoelen
Na afloop van dit vak zijn studenten in staat om:
een eindige automaat voor een gegeven taal te ontwerpen en eindige automaten te interpreteren
een reguliere expressie voor een gegeven taal te ontwerpen en reguliere expressies te interpreteren
een context-vrije grammatica voor een gegeven taal te ontwerpen en context-vrije grammatica's te interpreteren
een stapelautomaat voor een gegeven taal te ontwerpen en stapelautomaten te interpreteren
een Turingmachine voor een gegeven taal of functie te ontwerpen en Turingmachines te interpreteren
de (on)beslisbaarheid van problemen aan te tonen en reducties toe te passen
definities te reproduceren en toe te passen van, o.a., bovenstaande concepten
constructies te beschrijven en toe te passen, o.a. . tussen eindige automaten en reguliere expressies . tussen eindige automaten en reguliere grammatica's . tussen context-vrije grammatica's en stapelautomaten
eenvoudige eigenschappen te bewijzen en toe te passen, zoals afsluitingseigenschappen en pomplemma's
Rooster
Het meest recente rooster is te vinden op de Studenten-website:
In MyTimetable kun je alle vak- en opleidingsroosters vinden, waarmee jij je persoonlijke rooster kunt samenstellen. Onderwijsactiviteiten waarvoor je je via MyStudyMap hebt ingeschreven, worden automatisch in je rooster getoond.
Daarnaast kun je My Timetable gemakkelijk koppelen aan een agenda-app op je telefoon en worden roosterwijzigingen automatisch in je agenda doorgevoerd; bovendien ontvang je desgewenst per e-mail een notificatie van de wijziging. Je kunt notificaties aanzetten bij Instellingen, nadat je bent ingelogd.
Vragen? Bekijk de video, lees de instructie of neem contact op met de ISSC helpdesk.
Let op: Joint Degree studenten Leiden/Delft dienen de informatie uit de Leidse en Delftse MyTimetables samen te voegen om een volledig rooster te zien. Deze video legt uit hoe dat werkt.
Onderwijsvorm
Elke week twee uur hoorcollege en twee uur werkcollege. Daarnaast worden vier huiswerkopgaven opgegeven.
Toetsing en weging
Vier huiswerkopgaven in de loop van het semester en een schriftelijk tentamen aan het eind van het semester. Het minimumcijfer voor de huiswerkopgaven is 0, het minimumcijfer voor het tentamen is 1. De huiswerkopgaven zijn niet verplicht, en kennen dan ook geen herkansing. Ze tellen wel mee voor het eindcijfer. Het tentamencijfer dient minstens 5.5 te zijn. In dat geval wordt het eindcijfer berekend als een gewogen gemiddelde van het tentamencijfer (70%) en het gemiddelde van de huiswerkopgaven (30%). Als dit gewogen gemiddelde lager is dan 5.5, is het eindcijfer toch een 6. Als het tentamencijfer lager is dan 5.5, is het eindcijfer gelijk aan het (onvoldoende) tentamencijfer. Deelcijfers voor huiswerk en/of tentamen van vergelijkbare vakken in eerdere jaren kunnen niet worden meegenomen naar het nieuwe jaar.
Literatuurlijst
John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw Hill, 2011
Inschrijven
Als student ben je zelf verantwoordelijk voor het tijdig inschrijven via MyStudyMap.
In deze korte video zie je stap voor stap hoe je je kunt inschrijven voor cursussen in MyStudyMap.
Uitgebreide informatie over de werking van MyStudyMap vind je hier.
Er zijn twee inschrijfperiodes per jaar:
de inschrijving voor het najaar opent in juli
de inschrijving voor het voorjaar opent in december
Zie deze pagina voor meer informatie over deadlines en inschrijven voor vakken en tentamens.
Let op:
Het is verplicht om je in te schrijven voor alle activiteiten die je gaat volgen van een vak.
Je inschrijving is pas voltooid wanneer je je cursusplanning indient in het tabblad ‘Klaar voor inschrijving’ door op ‘indienen’ te klikken.
Niet ingeschreven zijn voor een (her)tentamen betekent dat je niet mag deelnemen aan het (her)tentamen.
Contact
Onderwijscoördinator LIACS bachelors
Website
https://liacs.leidenuniv.nl/~vlietrvan1/ftb/
Opmerkingen
Dit vak vervangt in overgangsjaar 2025-2026 de oude vakken Automata Theory (6ECTS) en Computability (3ECTS). Met ingang van het studiejaar 2026-2027 zal dit vak aansluiten op het nieuwe eerstejaarsvak Automaten (3ECTS), waardoor de inhoud weer wat zal verschuiven. In studiejaar 2025-2026 worden bezemtentamens georganiseerd voor de vakken Automata Theory en Computability. Studenten die een van deze oude vakken hebben gehaald, wordt verzocht contact op te nemen met de studieadviseur alvorens een van de nieuwe vakken te volgen.
Voor meer informatie over Brightspace kun je op deze link klikken om de handleidingen van de universiteit te bekijken. Bij overige vragen of problemen kan contact opgenomen worden met de helpdesk van de universiteit Leiden.