Automata and formal languages

Course: Informatics

Structural unit: Faculty of Computer Science and Cybernetics

Title
Automata and formal languages
Code
ВК.3.02
Module type
Вибіркова дисципліна для ОП
Educational cycle
First
Year of study when the component is delivered
2022/2023
Semester/trimester when the component is delivered
6 Semester
Number of ECTS credits allocated
3
Learning outcomes
PLO 18.3. Know the mathematical apparatus and principles of programming and be able to apply them in the creation of software systems.
Form of study
Prerequisites and co-requisites
1. Know the basic concepts in the field of set theory, graph theory, Boolean functions; basic concepts, means and methods of the theory of algorithms; main formal models of algorithms; basic unsolvable algorithmic problems. 2. Be able to perform combinatorial calculations; build formal models of algorithms (Turing machines). 3. To have basic skills of using logico-mathematical symbols and programming in high-level programming languages.
Course content
The discipline considers algorithmic devices, formal languages, and the complexity of algorithms. During the course of study, students should deepen their knowledge of the apparatus of finite automata and regular expressions, learn to use regular expressions in practical tasks, gain in-depth knowledge of the theory of context-free languages, syntactic analysis and the complexity of algorithms. The acquired knowledge will allow you to effectively work with regular expressions and finite automata; understand the problems associated with NP-completeness and the limits of the practical applicability of the theory of regular and context-free languages. It is taught in the 6th semester of the 3rd course in the amount of 90 hours. (3 ECTS credits), in particular: lectures – 42 hours, consultations – 2 hours, independent work – 46 hours.
Recommended or required reading and other learning resources/tools
Osnovnі: 1. Hopcroft J. Introduction to automata theory, languages and computation / J. Hopcroft, J. Ullman. – Addison-Wesley publishing company, 1979. https://www.dropbox.com/sh/vznral3awh628f4/AACKTD-dYcsIF9z8jPQaOtsOa?dl=0 2. Osnovi diskretnoї matematiki: pіdruch. [dlia stud. vishch. navch. zakl.] / Iu. V. Kapіtonova [ta іn.]. – K.: Naukova dumka, 2002. 3. Vardi, M.Y. Nontraditional applications of automata theory. / M.Y. Vardi [Internet] 4. Biukhi, D.R. Slabaia arifmetika vtorogo poriadka i konechnye avtomaty. // Kiberneticheskii sbornik. – 1964. – Vip. 8. – S.42-77. 5. Lisovik, L.P. Algoritmicheskie voprosy dlia real-nykh funktsii // Kibernetika .– 1987.– #1. – S.12-17. 6. Jena, S.R. Theory of computation and application. / S.R.Jena, S.K.Swain .– 2nd ed. – New Delhi: Laxmi Publications, 2020.– URL:https://www.researchgate.net/publication/337840420_Theory_of_Computation_and_Application-_2nd_Edition_Automata_Formal_Languages_Computational_Complexity-_SR_Jena_SK_Swain ..
Planned learning activities and teaching methods
Lectures, consultations, independent work
Assessment methods and criteria
1. Control work 1: РН1.1, РН2.3 – 20 points/10 points. 2. Control work 2: РН1.1, РН1.2, РН1.3, РН2.3 – 20 points/10 points. 3. Practical task: PH1.1, PH1.2, PH2.1, PH2.2 – 60 points/36 points.
Language of instruction
Ukrainian

Lecturers

This discipline is taught by the following teachers

Departments

The following departments are involved in teaching the above discipline