|
49409 Automata, Formal Languages and Computability
| |
Danish title: Automater, sprog og beregnelighed
| |
Language: English
Credit points: 5 |
|
| Type: | Open University
Language: English |
| |
| |
| |
| |
Prerequisite: 49142
| |
| |
Recommended semester: 4th -7th semester
| |
Scope and form: 2 lectures per week. 2 hours per week with problem solving.
| |
Examination: Compulsory coursework and written exam ??? (13-scale)
| |
| |
| |
| |
URL: http://www.it.dtu.dk/c49409
| |
Department: Department of Information Technology
|
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.
|
|
|
