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.
Aanbevolen voorkennis: Foundations of Computer Science
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
Per week twee uur hoorcollege en twee uur werkcollege. Daarnaast worden vier huiswerkopgaven opgegeven.
Toetsing en weging
Schriftelijk tentamen en huiswerkopgaven. Het eindcijfer is een gewogen gemiddelde van het tentamencijfer (70%) en het gemiddelde van de huiswerkopgaven (30%). Het tentamencijfer 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.
De docent zal de studenten informeren hoe de inzage en de nabespreking van de tentamens zal plaatsvinden.
Literatuurlijst
- John C. Martin, Introduction to Languages and the Theory of Computation, 4th edition, McGraw Hill, 2011
Aanmelden
Aanmelding voor vakken verloopt via uSis. Hiervoor is de uSis-code van het vak nodig, die te vinden zijn in de Studiegids. Meer info over het inschrijven voor vakken of tentamens is hier te vinden.
MyTimetable
In MyTimetable kun je alle vak- en opleidingsroosters vinden, waarmee jij je persoonlijke rooster kunt samenstellen. Onderwijsactiviteiten waarvoor je in uSis staat ingeschreven, worden automatisch in je rooster getoond. Daarnaast kun je My Timetable gemakkelijk koppelen aan een agenda-app op je telefoon en worden roosterwijzigingen automatisch in je agenda doorgevoerd; bovendien ontvang je desgewenst per e-mail een notificatie van de wijziging.
Vragen? Bekijk de video-instructie, lees de instructie of neem contact op met de ISSC helpdesk.
Brightspace
Inschrijving voor vakken verloopt via uSis. Wanneer je je hier inschrijft voor een bepaald vak krijg je automatisch ook toegang tot de omgeving van dit vak via Brightspace.
Voor meer informatie over Brightspace kun je op deze link klikken om de handleidingen van de universiteit te bekijken. Bij overige vragen of problemen kan contact opgenomen worden met de helpdesk van de universiteit Leiden.
Contact
Onderwijscoördinator Informatica, Riet Derogee