Formele Talen en Berekenbaarheid

najaar 2025

Toren Academiegebouw

Laatste nieuws

(30.10.2025) Huiswerkopgave 1 is nagekeken. De beoordelingen zijn naar alle studenten gestuurd. De cijfers staan in Brightspace.

Formele Talen en Berekenbaarheid (FTB) is een verplicht tweedejaars vak in de bachelor Informatica van de Universiteit Leiden. Het wordt dit jaar voor het eerst gegeven, en zal in dit overgangsjaar een combinatie van onderwerpen uit de `oude' vakken Automata Theory en Computability behandelen.
Mocht je het vak dit jaar niet halen, dan moet je in het voorjaar van 2026 het vak Automaten volgen en in het najaar van 2026 dit vak (Formele Talen en Berekenbaarheid) in zijn definiteve vorm.

Praktische informate

Docent (voor de hoorcolleges): Rudy van Vliet
te vinden op: kamer BM.2.03 van het Gorlaeus
telefoon: 071-527 2876
email: rvvliet(at)liacs(dot)nl
Assistenten (voor de werkcolleges en huiswerkopgaven): Simon van Prooijen, Eef Witteveen en Lucas Zuurmond
Algemeen emailadres assistenten: ...(at)liacs(dot)leidenuniv(dot)nl (wordt nog geregeld)
Onderwijsvorm: per week in principe twee uur hoorcollege en twee uur werkcollege, allemaal on-campus.
Collegetijden: van 3 september t/m 11 december 2025. Alleen het eerste hoorcollege is niet op maandag 1 maar op woensdag 3 september. Zelfde tijd, zelfde zaal. En in de week van 20-24 oktober zijn er helemaal geen colleges FTB.

Er komt geen livestream van de colleges. We bekijken nog of het mogelijk is om de hoorcolleges op te nemen en achteraf (na twee weken) beschikbaar te maken. Je kunt sowieso ook terugkijken naar de hoorcolleges Automata Theory en Computability van vorig jaar. Maar bedenk dat we bij FTB niet aan alle onderwerpen toe kunnen komen.

Studielast

Met het behalen van dit vak verdient u 6 EC. Het niveau van het vak wordt aangeduid als `200'.

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.

Voor globale informatie over het vak in studiejaar 2025-2026 wordt men verwezen naar de algemene webpagina in de studiegids.

Leerdoelen

Na afloop van dit vak zijn studenten in staat om:

Toetsing

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.

Exams

Er zijn twee tentamens gepland, allebei on-campus:
Eerste tentamen: vrijdag 9 januari 2026, 09.00-12.00, in Lecture Hall (schotel) C4/5.
Hertentamen: (onder voorbehoud) donderdag 26 maart 2026, 09.00-12.00, in zalen Gorlaeus BW.0.20 en BW.0.29.
De cijfers van de tentamens zullen gepubliceerd worden in Brightspace. Zorg dus dat je je aanmeldt voor de cursus in Brightspace.

Vragenuur

Indien daar belangstelling voor bestaat, kan er een vragenuur voor het (eerste) tentamen worden ingepland. Daarbij kun je dan de vragen stellen die opgekomen zijn bij het leren voor het tentamen.

Huiswerkopgaven

In de loop van het semester worden vier huiswerkopgaven opgegeven. Samen tellen deze voor 30% van het eindcijfer.
De huiswerkopgaven moeten individueel gemaakt worden. Wanneer blijkt dat studenten teveel hebben samengewerkt voor hun oplossing, zullen de (voor een enkele oplossing) verdiende punten worden gedeeld door het aantal betrokken studenten. In bijzondere gevallen kan ook een melding worden gedaan bij de examencommissie. In dat geval wordt de beoordeling van de opgave voor die studenten opgeschort, in afwachting van een oordeel van de examencommissie.
Oplossingen voor de huiswerkopgaven dienen op of voor de deadline ingeleverd te worden. Vaak zal dit ongeveer twee weken na publicatie van de opgave zijn. Haal je die deadline niet, dan heeft het in principe geen zin meer om je oplossing in te leveren. Dat wil zeggen: je verdient er geen punten meer voor.

