Infopaket

Automata and formal languages

ВК.3.02

Вибіркова дисципліна для ОП

First

2022/2023

6 Semester

3

PLO 18.3. Know the mathematical apparatus and principles of programming and be able to apply them in the creation of software systems.

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.

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.

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 ..

Lectures, consultations, independent work

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.

Ukrainian