Formal Languages and Automata Theory
Public syllabus for 2025-2026
Academic overview
Teaching team
Learning time distribution
| Total | ||||||
|---|---|---|---|---|---|---|
| Curriculum | Lecture | Practice | Total Weekly | Lecture | Practice | |
| 56 | 28 | 28 | 4 | 2 | 2 | |
| Exam hours | ||||||
| 2 | ||||||
| Individual Study | Bibliography study | Field study | Homework | Tutoring | Others | |
| 67 | 14 | 23 | 28 | 2 | 0 | |
| Overall | ||||||
| 125 |
Learning outcomes
Knowledge
- Acquiring the fundamental concepts and results regarding formal languages (especially those of type 2 and 3), grammars, finite automata, regular expressions, and pushdown automata
- Knowledge of the fundamental algorithms for syntactic analysis and translation to intermediate code
Skills
- Knowledge objectives: (1) Identify different formal language classes and their relationships (2) Design grammars and recognizers for different formal languages
- Habilitation objectives: (1) Prove or disprove theorems in automata theory using its properties (2) Determine the decidability and intractability of computational problems
- Attitudinal objectives: (1) to argue the importance of formal languages, automata, decidability results to an IT specialist.
Responsibility
(none)
Online platform
Course content
| Content | Methods | Obs |
|---|---|---|
| C1-2 (4 hours): Course overview. Formal languages and grammars. The Chomsky hierarchy | Lecture (beamer) | Lecture materials will be made available on Google Classroom |
| C3. Closure properties of languages | Lecture (beamer) | Same as above |
| C4. Nondeterministic and deterministic automata | same as above | Same as above |
| C5. Finite automata and regular languages | same as above | Same as above |
| C6. Algebraic characterisation of regular languages | same as above | Same as above |
| C7. Properties of regular languages | same as above | Same as above |
| C8. ε-NFA and regular expressions | same as above | Same as above |
| C9. Context-free grammars and derivation trees | same as above | Same as above |
| C10. Decidability for context-free grammars. Recursive grammars | same as above | Same as above |
| C11. Normal forms for context-free grammars | same as above | Same as above |
| C12. Pushdown automata | same as above | Same as above |
| C13.Context-sensitive and type-0 languages. Turing machines. Undecidability | same as above | Same as above |
| C14. (2h) Course & Finals Review | same as above | All the bibliographic material listed below |
Course bibliography
[1] JE Hopcroft, R Motwani and JD Ullman. Introduction to automata theory, languages and computation Addison Wesley/Pearson; 3rd Edition [2] Dexter C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science). Springer 1997
Seminar content
| Content | Methods | Obs |
|---|---|---|
| S1. Exercises related to lectures 1-2 | Questioning, dialogue, collaborative learning | |
| S2. Exercises related to lectures 3-4 | Same as above | The homework will be posted after each lecture. Students have to do it in teams until the next seminar. At the next seminar, students will be nominated for a presentation. |
| S3. Exercises related to lectures 5-6 | Same as above | Same as above |
| S4. Exercises related to lectures 7-8 | Same as above | Same as above |
| S5. Exercises related to lectures 9-10 | Same as above | Same as above |
| S6. Exercises related to lectures 11-12 | Same as above | Same as above |
| S7. Exercises related to lectures 13. Recap & final review | Same as above | Same as above |
| Bibliography: |
Seminar bibliography
The content of the lecture is consistent with one of similar courses from other universities. It covers the fundamental aspects necessary for the familiarity with issues of formal languages and automata. The content is not very useful for ordinary IT companies, but students can train their algorithmic thinking and improve their skills of problem solving, tasks which are indispensable for a programmer.
Corroboration
(none)
AI tools guidance
Evaluation and delivery
| Activity | Criteria | Methods | Percentage |
|---|---|---|---|
| C |
|
|
|
| S |
|
|
|
Performance standards
Minimal knowledge for passing (grade 5): Acquiring fundamental understanding of the knowledge of automata theory and formal languages. The final grade is computed as a weighted average of the grades given at the written exam (session A) and at the seminars. Each has to be passed with at least 5. The attendance requirements are in accordance with the Code of rights and obligations of students and the Regulation of the activity of UVT’s students. Students who do not pass session A will have the opportunity to take only the written – there is no way to improve the grade for seminar activity. Same holds for those who want to improve their grade. Note: Students may attend office hours (2 modules / week according to the schedule set out at the beginning of the semester) where the lecturer (course/seminar) answers questions from students and provides further explanations related to course content, applications from seminar themes.
Additional info
(none)