| Course title | Formal Languages and Automata |
|---|---|
| Course code | KMI/FJ |
| Organizational form of instruction | Lecture + Exercise |
| Level of course | Bachelor |
| Year of study | not specified |
| Semester | Summer |
| Number of ECTS credits | 6 |
| Language of instruction | Czech |
| Status of course | Compulsory, Compulsory-optional |
| Form of instruction | Face-to-face |
| Work placements | This is not an internship |
| Recommended optional programme components | None |
| Lecturer(s) |
|---|
|
| Course content |
|
Basic notions: formal language, hierarchy of grammars and languages. Finite automata: deterministic and nondeterministic finite automata, their extension, mutual relationship, and applications. Regular grammars and languages: relationship to finite automata, closure properties of regular languages, criteria of regularity, minimization of automata. Regular expressions and their applications: standard and extended regular expressions, application for text processing, selected topics. Context-free languages: definition and properties, derivation trees, properties of context-free languages and their relationship to regular languages Pushdown automata: variants, relationship to context-free languages, top-down syntactic analysis, bottom-up syntactic analysis, deterministic pushdown automata.
|
| Learning activities and teaching methods |
Lecture, Demonstration
|
| Learning outcomes |
|
The students become familiar with basic concepts of formal languages.
1. Knowledge Describe basic generative and analytical formalisms for languages. |
| Prerequisites |
|
unspecified
|
| Assessment methods and criteria |
|
Oral exam, Written exam
Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam. |
| Recommended literature |
|
| Study plans that include the course |
| Faculty | Study plan (Version) | Category of Branch/Specialization | Recommended semester | |
|---|---|---|---|---|
| Faculty: Faculty of Science | Study plan (Version): Bioinformatics (2021) | Category: Informatics courses | 2 | Recommended year of study:2, Recommended semester: Summer |
| Faculty: Faculty of Science | Study plan (Version): Mathematics (2026) | Category: Mathematics courses | 1 | Recommended year of study:1, Recommended semester: Summer |
| Faculty: Faculty of Science | Study plan (Version): Computer Science for Education (2024) | Category: Informatics courses | 2 | Recommended year of study:2, Recommended semester: Summer |
| Faculty: Faculty of Science | Study plan (Version): Computer Science (2020) | Category: Informatics courses | 2 | Recommended year of study:2, Recommended semester: Summer |
| Faculty: Faculty of Science | Study plan (Version): Computer Science - Specialization in Programming and Software Development (2021) | Category: Informatics courses | 2 | Recommended year of study:2, Recommended semester: Summer |
| Faculty: Faculty of Science | Study plan (Version): Computer Science - Specialization in General Computer Science (2021) | Category: Informatics courses | 2 | Recommended year of study:2, Recommended semester: Summer |