|
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. |
|
|
