Previous page | Current version Archive 1998/1999 
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.