IA006 Selected topics on automata theory
Faculty of InformaticsAutumn 2004
- 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. (seminar tutor) - 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. - Timetable
- Mon 12:00–14:50 D2
- Timetable of Seminar Groups:
IA006/02: each even Thursday 16:00–17:50 B003 - Prerequisites
- ! I006 Automata II
Knowlegde corresponding to the courses IB005 - Formal languages and automata and IB107 - Computability and complexity - Course Enrolment Limitations
- The course is only offered to the students of the study fields the course is directly associated with.
- fields of study / plans the course is directly associated with
- Applied Informatics (programme FI, N-AP)
- Informatics (programme FI, M-IN)
- Informatics (programme FI, N-IN)
- Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
- Upper Secondary School Teacher Training in Informatics (programme FI, M-TV)
- Upper Secondary School Teacher Training in Informatics (programme FI, N-SS)
- Course objectives
- The purpose of this course is to introduce computer science students to selected advanced parts of automata theory (including infinite words, bisimulations,...) and to understand methods 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.
- Transition systems and nondeterminism - bisimulation. Selected decidable problems related to process verification.
- 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
- 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, xx, 625. ISBN 3540614869. info
- Handbook of formal languages. background and application. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997, xxii, 528. 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
- CHYTIL, Michal. Automaty a gramatiky. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984, 331 s. URL info
- Assessment methods (in Czech)
- Během semestru jedna pisemná zkouška, jejíž výsledek se započítává do výsledného hodnocení s vahou cca 45%. Závěrečná zkouška je rovněž písemná; obě bez použití pomocných materiálů.
- Language of instruction
- Czech
- Follow-Up Courses
- Further Comments
- The course is taught annually.
- Teacher's information
- http://www.fi.muni.cz/usr/kretinsky/fja2.html
- Enrolment Statistics (Autumn 2004, recent)
- Permalink: https://is.muni.cz/course/fi/autumn2004/IA006