FI:IA006 Automata theory - Course Information
IA006 Selected topics on automata theory
Faculty of InformaticsAutumn 2014
- Extent and Intensity
- 2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: z (credit).
- Teacher(s)
- prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (alternate examiner)
prof. RNDr. Jan Strejček, Ph.D. (alternate examiner)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
doc. RNDr. Tomáš Brázdil, Ph.D. (seminar tutor)
Mgr. Karolína Malá (seminar tutor)
RNDr. František Blahoudek, Ph.D. (assistant)
Mgr. Bc. Tomáš Janík (assistant)
doc. RNDr. Petr Novotný, Ph.D. (assistant) - Guaranteed by
- prof. RNDr. Mojmír Křetínský, CSc.
Department of Computer Science – Faculty of Informatics
Contact Person: prof. RNDr. Mojmír Křetínský, CSc.
Supplier department: Department of Computer Science – Faculty of Informatics - Timetable
- Thu 10:00–11:50 D1
- Timetable of Seminar Groups:
IA006/02: each odd Thursday 12:00–13:50 A218, J. Barnat
IA006/03: each even Monday 8:00–9:50 B410, T. Brázdil
IA006/04: each odd Monday 8:00–9:50 B410, T. Brázdil
IA006/05: each even Monday 12:00–13:50 C511, K. Malá
IA006/06: each odd Monday 12:00–13:50 C511, K. Malá
IA006/07: each even Monday 10:00–11:50 C525, V. Řehák
IA006/08: each odd Monday 10:00–11:50 C525, V. Řehák
IA006/09: each even Wednesday 14:00–15:50 A217, J. Strejček
IA006/10: each odd Wednesday 14:00–15:50 A217, J. Strejček - Prerequisites
- Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity
- Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
The capacity limit for the course is 256 student(s).
Current registration and enrolment status: enrolled: 0/256, only registered: 0/256, only registered with preference (fields directly associated with the programme): 0/256 - fields of study / plans the course is directly associated with
- Applied Informatics (programme FI, N-AP)
- Information Technology Security (programme FI, N-IN)
- Bioinformatics (programme FI, N-AP)
- Information Systems (programme FI, N-IN)
- Informatics (eng.) (programme FI, D-IN4)
- Informatics (programme FI, D-IN4)
- Mathematical Informatics (programme FI, B-IN)
- Parallel and Distributed Systems (programme FI, N-IN)
- Computer Graphics (programme FI, N-IN)
- Computer Networks and Communication (programme FI, N-IN)
- Computer Systems and Technologies (eng.) (programme FI, D-IN4)
- Computer Systems and Technologies (programme FI, D-IN4)
- Computer Systems (programme FI, N-IN)
- Embedded Systems (eng.) (programme FI, N-IN)
- Embedded Systems (programme FI, N-IN)
- Service Science, Management and Engineering (eng.) (programme FI, N-AP)
- Service Science, Management and Engineering (programme FI, N-AP)
- Social Informatics (programme FI, B-AP)
- Theoretical Informatics (programme FI, N-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, N-SS) (2)
- Artificial Intelligence and Natural Language Processing (programme FI, N-IN)
- Image Processing (programme FI, N-AP)
- Course objectives
- At the end of the course students should be able to understand and explain selected advanced parts of automata theory, including parsing techniques for deterministic contex-free languages, relationship betwqeen finite-state automata and MSO logic, automata on infinite words, and process specifications. Further, students should be able to make reasoned decisions about computational models appropriate for the respective area and to understand methods and techniques of their applications.
- Syllabus
- Methods of syntactic analyses of detCFLs.
- LL(k) grammars and languages, properties and analyzers.
- LR(k) grammars and languages, properties and analyzers.
- Relationships between LL, LR and detCFL.
- Infinite=state transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
- Finite-state automata and monadic second-order logic
- Automata and infinite words: infinite words, regular (rational) sets of infinite words.
- Automata: deterministic and nondeterministic Buchi automata, Muller, Rabin, and Street automata. McNaughton theorem. Relationships.
- Literature
- CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
- KOZEN, Dexter C. Automata and computability. New York: Springer, 1997, xiii, 400. ISBN 0387949070. info
- Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxiv, 873. ISBN 3540614869. info
- Handbook of formal languages. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xx, 625. ISBN 3540614869. info
- SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Berlin: Springer-Verlag, 1990, 417 s. ISBN 0-387-51732-4. info
- další odkazy na studijní literaturu jsou uvedeny na webové stránce předmětu.
- Teaching methods
- Lectures, exercises, and reading. Optional homeworks.
- Assessment methods
- One midterm written exam and written final exam. Grading for the course: 25% the midterm exam, 75% the final exam. Exams are written without any reading materials (closed book).
- Language of instruction
- Czech
- Follow-Up Courses
- Further Comments
- Study Materials
The course is taught annually. - Teacher's information
- http://www.fi.muni.cz/usr/kretinsky/fja2.html
- Enrolment Statistics (Autumn 2014, recent)
- Permalink: https://is.muni.cz/course/fi/autumn2014/IA006