Toegangseisen
Niet van toepassing.
Beschrijving
De theorie van Automaten en Formele Talen vormt een van de hoekstenen van Theoretische Informatica, omdat ze ons instaat 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 genereren. 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.
Leerdoelen
The course gives an introduction is an introduction to the theory of computation with emphasis on the relationships between formal languages, automata and abstract models of computation.
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.
Rooster
Het meest recente rooster is te vinden op de Studenten-website:
Onderwijsvorm
Hoorcollege en werkcollege. Inleveropdrachten.
Toetsing
Eindcijfer samengesteld uit schriftelijk examen (70%, tenminste cijfer 5.0) en inleveropdrachten (30%).
Literatuur
- John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw Hill, 2010
Aanmelden
Aanmelden via Usis: Selfservice > Studentencentrum > Inschrijven Activiteitencodes te vinden via de facultaire website
Contact
Onderwijscoördinator Informatica, Riet Derogee