| Aan het einde van deze cursus kunnen de studenten
- talen karakteriseren via reguliere expressies, automaten en grammatica's;
- bij een gegeven taal een herkennende automaat construeren;
- eigenschappen van talen onderzoeken aan de hand van beschrijvingen en automaten;
- een gegeven taal classificeren in de talenhiërarchie.
|
| In deze cursus maak je kennis met methoden om een (computer)taal heel precies te beschrijven en met mechanismen om na te gaan of een gegeven tekst tot die taal behoort. Je past deze methoden toe op een voorbeeld uit de praktijk.
Aspecten van deze cursus kom je overal tegen in de informatica, bijvoorbeeld bij het ontwerp van programmeer- en specificatietalen en bij de constructie van vertalers (compilers) en gebruikersinterfaces.
|
|
|
|
 • Woorden, talen, klassen van talen; de Chomsky hiërarchie in het kort
• Reguliere talen: reguliere expressies, reguliere grammatica's, eindige automaten, pomplemma
• Contextvrije talen: contextvrije grammatica's, standaardvormen, stapelautomaten
• Toepassingen: alternatieve beschrijvingen, parseren |
De beoordeling is gebaseerd op drie resultaten:
• de huiswerk opdrachten (h),
• een schriftelijk deeltentamen over het onderdeel reguliere talen (t1),
• een schriftelijk deeltentamen over het onderdeel contextvrije talen (t2).
Het eindcijfer voor Talen en Automaten is (t1+t2)/2 + h/10 mits:
• beide deeltentamencijfers >= 5 zijn
• het huiswerkcijfer >= 5 is |
De studenten kunnen
• wiskundige definities in termen van verzamelingen, relaties en functies uitleggen;
• elementaire bewijsmethoden voor deze structuren toepassen;
• eigenschappen voor natuurlijke getallen bewijzen met behulp van volledige inductie.
Hiervoor volstaat het succesvol doorlopen van de cursus Wiskundige Structuren. |
| Dictaat van Alexandra Silva (beschikbaar via de website van de cursus): "Languages and Automata",Slides van de cursus (beschikbaar via de website van de cursus)T.A. Sudkamp, Languages and Machines: An introduction to the theory of computer science, Third Edition, Pearson/Addison Wesley, Boston etc., 2006. ISBN 0-321-31534-0. |
• 16 uur hoorcollege
• 16 uur werkcollege
• 52 uur zelfstudie |
| | Verplicht materiaalDictaat| Dictaat van Alexandra Silva: "Languages and Automata" |
| | Handouts |
|
Aanbevolen materiaalBoek| T.A. Sudkamp, Languages and Machines: An introduction to the theory of computer science, Third Edition, Pearson/Addison Wesley, Boston etc. |
|
|
WerkvormenToetsenTentamen| Weging | | 1 |
| Gelegenheden | | Blok KW2, Blok KW4 |
|
|
| |