Het is niet verplicht om de huiswerkopgaven te maken. Het is echter wel verstandig om dat te doen. Immers: (1) het is een nuttige oefening voor het tentamen, (2) als je een of meer huiswerkopgaven mist, krijg je een 0 voor die opgaven, en dat kan je eindcijfer negatief be-invloeden.

Je kunt je oplossingen voor de huiswerkopgaven in Brightspace inleveren. De cijfers voor de huiswerkopgave zullen ook gepubliceerd worden in Brightspace. Zorg dus dat je je aanmeldt voor de cursus in Brightspace.

Resultaten voor de huiswerkopgaven van vergelijkbare vakken uit een eerder studiejaar zijn dit jaar niet meer geldig.

Als de huiswerkopgaven beschikbaar zijn, zullen ze hieronder gepubliceerd worden. Inmiddels is beschikbaar:

Als je eindige automaten digitaal wil teken, kun je gebruik maken van de Finite State Machine Designer. Mocht de notatie hierbij afwijken van de notatie die wij in het vak gebruiken, maak dat dan expliciet als je je oplossing voor de huiswerkopgave inlevert.

Literatuur

John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw Hill, 2010/2011.


Twee keer de 4e editie: de Amerikaanse editie (ISBN-13: 978-0073191461) en de internationale editie (ISBN-13: 978-007-128942-9)
Er is een lijst met errata bij dit boek beschikbaar. Heeft u zelf (andere) foutjes in het boek ontdekt, meld het dan aan de docent. Dan kunnen die ook in de lijst worden opgenomen.

Dit boek schijnt niet meer in de winkel te liggen. Online kun je misschien nog een tweedehands exemplaar vinden. In een eerder jaar heeft de docent voor het vak Automata Theory een (klein) stukje dictaat geschreven, onder andere over het pomplemma voor reguliere talen.

Tentamenstof

De tentamenstof is in grote lijnen Een compleet, gedetailleerd overzicht van de tentamenstof, komt na het laatste college op deze site.

N.B: Vaak bestaan er verschillende constructies om hetzelfde doel te bereiken. Het internet staat er vol mee. Voor de huiswerkopgaven en het tentamen is het van belang om de constructies te gebruiken die we bij dit vak hebben behandeld. Anders kunnen punten worden afgetrokken.

Opmerkingen: Begrippen, notaties en technieken behandeld bij het vak Foundations of Computer Science, in het bijzonder inductie, worden bekend verondersteld. Je moet in staat zijn ze ook bij dit vak te gebruiken.

Behandelde stof, opgaven en slides

Voor wie door omstandigheden een hoorcollege of werkcollege moet missen, houden we per week bij welke stof en opgaven we hebben behandeld. U vindt dit overzicht hier (bijgewerkt t/m hoorcollege van 3 november 2025).

De slides die tijdens de colleges gebruikt worden, worden voor elk college hieronder gepubliceerd.
N.B: De slides zijn niet bedoeld ter vervanging van het boek. Het kan dus lastig zijn om de stof puur met behulp van de slides, zonder het boek, te begrijpen.
N.B.2: Om gemakkelijk naar eerdere definities/resultaten/plaatjes te kunnen verwijzen tijdens het college, worden slides regelmatig hergebruikt. Er zitten dus nogal wat dubbele slides bij.

Antwoorden bij opgaven

Van een deel van de opgaven uit het boek zijn nette uitwerkingen beschikbaar. Deze vindt u hieronder. Achterin het boek staan ook nog antwoorden van een aantal opgaven.

Oude tentamens:

Tja, dit vak wordt voor het eerst gegeven. Er zijn dus nog geen oude tentamens beschikbaar. Je kunt wel kijken bij de twee voorganger vakken Automata Theory en Computability. Maar bedenk dat we bij FTB niet alle stof uit die twee vakken kunnen behandelen. Niet alle opgaven uit de oude tentamens van die vakken zullen daarom nu tot de tentamenstof behoren.
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 3 november 2025 - https://www.liacs.leidenuniv.nl/~vlietrvan1/ftb/