Toegangseisen
Recommended prior knowledge: Foundations of Computer Science.
Beschrijving
Automata theory and formal languages form the foundations of theoretical computer science, as they allow us to talk precisely about what an algorithm or a computation is, and what the complexity of an algorithm is. An automaton is in fact a model of computation that can be defined mathematically. Formal languages are used to describe the result of the computation, and the computational power of the model as such.
The simplest automaton that we will consider in this course is the finite automaton: a machine that is only able to keep track of its current state but has no memory. Finite automata specify an algorithmic procedure for recognizing whether a word is in a language. We will concentrate on the relationships between languages recognized by a finite automaton, languages generated by a grammar and languages described by a so-called regular expression. We will obtain algorithms for translating one description of a language into another.
Adding a restricted form of memory to finite automata increases its expressivity. We will study push-down automata, i.e. the class of automata with an auxiliary memory organized as a stack. The languages accepted by a push-down automaton can be generated by context-free grammars, which also play a crucial role in the definition of programming languages. Push-down automata, in turn, are important in compiler design and parsing.
Both for finite automata and push-down automata, we compare the deterministic and the non-deterministic variants. We also explore closure properties, which may be used to build more complex languages from simple languages. We finally study the limitations of both models with so-called pumping lemmas.
Leerdoelen
After this course, students are able to
design a finite automaton for a given language and interpret finite automata
design regular expressions for a given language and interpret regular expressions
design context-free grammars for a given language and interpret context-free grammars
design pushdown automata for a given language and interpret pushdown automata
reproduce and apply definitions of, e.g., the above concepts, distinguishability, a derivation (tree), a computation
describe and apply constructions, e.g.,
- to minimize finite automata
- between finite automata and regular expressions
- between finite automata and regular grammars
- to convert context-free grammars into some normal form
- between context-free grammars and push-down automata
prove and apply simple properties, including closure properties and pumping lemmas
Rooster
In MyTimetable 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 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. Je kunt notificaties aanzetten bij Instellingen, nadat je bent ingelogd.
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
Every week a two-hour lecture and a two-hour exercise class. In addition, four homework assignments are provided.
Toetsing en weging
Four homework assignments in the course of the semester, and a written exam at the end of the semester. The minimum grade for every homework assignment is 0, the minimum grade for the exam is 1. The homework assignments are not mandatory, but do count for the final grade. The grade for the exam must be at least 5.5. In that case, the final grade is a weighted average of the exam grade (70%) and the average homework grade (30%). If this weighted average happens to be less than 5.5, then the final grade will still be sufficient (6.0). If the exam grade is less than 5.5, then the final grade will be equal to the exam grade.
Partial grades received in earlier years for homework and/or exam cannot be carried over to the new year.
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
Als student ben je zelf verantwoordelijk voor het tijdig inschrijven via MyStudyMap.
In deze korte video zie je stap voor stap hoe je je kunt inschrijven voor cursussen in MyStudyMap.
Uitgebreide informatie over de werking van MyStudyMap vind je hier.
Er zijn twee inschrijfperiodes per jaar:
de inschrijving voor het najaar opent in juli
de inschrijving voor het voorjaar opent in december
Zie deze pagina voor meer informatie over deadlines en inschrijven voor vakken en tentamens.
Let op:
Het is verplicht om je in te schrijven voor alle activiteiten die je gaat volgen van een vak.
Je inschrijving is pas voltooid wanneer je je cursusplanning indient in het tabblad ‘Klaar voor inschrijving’ door op ‘indienen’ te klikken.
Niet ingeschreven zijn voor een (her)tentamen betekent dat je niet mag deelnemen aan het (her)tentamen.
Contact
Onderwijscoördinator LIACS bachelors
Opmerkingen
Software
Vanaf collegejaar 2024/2025 werkt de faculteit Wiskunde en Natuurwetenschappen met het software distributieplatform Academic Software. Via het platform kun je toegang krijgen tot de software die je nodig hebt voor bepaalde vakken in je studie. Voor sommige software moet je laptop aan bepaalde systeemeisen voldoen. Dit staat aangegeven bij de software. Belangrijk is dat je de software installeert voor de start van het vak. Meer informatie over het laptopprofiel vind je op de studentenwebsite.