Languages and Machines
Faculteit  Science and Engineering 
Jaar  2022/23 
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, the classes P and NP, and the Chomsky hierarchy. 

Omschrijving  This course addresses a fundamental topic in 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. Formal languages are specified via (1) machines for language recognition and (2) grammars for language generation. The kinds of machines employed include (non)deterministic finite state machines, (non)deterministic pushdown machines, and Turing machines. 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). Turing machines are introduced to introduce basic concepts on the 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. 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. 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  
Verplichte literatuur 


Entreevoorwaarden  The course assumes prior knowledge acquired from courses "Introduction to Logic" and "Discrete Structures" (BSc Computing Science). The course also assumes the maturity of having completed the first year of the BSc Computing Science. 

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 
