Languages and Machines
Faculteit  Science and Engineering 
Jaar  2017/18 
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  1. The student learns to understand and apply: (a) The basic theory of finite state, pushdown, and Turing machines, and of the regular, contextfree, and decidable and semidecidable languages. (b) The relationships between machines and languages, and the translation algorithms between the various representations (e.g. regular expressions, normal forms of grammars). 2. The student obtains an elementary understanding of decidability, undecidability, semidecidability, computability, time complexity, the classes P and NP, and the Chomsky hierarchy. 

Omschrijving  The subject matter of this course is to describe, analyse, and classify the languages that can be read by machines and the machines that can read them. It does not concern the interpretation of such languages. There are two methods to specify formal languages: (1) via machines for language recognition, (2) via grammars for language generation. The kinds of machines employed include finite state machines (both deterministic and nondeterministic), (nondeterministic)pushdown machines, and Turing machines of various flavours. The theme of finite state machines includes regular expressions and regular grammars, and the algorithms for translation between the various forms of specification. With respect to grammars, the focus is on contextfree grammars and reduction to normal form (such as the Chomsky normal form). Pumping lemmas are derived, and are applied 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), Werkcollege (T)
(en verplicht huiswerk) 

Toetsvorm 
Opdracht (AST), Schriftelijk tentamen (WE)
(20% huiswerk, 80% tentamen. Bij hertentamen telt huiswerk niet meer mee.) 

Vaksoort  bachelor  
Coördinator  dr. J.A. Perez Parra  
Docent(en)  dr. J.A. Perez Parra  
Verplichte literatuur 


Entreevoorwaarden  Recommended: Discrete Structures.  
Opmerkingen  
Opgenomen in 
