Automata Theory

najaar 2020

Toren Academiegebouw

Laatste nieuws

Huiswerkopgave 2 is nagekeken. Er vindt nog wel een tweede correctie plaats op de laatst nagekeken inzendingen. Cijfers worden naar verwachting op 2 of 3 december bekend.

College en werkcollege 13 zijn de laatste colleges. De colleges van 8 december vervallen. We zijn klaar!

Huiswerkopgave 4 is beschikbaar. Zie verderop.


Automata Theory (voorheen: Fundamentele Informatica 2) is een verplicht tweedejaars vak binnen de bachelor Informatica aan de Universiteit Leiden.

Praktische informatie

Docent: Rudy van Vliet
te vinden op: kamer 140 van het Snellius
telefoon: 071-527 2876
email: rvvliet(at)liacs(dot)nl
Assistent voor de huiswerkopgaven: Femke Slangen
Onderwijsvorm: weblectures voor hoorcollege en werkcollege, online vraag- en antwoordsessies en huiswerkopgaven
Collegetijden: hoorcollege op dinsdagmiddag, 14.15-16.00 uur, als weblecture
werkcollege op dinsdagmiddag, 16.15-17.00 uur, als weblecture
interactieve vraag- en antwoordsessies op dinsdagmiddag, 17.15-18.00 uur, in Kaltura (te bereiken via Brightspace -> Course tools -> Kaltura Media -> Join room (rechtsboven) ),
van 1 september t/m 8 december 2020
(allemaal volgens het rooster van 28 augustus 2020).
Het is mijn bedoeling om de weblectures niet al te lang (misschien maar een paar weken) online te laten staan. Zorg dus dat je ze op tijd bekijkt. En maak aantekeningen.
Andere onderdelen van deze website, zoals de collegeslides, blijven wel gewoon tot en met (in ieder geval) het hertentamen online.

Studielast

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

Aanbevolen voorkennis

Fundamentele Informatica 1.

Inhoud

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. Wanneer we een beperkte vorm van extern geheugen aan de eindige automaat toevoegen, ontstaat de stapelautomaat, een krachtiger concept.

We bestuderen de twee types automaten, en de structuur van de talen die ze kunnen accepteren. Dit leidt tot zogenaamde pomp-lemma's die laten zien dat bepaalde talen juist niet door een automaat kunnen worden herkend. We vergelijken voor beide types automaten de deterministische en niet-deterministische varianten. Verder verkennen we algoritmes die van beschrijvingen van eenvoudige talen meer complexe talen maken, de zogenaamde afsluitingseigenschappen.

De studie van talen en automaten kan niet zonder het kijken naar de Chomsky hierarchie van talen, automaten en hun bijpassende grammatica's. Zo laten we zien dat talen van eindige automaten kunnen worden beschreven door reguliere expressies. Verder komt aan de orde dat de stapelautomaat correspondeert met de context-vrije grammatica.

Voor globale informatie over het vak in studiejaar 2020-2021 wordt men verwezen naar de algemene webpagina.

Doelstelling

Het vak biedt een introductie tot de `theory of computation', met een nadruk op de relaties tussen formele talen, automaten en grammatica's.

Toetsing

Schriftelijk tentamen aan het eind van het semester.

Het eindcijfer van het vak is een gewogen gemiddelde van het tentamencijfer (70%) en het gemiddelde van de huiswerkopgaven (30%). Het tentamencijfer zelf moet minstens 5.5 zijn. In dat geval zal het eindcijfer ook minstens 5.5 zijn, zelfs als je geen enkele huiswerkopgave hebt gemaakt. Wie het tentamen niet haalt, krijgt het (onvoldoende) tentamencijfer als eindcijfer.

Tentamens

Er zijn twee tentamens gepland:
Eerste tentamen: maandagochtend 11 januari 2021, (exacte tijd?)
Hertentamen: dinsdag 23 maart 2021, 10.15 uur -- 13.15 uur (onder voorbehoud). Beide tentamens worden, als het goed is, `gewoon' fysieke tentamens.

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 of vijf huiswerkopgaven opgegeven. Deze zijn samen goed 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.
Huiswerkopgaven dienen op of voor de deadline ingeleverd te worden. Haal je die deadline niet, dan heeft het geen zin meer om het huiswerk in te leveren. Dat wil zeggen: het levert geen punten meer op.
Je bent niet verplicht om de huiswerkopgaven te maken. Het is echter wel aan te raden, want: (1) het vormt een nuttige oefening voor het tentamen, en (2) als je huiswerkopgaven mist, krijg je een 0 voor die opgaven, en dat kan negatief doorwerken in je eindcijfer voor het vak.

Resultaten voor de huiswerkopgaven van Fundamentele Informatica 2 uit een eerder studiejaar zijn dit jaar niet meer geldig.

De cijfers voor de huiswerkopgaven komen te zijner tijd in Brightspace.

Inmiddels is beschikbaar

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)
NB: dit boek wordt ook gebruikt bij het college Fundamentele Informatica 3 / Computability.
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. Misschien is het online nog wel te vinden.

Tentamenstof

De tentamenstof zal bestaan uit Een compleet, gedetailleerd overzicht van de tentamenstof, komt na het laatste college op deze site.

Opmerkingen: Begrippen en notaties behandeld bij Fundamentele Informatica 1 worden bekend verondersteld.

Behandelde stof, opgaven en slides

Voor wie door omstandigheden een hoorcollege of werkcollege moet missen, zullen we per week bijgehouden welke stof en opgaven we hebben behandeld. U vindt dit overzicht hier (bijgewerkt t/m werkcollege 13 van 1 december 2020, compleet dus)

De slides die tijdens de colleges gebruikt worden, worden na elk college hieronder gepubliceerd.

In de slides van het hoorcollege wordt regelmatig verwezen naar twee boeken:
[M]: het boek van John C. Martin dat hierboven genoemd wordt
[L]: Peter Linz: An Introduction to Formal Languages and Automata

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

De afgelopen jaren is het vak Fundamentele Informatica 2 door andere docenten gegeven. Nieuwe tentamens voor het huidige vak Automata Theory kunnen dus een (iets) ander karakter krijgen dan de tentamens van toen: De laatste keer dat het vak Fundamentele Informatica 2 werd gegeven, was in het najaar van 2019. De website van die keer vindt u hier. Daar vindt u ook een verwijzing naar de editie van najaar 2018, met nog meer oude tentamens.
Vragen en opmerkingen kunt u sturen naar:
Rudy van Vliet; rvvliet(at)liacs(dot)nl
Laatste wijziging: 1 december 2020 - http://www.liacs.leidenuniv.nl/~vlietrvan1/automata/