IB005 Formal Languages and Automata I

Faculty of Informatics
Spring 2003
Extent and Intensity
2/2. 4 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. Ivana Černá, CSc. (deputy)
prof. RNDr. Ivana Černá, CSc. (seminar tutor)
prof. RNDr. Jiří Barnat, Ph.D. (seminar tutor)
doc. RNDr. Tomáš Brázdil, Ph.D. (seminar tutor)
Mgr. Jan Holeček (seminar tutor)
Mgr. Pavel Moravec (seminar tutor)
doc. Mgr. Radek Pelánek, Ph.D. (seminar tutor)
Roman Rožník (seminar tutor)
doc. RNDr. Vojtěch Řehák, Ph.D. (seminar tutor)
Mgr. Oldřich Stražovský (seminar tutor)
RNDr. Pavel Šimeček, 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 of Seminar Groups
IB005/01: Thu 13:00–14:50 B003, J. Barnat
IB005/02: Thu 15:00–16:50 B003, J. Barnat
IB005/03: Thu 13:00–14:50 B007, V. Řehák
IB005/04: Wed 9:00–10:50 B204, V. Řehák
IB005/05: Thu 9:00–10:50 B011, R. Rožník
IB005/06: Thu 11:00–12:50 B011, R. Rožník
IB005/07: Thu 13:00–14:50 B011, O. Stražovský
IB005/08: Fri 8:00–9:50 B204, R. Pelánek
IB005/09: Thu 9:00–10:50 B003, P. Moravec
IB005/10: Thu 15:00–16:50 B007, T. Brázdil
IB005/11: Thu 11:00–12:50 B007, J. Holeček
IB005/12: Thu 9:00–10:50 B007, P. Šimeček
IB005/A: Thu 11:00–12:50 B003, I. Černá
IB005/St: Wed 13:00–15:50 D1, M. Křetínský
Prerequisites (in Czech)
! I005 Formal Languages and Automata I &&! I505 Formal Languages and Automata I && ( MB005 Foundations of mathematics || M005 Foundations of mathematics )&& ! IB102 Automata and Grammars
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
Course objectives
The purpose of this course is twofold: to introduce computer science students to the rich heritage of models and abstractions that have arisen over the years, and to develop the capacity to form abstractions of their own and reason in terms of them.
Syllabus
  • Languages and grammars. Chomsky hierarchy.
  • Finite automata and regular grammars.
  • Properties of regular languages. Applications.
  • Context-free grammars and pushdown automata.
  • Properties of context-free languages.
  • Turing machines. Computable languages and functions, LBA. Properties of recursive and recursive enumerable languages.
  • Deterministic pushdown automata. Properties and applications.
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
  • 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.
Listed among pre-requisites of other courses
Teacher's information
http://www.fi.muni.cz/usr/kretinsky/fja1.html
The course is also listed under the following terms Spring 2004, Spring 2005, Spring 2006, Spring 2007, Spring 2008, Spring 2009, Spring 2010, Spring 2011, Spring 2012, Spring 2013, Spring 2014, Spring 2015, Spring 2016, Spring 2017, Spring 2018, Spring 2019, Spring 2020, Spring 2021, Spring 2022, Spring 2023, Spring 2024, Spring 2025.
  • Enrolment Statistics (Spring 2003, recent)
  • Permalink: https://is.muni.cz/course/fi/spring2003/IB005