| TDDD14 | Formal Languages and Automata Theory, 6 ECTS credits. /Formella språk och automatateori/ |
||
Prel. scheduled
hours: 50 |
|||
|
Area of Education: Technology Main field of studies: Computer Science, Computer Engineering |
|||
| Advancement level
(G1, G2, A): G2
|
|||
| Aim: This course will give an introduction to formal languages and automata theory. Automata and formal languages appear (possibly in various disguises) in almost every branch of computer science. Having completed the course the student will be able to:
|
|||
| Prerequisites: (valid for students admitted to programmes within which the course is offered) Basic mathematics, for instance given by discrete mathematics courses Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshhold requirements for progression within the programme, or corresponding. |
|||
| Supplementary courses: Compiler Construction, Complexity Theory, Rewriting Systems, Programming Theory,Logic, advanced course |
|||
| Organisation: The theory is presented during the lectures. Problem solving is practiced during the lessons. |
|||
| Course contents: Course content: Finite automata and regular expressions. Context-free grammars and pushdown automata. Deterministic context-free languages, LR parsing. Chomsky's hierarchy. Introduction to Turing Machines and undecidability. |
|||
| Course literature: D. C. Kozen, Automata and Computability, 1997, Springer Verlag. Compendium compiled at the Department of Computer and Information Science. |
|||
| Examination: | |||
| Written examination Compulsory lab assignment |
5 ECTS 1 ECTS |
||
Course language is English. Department offering the course: IDA. Director of Studies: Patrick Lambrix Examiner: Ulf Nilsson Link to the course homepage at the department Course Syllabus in Swedish |
|||
|
|
 |
|||||
| ||||||