| TDDD14 |
Formal Languages and Automata Theory, 6 ECTS credits.
/Formella språk och automatateori/
For:
D
I
Ii
IT
MMAT
|
| |
Prel. scheduled
hours: 50
Rec. self-study hours: 110
|
| |
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:
- Deal with regular and context-free languages;construct, understand and apply their formal descriptions.
- Describe relations between languages and language classes.
- Apply basic parsing methods.
- Explain the difference between decidable and undecidable problems.
|
|
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, published at the homepage.
|
|
Examination: |
|
Written examination
Hand-in assignments
|
5 ECTS
1 ECTS
|
| |
|
|
Course language is Swedish.
Department offering the course: IDA.
Director of Studies: Ahmed Rezine
Examiner: Johannes Schmidt
Link to the course homepage at the department
Course Syllabus in Swedish
|