Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Theory of formal languages (17.DOM44L)

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

General information:

Category	Scientific-professional
Scientific or art field	Applied Computer Science and Informatics Teorijska i primenjena matematika
ECTS	10

The objective of the course is to acquire knowledge and get acquainted with basic results from the theory of formal languages. The doctoral students will train the skills of developing formal models and analyzing their properties using known methods and results from the field. The ultimate goal is for students to master the formal techniques used in the development of programming languages, and finally to enable them to actively engage in research groups working in specific fields that apply the theory of formal languages.

Doctoral students will have fundamental knowledge about basic notions and results in formal languages theory. In addition, doctoral students will master the skill of developing formal models and analysing their properties, using known methods from the field. Students will learn formal techniques used in the development of programming languages. Young researchers will be involved in research in specific fields that apply the theory of formal languages, at the student's choice, in collaboration with other researchers.

Formal grammars. Presentation of formal languages. Chomsky hierarchy. Regular languages, regular expressions and finite automata. Context free languages and push-down automata. Context sensitive languages. Type 0 grammar. Computabilty and grammar. Application of formal grammar in programming languages. Automata over infinite words and aplication in verification.

The presentation of the theoretical part is followed by the corresponding examples which contribute to better understanding of the theoretical part. The students are expected to individually study the additional literature and discuss it with the subject teacher at the consultation classes. Through research and study work the student will, on the bases of scientific journals and other relevant literature that has been studied independently, develop further understanding of the material covered in lectures. Working with the course teacher the student develops the ability to independently work on a scientific paper.

Authors	Title	Year	Publisher	Language
A. Aho, R. Sethi, J. Ullman	Compilers, principles, techniques, and tools	1986	Addison-Wesley	English
J.Hopcroft, J.Ullman	Formal languages and their relation to automata	1969	Addison-Wesley	English
H. Lewis, C. Papadimitriou	Elements of the theory of computation	1981	Prentice-Hall	English