Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Automata Theory (17.0M512)

Native organizations units: Department of Fundamentals Sciences

Type of studies	Title
Master Academic Studies	Mathematics in Engineering (Year: 1, Semester: Winter)

General information:

Category	Theoretical-methodological
Scientific or art field	Teorijska i primenjena matematika
ECTS	5

The main objective of the course is to acquire basic knowledge in automation theory and formal languages, including regular languages, finite automata, formal languages and push-down automata. Students will not only learn these fundamental formal models, but also some well-known applications in various branches of computer science (e.g. construction of compilers, development of programming languages and models for concurrent systems). During the course, the above formal models and techniques for their analysis will be studied through examples and discussion. The ultimate goal is for students to develop skills for setting up formal models and using techniques for analyzing complex systems.

As an outcome of the course, the student will acquire basic knowledge in Theory of Automata and Formal Languages. Additionally, students will master skills for setting up formal methods and analyzing their properties, using known methods from the above fields. Students will learn formal techniques that are used in some areas of computer science (for example, the development of programming languages).

Deterministic finite automaton, definition and examples. Regular languages and regular operations. Nondeterministic finite automaton, definition and examples. Regular expressions and conection with regular languages. Language equivalence on finite automata. Context-free languages. Push-down automata. Conection between push-down automata nad context-free languages.

The presentation of the theoretical part during the lectures is followed by the characteristic examples which contribute to better understanding of the subject matter. The students are expected to individually study the additional literature which they discuss with the . subject teacher at the consultation classes.

Authors	Title	Year	Publisher	Language
Dexter C. Kozen	Automata and Computability	1997	Springer	English
Shawn Hedman	A First Course in Logic	2008	Oxford University Press	English
Sipser, M.	Introduction to the Theory of Computation	2006	Thomson Course Technology, Boston	English
Hopcroft, J.E., Ullman, J.D.	Introduction to automata theory, languges and computation	1979	Adison-Wesley, Reading, Mass.	English

Course activity	Pre-examination	Obligations	Number of points
Test	Yes	Yes	10.00
Theoretical part of the exam	No	Yes	30.00
Test	Yes	Yes	10.00
Exercise attendance	Yes	Yes	5.00
Written part of the exam - tasks and theory	No	Yes	40.00
Lecture attendance	Yes	Yes	5.00