By the end of this course, the students can
- recognise and describe languages using various kinds of automata, grammars, regular expressions and set-theoretic descriptions
- carry out basic constructions on automata and expressions, including constructions to convert between different descriptions of regular and context-free languages
- classify languages in the Chomsky hierarchy
- define and reason about languages and words using structural induction
In this course, you learn to accurately and formally describe (computer) languages, and mechanisms to check whether a given word/text is a member of such a language. You learn about different classes of languages, and ways to describe these with mathematical models. Aspects of this course occur throughout computer science, for example in the design of programming languages, in (network) protocols, text processing, program verification, and in compiler construction. |
The students can
It suffices to succesfully complete the course Mathematical Structures.
- explain mathematical definitions in terms of sets, relations and functions
- apply elementary proof techniques for these structures
- prove properties of natural numbers using induction
The final grade is based on:|
• weekly homework assignments (h),
• final exam (t)
Homework qualifies as a potential bonus for the final grade, which is t + h/10, provided that t >= 5 (the final grade is t itself if t < 5).