Vanwege de coronamaatregelen kan de onderwijsvorm of tentaminering afwijken. Zie voor actuele informatie de betreffende cursuspagina’s op Brightspace.

Studiegids

nl en

Automata Theory

Vak
2020-2021

Toegangseisen

Niet van toepassing.

Beschrijving

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 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

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.

Rooster

Het meest recente rooster is te vinden op de Studenten-website:

Onderwijsvorm

Hoorcollege en werkcollege. Inleveropdrachten.

Toetsing en weging

Eindcijfer samengesteld uit schriftelijk examen (70%, tenminste cijfer 5.5) en inleveropdrachten (30%).

De docent zal de studenten informeren hoe de inzake en de nabespreking van de tentamen zal plaatsvinden.

Literatuurlijst

  • John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw Hill, 2011

Aanmelden

Aanmelden via Usis: Selfservice > Studentencentrum > Inschrijven Activiteitencodes te vinden via de facultaire website

Contact

Onderwijscoördinator Informatica, Riet Derogee

Website

Automata Theory