| TDDA89 | Formal Languages and Automata Theory, 5 ECTS credits. /Formella språk och automatateori/ |
||
Prel. scheduled
hours: 50 |
|||
|
Area of Education: Technology Subject area: Computer Science/Computer Engineering |
|||
| Advancement level
(A-D): B
|
|||
| Aim: The purpose of the course is to give an introduction to formal languages and automata theory. |
|||
| Prerequisites: (valid for students admitted to programmes within which the course is offered) TATA35 Discrete mathematics, or equivalent 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: TDDB44 Compiler Construction, TDDB41 Complexity Theory, TDDB40 Rewriting Systems, TDDA43 Programming Theory, TDDB08 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 Hand-in assignments |
3,5 p 0 p |
||
Course language is English. Department offering the course: IDA. Director of Studies: sas-sr@ida.liu.se Examiner: Wlodek Drabent Link to the course homepage at the department Course Syllabus in Swedish |
|||
|
|
 |
|||||
| ||||||