UIIABP0046 Theory of languages and automata I

Faculty of Philosophy and Science in Opava
Summer 2021
Extent and Intensity
2/2/0. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
doc. RNDr. Lucie Ciencialová, Ph.D. (lecturer)
doc. RNDr. Lucie Ciencialová, Ph.D. (seminar tutor)
Mgr. Ondřej Mazurek (seminar tutor)
Guaranteed by
doc. RNDr. Lucie Ciencialová, Ph.D.
Institute of Computer Science – Faculty of Philosophy and Science in Opava
Timetable
Tue 8:05–9:40 B2
  • Timetable of Seminar Groups:
UIIABP0046/A: Thu 13:55–15:30 B3a, O. Mazurek
Prerequisites (in Czech)
TYP_STUDIA(B)
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
Course objectives (in Czech)
V tomto kurzu se zabýváme především teoretickými základy metod používaných pro modelování struktur a postupů, tedy konečnými automaty, regulárními jazyky, regulárními výrazy a bezkontextovými gramatikami. Na teoretický základ navazují také příklady využití v praxi. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášek.
Syllabus (in Czech)
  • 1. Abeceda, formální jazyky, operace s formálními jazyky.
  • 2. Regulární jazyky, regulární výrazy.
  • 3. Konečné automaty.
  • 4. Uzávěrové vlastnosti regulárních jazyků.
  • 5. Chomského hierarchie jazyků.
  • 6. Regulární gramatiky a jejich vztah ke konečným automatům.
  • 7. Bezkontextové gramatiky, jejich varianty a vlastnosti.
  • 8. Zásobníkové automaty.
Literature
    required literature
  • VAVREČKOVÁ, Šárka. Teorie jazyků a automatů I. Opava: Slezská univerzita v Opavě, 2017. info
  • CIENCIALOVÁ, Lucie. Teoretické základy informatiky. Opava: Slezská univerzita v Opavě, 2014. ISBN 978-80-7510-130-3. info
    recommended literature
  • LINZ, Peter. An introduction to formal languages and automata. Sixth edition. Burlington, MA: Jones, 2017. ISBN 978-1-284-07724-7. info
  • HOPCROFT, JOHN E, Rajeev MOTWANI and JEFFREY D ULLMAN. Introduction to automata theory, languages, and computation. Harlow: Pearson Addison-Wesley, 2014. ISBN 978-1-292-03905-3. info
  • MEDUNA, Alexander and Petr ZEMEK. Regulated grammars and automata. New York: Springer, 2014. ISBN 978-1-4939-0368-9. info
  • ČERNÁ, I, M KŘETÍNSKÝ and A KUČERA. Automaty a formální jazyky I. Brno: FI MU, 2002. info
  • MEDUNA, A. Automata and Languages: Theory and Applications. Springer, London, 2000. info
Teaching methods
Lecture, tutorial
Assessment methods (in Czech)
Zápočet: dvě písemky, účast na cvičeních min. 75 %.
Zkouška: písemná a ústní část, seznam možných otázek na webu vyučujícího.
Language of instruction
Czech
The course is also listed under the following terms Summer 2022, Summer 2023, Summer 2024, Summer 2025.
  • Enrolment Statistics (Summer 2021, recent)
  • Permalink: https://is.slu.cz/course/fpf/summer2021/UIIABP0046