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
Recognize languages in the different families 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
Schedule
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.
Teaching method
Weekly lecture and exercise class.
Assesment 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. Participation in at least two of the three quizzes is mandatory.
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. Naturally, the weighted average of all components should be at least 5.5.
Resit, review & feedback
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.
Reading list
Peter Linz & Susan H. Rodger; An Introduction to Formal Languages and Automata; 7th edition; Jones & Bartlett Learning; 2023
Registration
Contact
For substantive questions, contact the lecturer (listed in the right information bar). For questions about enrolment, admission, etc., contact the Education Administration Office.
Remarks
If you wish to carry over partial results from the previous iteration of this course (Languages and computation), please contact the lecturer ASAP to discuss the possibilities. Partial results for Automata Theory recorded in any previous year cannot be carried over to this course.