Formele Talen en Berekenbaarheid

najaar 2026

Toren Academiegebouw

Laatste nieuws

(25.09.2026) Huiswerkopgave 1 is deels beschikbaar. Deadline 9 oktober 2026. Zie verderop.

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 in de definitieve vorm gegeven. Vorig jaar werd in het vak een selectie van onderwerpen uit de oude vakken Automata Theory en Computability behandeld. Dit jaar wordt in principe de (hele) stof uit de tweede helft van Automata Theory en het (hele) vak Computability behandeld. Het sluit hiermee aan op het eerstejaarsvak Automaten.
Als je vorig jaar het vak Formele Talen en Berekenbaarheid niet hebt gehaald, is de versie van dit jaar niet voldoende als vervanging! Overleg in zo'n geval met de studieadviseur.

Praktische informate

Docent (voor de hoorcolleges): Rudy van Vliet
te vinden op: kamer BE.2.07 van het Gorlaeus
telefoon: 071-527 2876
email: rvvliet(at)liacs(dot)nl
Assistenten (voor de werkcolleges en huiswerkopgaven): Edzard van der Molen, Eef Witteveen
Onderwijsvorm: elke week in principe twee uur hoorcollege en twee uur werkcollege, allemaal on-campus. Daarnaast worden vier huiswerkopgaven opgegeven.
Collegetijden: van 2 september t/m 10 december 2026. In de week van 19-23 oktober zijn er helemaal geen colleges FTB.

Er komt geen livestream van de colleges. Wel worden de hoorcolleges opgenomen, en zullen de opnames achteraf (na twee weken) gepubliceerd worden op deze pagina.
Je kunt sowieso ook terugkijken naar de hoorcolleges Automata Theory en Computability van twee jaar geleden. Bedenk daarbij dat we bij FTB de eerste helft van Automata Theory overslaan.

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, Automaten

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 berekeningen en (formele) talen vast te leggen. Formele talen op hun beurt kunnen bijvoorbeeld 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. 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. Met behulp van een pomplemma tonen we aan dat bepaalde talen juist niet door een context-vrije grammatica gegenereerd kunnen worden.

De tweede 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. Recursief opsombare talen worden gegenereerd door unrestricted grammars.

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.

We vergelijken voor zowel stapelautomaten als Turingmachines 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 2026-2027 wordt men verwezen naar de studiegids. (link volgt nog)

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; 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.

Herkansing, inzage & nabespreking

De huiswerkopgaven kennen geen herkansing (want zijn niet verplicht). Het schriftelijke tentamen kan in hetzelfde studiejaar in dezelfde vorm worden herkanst. Bij het bekendmaken van de uitslag van het tentamen wordt aangegeven op welke wijze en op welk moment de inzage en nabespreking van het tentamen plaatsvindt.

Tentamens

Er zijn twee tentamens gepland, allebei on-campus:
Eerste tentamen: woensdag 13 januari 2027, 09.00-12.00, in Lecture Hall (schotel) C4/5.
Hertentamen: woensdag 24 maart 2027, 09.00-12.00, in zaal Gorlaeus BW.0.39
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 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.

Als de huiswerkopgaven beschikbaar zijn, zullen ze hieronder gepubliceerd worden. Op dit moment is beschikbaar:

Als je eindige automaten digitaal wil tekenen, 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. Dit gaat deels over stof van het vak Automaten (hoofdstukken 1, 2 en 3) en deels over de eerste helft van dit vak (hoofdstukken 4, 5 en 6).

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 de vakken Foundations of Computer Science en Automaten, in het bijzonder inductie en eindige automaten, 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, zullen we per week bijhouden welke stof en opgaven we hebben behandeld. U vindt dit overzicht hier (bijgewerkt t/m werkcollege van donderdag 24 september 2026).

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 in de huidige vorm gegeven. Er zijn dus geen tentamens uit eerdere jaren beschikbaar. Je kunt wel kijken bij de editie van vorig jaar, maar bedenk dat we bij FTB dit jaar (deels) andere stof behandelen dan vorig jaar. Je kunt ook kijken bij de twee voorganger vakken Automata Theory en Computability. We behandelen dit jaar bij FTB namelijk de tweede helft van de stof van Automata Theory en de (hele) stof van Computability.
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 25 september 2026 - https://www.liacs.leidenuniv.nl/~vlietrvan1/ftb/