Faculteit  Science and Engineering 
Jaar  2019/20 
Vakcode  INBTA08 
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 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 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)
(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 reexamination.) 

Vaksoort  bachelor  
Coördinator  prof. dr. J.A. Perez Parra  
Docent(en)  prof. dr. J.A. Perez Parra  
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, and Algorithms and Data Structures in C, and from the second year Functional Programming. 

Opmerkingen  
Opgenomen in 
