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
Getting familiar with the theory of computation in general, and formal languages, automata and grammars in particular.
Being able to construct automata, regular expressions and context-free grammars to describe given languages.
Understanding the power and limitations of the models, and the relations between them.
Being able to prove simple properties and to apply pumping lemmas.
Rooster
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
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.
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 via My Studymap. Zonder geldige voorinschrijving 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