Formal languages's theory
1000-I1TJF
1. Basic definitions: alphabet, words, languages, free monoid.
2. Regular sets and expressions.
3. Deterministic and nondeterministic finite automata.
4. Minimization of finite automata.
5. Kleene's Theorem.
6. Pumping lemma for regular languages
7. Lexical analysis: the problem of pattern matching, lexers
8. Decision algorithms for regular sets.
9. Grammars. Chomsky hierarchy.
10. Pumping lemma for context-free languages
11. Pushdown automata
12. Engineering applications of programming: parsing algorithms.
13. Decidability and undecidability.
14. Post Correspondence Problem
15. Basic decision problems for context-free languages
Total student workload
lecture - 30 hours
exercises - 30 hours
individual solving tasks assigned by the teacher - 30 hours
exam - 4 hours
individual work (preparation for classes, exercises solving, literature study) - 30 hours
preparation for the exam - 26 hours
TOTAL: 150 hours (6 ECTS credits)
Learning outcomes - knowledge
W1. The student has an orderly, theoretically founded general knowledge of programming, algorithms and complexity, formal languages and automata, programming languages and paradigms (K_W02).
W2. The student knows the basic methods of designing, analyzing and programming algorithms (structural design, recursion, computational complexity) (K_W04).
In particular, he knows:
• Regular expressions and languages,
• Finite automata,
• Grammars,
• Pushdown automata,
• Lexers and parsers,
• Decidable and undecidable decision problems in the theory of formal languages.
Learning outcomes - skills
Student:
U1. Can apply mathematical knowledge to formulate, analyzing and solving tasks related to computer science (K_U01).
U2. Can obtain information from literature, knowledge bases, the Internet and other reliable sources, integrate them, interpret them, and draw conclusions and formulate opinions (K_U02).
U3. Designs, analyzes in terms of correctness and computational complexity and programs algorithms; uses basic algorithmic techniques and data structures (K_U07).
U4. Can assess, at a basic level, the usefulness of routine IT methods and tools, and can select and apply the appropriate method and tools for specific IT tasks (K_U23).
Learning outcomes - social competencies
K1. Creativity: a student thinks creatively in order to improve existing or create new solutions.
K2. Conscientiousness and accuracy: a student is focused on the best execution of the task, takes care of detail, is systematic.
K3. Communication skills: a student effectively communicate his thoughts in a meaningful way, properly uses the professional terminology, is able to make contact within hisarea, and with a person representing a different area.
K4. Efforts made to develop: a student is focused on continually acquiring his knowledge, skills and experience, understands the need for continuous improvement and professional skills development.
K5. Perseverance and consistency: the student is working consistently and has the ability to positive approach to the difficulties standing in the way, keeps appointments.
Observation/demonstration teaching methods
- display
Expository teaching methods
- informative (conventional) lecture
- description
- narration
- discussion
Type of course
core frame (attribute withdrawn)
Prerequisites
Basic knowledge of mathematics and computer science, including set theory (1000-I1LTM), discrete mathematics (1000-I1MAD), theory of algorithms (1000-I1ASD) and programming (1000-I1PPR).
Course coordinators
Term 2023/24L: | Term 2024/25L: | Term 2022/23L: | Term 2025/26L: |
Assessment criteria
Credit with grade on the basis of:
• test results (at least 1) [W1, W2, U1, U3, U4, K1, K2, K3]
• entry tests results [W1, W2, U1, U3, U4, K1, K2, K3, K4, K5]
• results obtained for individual homework solved throughout the semester [W1, W2, U1, U2, U3, U4, K1, K2, K3, K4, K5]
• activity during classes [W1, W2, U1, U3, U4, K1, K2, K3, K4, K5].
Additionally, the final grade consists of:
• regularity
• solving tasks for those willing
• presence.
Acceptable limit of absences from classes - 2 times.
Note: A sick leave must be delivered within 2 weeks of the absence.
Grade for the lecture: written exam [W1, W2, U1, U2, U3, U4, K1, K2, K3, K4, K5].
Bibliography
• J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation
• M. Sipser, Introduction to the theory of computation
• S. Eilenberg, Automata, Languages and Machines
Additional information
Additional information (registration calendar, class conductors,
localization and schedules of classes), might be available in the USOSweb system: