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 1 december 2020
Studielast
Met het behalen van dit vak verdient u 6 EC.
Het niveau van het vak wordt aangeduid als `200'.
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.
Introductie tot de modellen binnen de Chomsky hierarchy.
Begrip van de kracht en beperkingen van de modellen, en hun onderlinge
relatie.
Eenvoudige eigenschappen kunnen bewijzen, maar ook het kunnen opstellen
van grammatics's en automaten voor gegeven talen.
Toepassen van pomplemma'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 (`gewoon' fysiek) geweest: Eerste tentamen:
maandagochtend 11 januari 2021, 09.00 - 12.00 uur in de grote hal
(sports hall) van het Universitair Sportcentrum.
Hertentamen:
donderdag 25 maart 2021, 09.00 uur - 12.00 uur
in
het Snellius.
Beide tentamens zijn nog terug te vinden in de lijst met oude tentamens
onderaan deze pagina. Van het eerste tentamen staat daar ook
een handgeschreven uitwerking van de docent.
De tentamens zijn nagekeken. De tentamencijfers, met de bijbehorende
eindcijfers, staan in
Brightspace.
Vragenuur
Op vrijdag 8 januari was er een vragenuur voor het tentamen gepland.
Daarbij kon je dan de vragen stellen die opgekomen waren bij
het leren voor het tentamen.
Huiswerkopgaven
In de loop van het semester
zijn vier huiswerkopgaven
opgegeven.
Deze waren 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.
Alle huiswerkopgaven van dit jaar zijn nagekeken. De cijfers staan in
Brightspace.
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 bestaat uit
de stof die tijdens de colleges is
behandeld
met de bijbehorende opgaven.
Alles bij elkaar is dit geworden:
Paragraaf 1.4
Hoofdstuk 2, minus
het bewijs van Stelling 2.36 `van rechts naar links'
(dat M_L inderdaad L accepteert en minimaal is)
Hoofdstuk 3, minus
constructie en bewijs Stelling 3.17
bewijs Stelling 3.18
inductiebewijs voor L(M1)* in Stelling 3.25
maar plus
alternatieve, eenvoudigere constructie voor Stelling 3.17 (zonder
bewijs)
algoritme van Brzozowski en McCluskey (uit college en opgave 3.54)
(inverse) homomorfismes (uit college en opgave 3.53)
en met notatie
L^k(i,j) en r^k(i,j) ipv L(i,j,k) en r(i,j,k) in bewijs voor Stelling 3.30
Hoofdstuk 4, minus
blz 147-148
operations on languages (even/odd/chop) en attribute grammars uit
college 9
maar plus
live, reachable, useful variabelen (uit college en opgaven 4.51-4.53)
Hoofdstuk 5, minus
inductiebewijs dat L(NT(G)) ⊆ L(G) bij Stelling 5.18
inductiebewijs in beide richtingen bij Stelling 5.23
inductiebewijs in beide richtingen bij Stelling 5.29
blz 195-196
maar plus
elimineren linksrecursie en factoriseren (uit opgaven 5.39-5.43)
Hoofdstuk 6, minus
tweede helft van blz 211 en blz 212-213
inductiebewijs bij Stelling 6.13
Ook als bewijzen geen tentamenstof zijn, zijn de bijbehorende
constructies dat wel, tenzij expliciet anders vermeld.
N.B:
Er bestaan vaak meerdere constructies om hetzelfde doel
te bereiken. Het internet staat er vol mee. Het is voor de huiswerkopgaven
en het tentamen van belang dat je de constructies gebruikt die we bij
dit vak behandeld hebben. Anders kan er aftrek gegeven worden.
Opmerkingen:
Begrippen, notaties en technieken
behandeld bij Fundamentele Informatica 1,
met name inductie,
worden bekend verondersteld en moeten kunnen worden gebruikt.
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 zijn,
zijn hieronder nog te bekijken.
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.
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
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.
Ook de tentamenstof is niet per se helemaal hetzelfde.
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: 19 augustus 2021
- https://www.liacs.leidenuniv.nl/~vlietrvan1/automata/najaar2020/
