Toegangseisen
Aanbevolen voorkennis: Foundations of Computer Science.
Beschrijving
De theorie van Automaten en Formele Talen 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.
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 is de eindige automaat, een machine die alleen een toestand bij kan houden, maar verder geen geheugen heeft. We leren dat er twee essentieel verschillende types eindige automaten bestaan. De deterministische eindige automaat legt een algoritme vast dat voor een string bepaalt of deze tot de taal behoort. De niet-deterministische automaat op haar beurt is beschrijvend van aard.
We bestuderen de twee types automaten, en de structuur van de talen die ze kunnen accepteren. Ook bekijken we welke talen juist niet door een automaat kunnen worden herkend. Verder verkennen we algoritmes die van beschrijvingen van eenvoudige talen meer complexe talen maken, de zogenaamde afsluitingseigenschappen.
Leerdoelen
Na het volgen van dit vak kan de student:
Eindige automaten en reguliere expressies opstellen aan de hand van een gegeven reguliere taal
Algoritmes toepassen om eindige automaten of reguliere expressies om te zetten of te vereenvoudigen
Aantonen of een gegeven taal regulier is, met behulp van een pomplemma of de stelling van Myhill-Nerode
Eenvoudige eigenschappen van reguliere talen en eindige automaten bewijzen
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
Per week twee uur hoorcollege en twee uur werkcollege.
Toetsing en weging
2 huiswerkopdrachten (10%)
Schriftelijk tentamen (90%)
Het gemiddeld huiswerkcijfer telt alleen mee als dat voordelig is voor het eindcijfer.
Om het vak te halen, dient er minstens een 5.0 behaald te zijn voor het tentamen.
Het tentamen kent een schriftelijke herkansing, waarbij het huiswerk nog steeds alleen meetelt als dat voordelig is voor het eindcijfer.
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
Opmerkingen
Dit vak en het vak Talen en berekenbaarheid (6ECTS) in het tweede jaar vervangen samen de oude vakken Automata Theory (6ECTS) en Computability (3ECTS). In het studiejaar 2025-2026 worden bezemtentamens georganiseerd voor de vakken oude stijl. Studenten die een van de vakken in de oude stijl hebben gehaald, worden verzocht contact op te nemen met de studieadviseur alvorens een van de vakken nieuwe stijl 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.