I505 Formal Languages and Automata I

Faculty of Informatics
Spring 2001
Extent and Intensity
3/2. 5 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium), z (credit).
Teacher(s)
prof. RNDr. Mojmír Křetínský, CSc. (lecturer)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
Mgr. Radek Czerný (seminar tutor)
prof. RNDr. Ivana Černá, CSc. (seminar tutor)
Mgr. BcA. Robert Král, Ph.D. (seminar tutor)
Mgr. Pavel Krčál (seminar tutor)
Mgr. Jaroslav Műller (seminar tutor)
Mgr. Miloslav Nepil, Ph.D. (seminar tutor)
doc. Mgr. Jan Obdržálek, PhD. (seminar tutor)
doc. Mgr. Radek Pelánek, Ph.D. (seminar tutor)
RNDr. Jaroslav Ráček, Ph.D. (seminar tutor)
Roman Rožník (seminar tutor)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
Mgr. Radek Sedláček, Ph.D. (seminar tutor)
Mgr. Oldřich Stražovský (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 D1, Wed 15:00–17:50 D1
  • Timetable of Seminar Groups:
I505/NEMOC: No timetable has been entered into IS. M. Křetínský
I505/LF2p: No timetable has been entered into IS. M. Křetínský
I505/LF4p: No timetable has been entered into IS. M. Křetínský
I505/S1: No timetable has been entered into IS. V. Řehák
I505/S2: No timetable has been entered into IS. R. Pelánek
I505/S3: No timetable has been entered into IS. J. Műller
I505/S4: No timetable has been entered into IS. V. Řehák
I505/S5: No timetable has been entered into IS. R. Sedláček
I505/S6_A: No timetable has been entered into IS. I. Černá
I505/S7: No timetable has been entered into IS. P. Krčál
I505/S8: No timetable has been entered into IS. R. Rožník
I505/S9: No timetable has been entered into IS. J. Obdržálek
I505/S10: No timetable has been entered into IS. J. Barnat
I505/S11: No timetable has been entered into IS. J. Ráček
I505/S12: No timetable has been entered into IS. J. Barnat
I505/S13: No timetable has been entered into IS. J. Ráček
I505/S14: No timetable has been entered into IS. M. Nepil
I505/S15: No timetable has been entered into IS. R. Král
I505/S16: No timetable has been entered into IS. R. Czerný
I505/S17: No timetable has been entered into IS. O. Stražovský
I505/S18: No timetable has been entered into IS. O. Stražovský
I505/P1_po: No timetable has been entered into IS. M. Křetínský
I505/P2_Str: No timetable has been entered into IS. M. Křetínský
Prerequisites
I000 Induction and Recursion &&( M005 Foundations of mathematics || M036 Introduction to Discrete Mathematics || PřF:M1500 Algebra I ) && (! I005 Formal Languages and Automata I )
I000 Induction and Recursion and M005 Foundations of mathematics required
Course Enrolment Limitations
The course is also offered to the students of the fields other than those the course is directly associated with.
fields of study / plans the course is directly associated with
Syllabus
  • Languages and grammars. Chomsky hierarchy.
  • Finite automata and regular grammars.
  • Properties of regular languages.
  • Context-free grammars and pushdown automata.
  • Properties of context-free languages.
  • Deterministic pushdown automata.
  • Turing machines. Computable languages and functions.
  • Undecidability, (semi)decidability. Halting problem for TM.
  • Post's correspondence problem. Undecidable CFL problems.
Literature
  • I.Černá, M.Křetínský, A.Kučera: FJA I, interní materiál FI MU
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • HOPCROFT, John E. and Jeffrey D. ULLMAN. Introduction to automata theory, languages, and computation. Reading: Addison-Wesley Publishing Company, 1979, 418 s., ob. ISBN 0-201-02988-X. info
  • 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
Assessment methods (in Czech)
2 písemné zkoušky během semestru a závěrečná písemná zkouška.
Language of instruction
Czech
Follow-Up Courses
Further Comments
The course is taught annually.
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja1.html
The course is also listed under the following terms Spring 2000, Spring 2002.
  • Enrolment Statistics (Spring 2001, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2001/I505