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
- there are 6 fields of study the course is directly associated with, display
- 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. Online. New York: Springer, 1997. xiii, 400. ISBN 0387949070. [citováno 2024-04-23] info
- Handbook of formal languages.. Online. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997. xx, 625. ISBN 3540614869. [citováno 2024-04-23] info
- Handbook of formal languages. background and application. Online. Edited by Grzegorz Rozenberg - Arto Salomaa. Berlin: Springer-Verlag, 1997. xxii, 528. ISBN 3540614869. [citováno 2024-04-23] info
- SIPPU, Seppo and Eljas SOISALON-SOININEN. Parsing theory : volume 2 : LR(k)and LL(k) parsing. Online. Berlin: Springer-Verlag, 1990. 417 s. ISBN 0-387-51732-4. [citováno 2024-04-23] info
- CHYTIL, Michal. Automaty a gramatiky. Online. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1984. 331 s. [citováno 2024-04-23] 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