Languages and Machines

Faculteit Science and Engineering
Jaar 2019/20
Vakcode INBTA-08
Vaknaam Languages and Machines
Niveau(s) bachelor
Voertaal Engels
Periode semester II b

Uitgebreide vaknaam Languages and Machines
Leerdoelen At the end of the course, the student is able to:
1) Understand and apply the basic theory of finite state, pushdown, and Turing machines, and of the regular, context-free, and decidable and semi-decidable languages.
2) Understand and apply the relationships between machines and languages, and the translation algorithms between the various representations (e.g. regular expressions, normal forms of grammars).
3) Apply an elementary understanding of decidability, undecidability, semi-decidability, computability, time complexity, the classes P and NP, and the Chomsky hierarchy.
Omschrijving This course studies how to describe, analyse, and classify the (formal) languages that can be read by machines, as well as the machines that can read those languages.

There are two methods to specify formal languages: (1) via machines for language recognition, and (2) via grammars for language generation. The kinds of machines employed include (non)deterministic finite state machines, (non)deterministic pushdown machines, and Turing machines of various flavours.

The theme of finite state machines includes regular expressions and regular grammars, and algorithms for translating between the various forms of specification. With respect to grammars, the focus is on context-free grammars and reductions to grammars in normal form (such as the Chomsky normal form). Pumping lemmas are introduced as a tool to show that certain languages are not regular, or not context-free.

Turing machines are introduced to formalize decidability and semi-decidability of languages, and computability of functions. The closure properties of the classes of regular languages, of context-free languages, of decidable and semi-decidable languages are investigated. Turing's halting language and some other languages are proved to be undecidable. The course concludes with the Chomsky hierarchy of languages.

The course has a strong mathematical flavour in that the student must learn to prove or refute plausible assertions. It is also useful to execute the algorithms presented by hand in elementary cases, because this enhances the understanding of them. The lecture notes therefore contain many exercises, some of which will be done in the tutorials or the homework.
Uren per week
Onderwijsvorm Hoorcollege (LC), Opdracht (ASM), Werkcollege (T)
(en verplicht huiswerk)
Toetsvorm Opdracht (AST), Schriftelijk tentamen (WE)
(Homework 30% and Exam 70%. The final grade must be equal or above 5.75 for students to pass the course. The homework grade does not count at the re-examination.)
Vaksoort bachelor
Coördinator prof. dr. J.A. Perez Parra
Docent(en) prof. dr. J.A. Perez Parra
Verplichte literatuur
Titel Auteur ISBN Prijs
Lecture notes: Languages and Machines by W.H. Hesselink (available online) ca. €  8,00
Entreevoorwaarden The course unit assumes prior knowledge acquired from Discrete Structures (BSc Computing Science).
The course also assumes the maturity of having completed the first year of the Bachelor CS; in particular, it assumes certain elements from the courses Calculus, and Algorithms and Data Structures in C, and from the second year Functional Programming.
Opgenomen in
Opleiding Jaar Periode Type
BSc Computing Science 2 semester II b verplicht
BSc Courses for Exchange Students: Artificial Intelligence & Computing Science - semester II b Computing Science