| 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
(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 (like TATA17). 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:
|
||||
| Examination: | ||||
| Written examination Hand-in assignments |
3,5 p 0 p |
/ / |
5 ECTS 0 ECTS |
|
Course language is English. Department offering the course: IDA. Director of Studies: sas-sr@ida.liu.se Examiner: Ulf Nilsson Link to the course homepage at the department Course Syllabus in Swedish |
||||
|
|
 |
|||||
| ||||||