I00109 (I00109)
Talen en automaten*
< 2006/2007 > 18-09-2006 t/m 13-01-2007 () H
Informatica - Bachelor (2003) Grondslagen (3 ec)
Informatica - Master na HBO Artificial Intelligence variant MT (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Artificial Intelligence variant O (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Computer Security variant MT (2003) Schakelcursussen (3 ec)
Informatica - Master na HBO Computer Security variant O (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Embedded Systems variant MT (2003) Schakelcursussen (3 ec)
Informatica - Master na HBO Embedded Systems variant O (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Information Systems variant MT (2003) Schakelcursussen (3 ec)
Informatica - Master na HBO Information Systems variant O (2004) Schakelcursussen (3 ec)
Informatica - Master na HBO Software Construction variant MT (2003) Schakelcursussen (3 ec)
Informatica - Master na HBO Software Construction variant O (2004) Schakelcursussen (3 ec)
omvang
3 ec (84 uur) : 16 uur plenair college, 16 uur groepsgewijs college, 0 uur computerpracticum, 0 uur 'droog' practicum, 0 uur gesprekken met de docent, 0 uur onderling overleg met medestudenten (werkgroepen, projectwerk e.d.), 52 uur zelfstudie
investering
3 ec * 28 u/ec + #std * (1 + 3ec * 0.75 u/student/ec)
inzet tentatief
speciale web-site
http://www.cs.kun.nl/~wil

 

Computers laten je dingen doen met behulp van programmeertalen. In het college Talen en Automaten worden twee soorten formele talen ingevoerd en machines die deze talen kunnen herkennen. Het betreft de `reguliere' en de `contextvrije' talen. De machines die deze talen kunnen herkennen zijn de `eindige automaten' en de `stapel automaten'.

Leerdoelen

In de informatica wordt een taal L gezien als een collectie strings (dat zijn rijtjes symbolen uit een alfabet). Het is van belang te weten, afhankelijk van de taal, hoeveel moeite het kost om te herkennen dat een string s tot een taal L behoort. Hiervoor zullen verschillende machinemodellen (automaten) beschouwd worden. Daarbij komen zowel deterministische als niet-deterministische automaten aan bod.

Onderwerpen

aaaOnder andere de volgende begrippen komen aan bod. Reguliere en contextvrije talen. Eindige automaten (zonder geheugen) en push-down automaten (met geheugen). De correspondentie tussen talen en automaten: bij een gegeven taal een automaat maken die precies de strings in die taal kan herkennen; en andersom bij een gegeven automaat bepalen welke taal erdoor herkend wordt. Van eenvoudige talen de klassificatie in de hiƫrarchie kunnen bepalen. Van eenvoudige automaten de klassificatie kunnen bepalen. Van eenvoudige niet-deterministische automaten een deterministische versie kunnen construeren.

Toelichting

Voordat een programma door een computer verwerkt kan worden moet eerst bepaald worden of het grammatikaal correct is. Dit college gaat niet zozeer over concrete talen en machines, maar over klassen van deze begrippen. Het doel daarbij is een overzicht te krijgen van wat er mogelijk is,maar ook van wat er onmogelijk is.

Werkvormen

Hoorcolleges en practicum bijeenkomsten. Tijdens het practicum werk je onder begeleiding aan theoretische opgaven. In bijna alle weken wordt een toets afgenomen.

Vereiste voorkennis

Om het vak Talen en Automaten zinvol te kunnen verwerken dien je

  • een inzicht in wiskundige structuren te hebben;
  • eenvoudige bewijsmethoden toe te kunnen passen;
  • eenvoudige wiskundige notatievormen te kunnen begrijpen en hanteren.
Door het volgen van vakken van het eerste semester wordt aan deze eis voldaan.

Tentaminering

Schriftelijk, gesloten boek.

Combinatiemogelijkheden

Vanuit de vaklijn Theorie zijn er duidelijke koppelingen naar de vaklijnen Programmeertalen, Vertalerbouw en Wiskunde. Dit is reeds merkbaar aan het college Talen en Automaten.

Literatuur

Languages and Machines T.A. Sudkamp, Addison Wesley. ISBN 0201821362 Dit boek is onmisbaar. Het wordt ook gebruikt bij het vervolgcollege T1b. Dus snel bestellen of van een ouderejaars overnemen.


Evaluatie: studentenquêtes ; geen docentevaluatie bekend Rendement: 25 begonnen, echt meegedaan, geslaagd met 1e kans, geslaagd totaal
Q: