Toegangseisen
Aanbevolen voorkennis: Foundations of Computer Science.
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 accepteren. Dit leidt tot zogenaamde pomplemma’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:
In MyTimetable (login) kun je alle vak- en opleidingsroosters vinden, waarmee jij je persoonlijke rooster kunt samenstellen. Onderwijsactiviteiten waarvoor je je via MyStudymap hebt ingeschreven, worden automatisch in je rooster getoond. Daarnaast kun je MyTimetable 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. Je kunt notificaties aanzetten bij Instellingen, na login.
Vragen? Bekijk de video, lees de instructie of neem contact op met de ISSC helpdesk. Let op: Joint Degree-studenten Leiden/Delft dienen de informatie uit de Leidse en Delftse MyTimetables samen te voegen om een volledig rooster te zien. Deze video legt uit hoe dat werkt.
Onderwijsvorm
Per week twee uur hoorcollege en twee uur werkcollege. Daarnaast worden vier huiswerkopgaven opgegeven.
Toetsing en weging
Vier huiswerkopgaven in de loop van het semester, en schriftelijk tentamen aan het eind van het semester. Het minimumcijfer voor elke huiswerkopgave is 0, het minimumcijfer voor het tentamen is 1. De huiswerkopgaven zijn niet verplicht, maar tellen wel mee voor het eindcijfer. Het tentamencijfer moet minstens 5.5 zijn. In dat geval is het eindcijfer een gewogen gemiddelde van het tentamencijfer (70%) en het gemiddelde van de huiswerkopgaven (30%). Als dit gewogen gemiddelde lager is dan 5.5, zal het eindcijfer toch voldoende (6.0) zijn. Als het tentamencijfer minder dan 5.5 is, is het tentamencijfer tevens het 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
Inschrijven
Met ingang van het collegejaar 2022-2023 ben je als student zelf verantwoordelijk om je tijdig, dat wil zeggen 14 of 28 dagen voor aanvang van het vak, in te schrijven. Dat kan via MyStudymap. Dit doe je twee keer per jaar: één keer voor de vakken die je wilt volgen in semester 1 en één keer voor de vakken die je wilt volgen in semester 2.
Inschrijven voor vakken in het eerste semester is mogelijk vanaf juli; inschrijven voor vakken in het tweede semester is mogelijk vanaf december. Zie voor meer informatie deze pagina (tab Wiskunde en Natuurwetenschappen)
Daarnaast is het voor alle studenten, inclusief eerstejaars bachelorstudenten, verplicht om zich in te schrijven voor tentamens én de inschrijving voor elk tentamen in My Studymap te bevestigen. Dit kan tot en met uiterlijk 10 kalenderdagen voorafgaand aan het tentamen. Zonder geldige voorinschrijving én bevestiging in My Studymap kun je niet deelnemen aan het tentamen.
Uitgebreide informatie over de werking van MyStudymap vind je hier.
Contact
Onderwijscoördinator LIACS bachelors