Admission Requirements
Recommended prior knowledge: Foundations of Computer Science, Algorithms and Data Structures
Description
Formal languages play a fundamental role in computer science in the description of programming languages, but also in the analysis and generation of natural language. In the Chomsky hierarchy, languages are categorized in different classes, each corresponding to a certain model of language recognizers and generators. During this course, we will look at these models and the fundamental differences between them in terms of expressivity and complexity.
In addition to being tied to the categories of languages, the language recognizers can also be viewed as models of computation. In particular, the Turing machine can be seen as general model of computation on which modern-day computers are still based. We will have a detailed look at what these models can and cannot compute.
Course Objectives
After this course, students are able to
Describe the different families of languages in the Chomsky hierarchy, and the corresponding models for language recognition and generation and their limitations
Construct a regular expression for a regular language, and construct a parser for regular expressions and comment on its time and space complexity
Construct a context-free grammar for a context-free language, and construct bottom-up and top-down parsers for context-free grammars and comment on their merits and drawbacks
Understand the definition of core concepts concerning formal grammars, such as derivations, parse trees, ambiguity, and normal forms
Describe a Turing machine as general model of computation, and comment on its limitations in terms of decidability and tractability of problems
Read and understand formal notation for definitions in the field of languages and computability and reasoning about these definitions
Timetable
In MyTimetable, you can find all course and programme schedules, allowing you to create your personal timetable. Activities for which you have enrolled via MyStudyMap will automatically appear in your timetable.
Additionally, you can easily link MyTimetable to a calendar app on your phone, and schedule changes will be automatically updated in your calendar. You can also choose to receive email notifications about schedule changes. You can enable notifications in Settings after logging in.
Questions? Watch the video, read the instructions, or contact the ISSC helpdesk.
Note: Joint Degree students from Leiden/Delft need to combine information from both the Leiden and Delft MyTimetables to see a complete schedule. This video explains how to do it.
Mode of Instruction
Weekly lecture and exercise class.
Assessment Method
The assessment of the course consists of three parts:
3 coding assignments + quizzes (10%)
Midterm exam (20%)
Final exam (70%)
For every coding assignment, there will be a corresponding quiz, organized during a lecture or exercise class.
The midterm exam only counts if it is beneficial to the final grade; otherwise, the final exam counts for 90%.
In order to pass the course, the grade for the final exam needs to be at least 5.0. In addition, the average grade for the coding assignments and quizzes needs to be at least 5.0. Naturally, the weighted average of all components should be at least 5.5.
There is a retake exam which replaces the grade for the final exam; the grade for the midterm still only counts if it is beneficial. There is also a retake opportunity for the coding assignments and quizzes, which replaces the grade only for these.
Reading List
Peter Linz & Susan H. Rodger, An Introduction to Formal Languages and Automata, 7th edition, Jones & Bartlett Learning, 2023
Registration
Contact
Education coordinator LIACS bachelors
Remarks
This course replaces the course Automata Theory (taught until 2024-2025) in the bachelor Data Science and Artificial Intelligence. Partial results for Automata Theory recorded in any previous year cannot be carried over to this course.