Languages and Machines
Faculteit  Science and Engineering 
Jaar  2021/22 
Vakcode  WBCS02705 
Vaknaam  Languages and Machines 
Niveau(s)  bachelor 
Voertaal  Engels 
Periode  semester II b 
ECTS  5 
Rooster  rooster.rug.nl 
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, contextfree, and decidable and semidecidable 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, semidecidability, computability, time complexity, the classes P and NP, and the Chomsky hierarchy. 

Omschrijving  This course addresses a topic with foundational and practical relevance for Computer Science: how to describe, analyze, 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 contextfree 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 contextfree. Turing machines are introduced to formalize decidability and semidecidability of languages, and computability of functions. The closure properties of the classes of regular languages, of contextfree languages, of decidable and semidecidable 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)  
Toetsvorm 
Opdracht (AST), Schriftelijk tentamen (WE)
(Homework 40% and Exam 60%. The final grade must be equal or above 5.75 for students to pass the course. The homework grade does not count at the reexamination.) 

Vaksoort  bachelor  
Coördinator  prof. dr. J.A. Perez Parra  
Docent(en)  prof. dr. J.A. Perez Parra , D.R.S. Ramanayake, PhD.  
Verplichte literatuur 


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, Algorithms and Data Structures in C, and Functional Programming. 

Opmerkingen  All CS bachelor courses have limited enrollment:  CS students can always enter each course, regardless of whether the course is mandatory for them or not.  A maximum of only 20 places per course is available for nonCS students. These places are filled on a firstcomefirstserved basis, with priority given to students with a strong CSrelated background (e.g., CS exchange students, AI students, etc.). These students need to meet the course prerequisite requirements as mentioned on Ocasys.  Six weeks before the course starts, the 20 students that can join are selected and added to the course. If you enroll after this date, you will be placed on the waiting list. See here for more info about the enrollment procedure. 

Opgenomen in 
