49409 Automata, Formal Languages and Computability

Danish title: Automater, sprog og beregnelighed

 Type: Å, Language: E 
Credit points:
5 point 


Offered by:
Department of Information Technology
(IT) 
Prerequisite: 49142 
Recommended semester:
4th 7th semester 
Scope and form: 2 lectures per week. 2 hours per week with problem solving. 
Examination:
Approval of compulsory activities is a prerequisite for taking part in the exam. Written exam
(13 point scale
) 
Contact person: 
Michael R. Hansen, IT, Building 343, Tel. +45 4525 3727 

Aim: To give the students insight into different models for programs and computers, and their power. Furthermore, to give the students an understanding of principle limits for what problems can be solved on a computer. In this study the students will be acquainted with fundamental concepts and constructions that are used in, e.g., application programs, compilers, and verification tools.

Contents: Automata based models of computers, e.g., finite state machines, and stack and Turing machines. Characterization of the power of the different models through formal languages. The languages are described using regular expressions and grammars. For each model, we give problems that cannot be solved using the particular model. 

