Formal Languages and Formal Grammars (Part II)


Within the first part of the course, we introduced some of the basic notopns, e.g, finite state machines, push down machines, and formal grammars, and their relationships to formal languages. Within this part we will introduce the Turing Maschine in various ways and see that all of them turn to be equivallant. While the first part of the course was dedicated to the theoretical aparatus needed for constracting sintactically correct programs, the second part will introduce the semantical meaning of a program. In particular, we will introduce a mapping between program texts and computable functions.

There are no special prerequisites in terms of specific courses to attend. Students who have not attended the first part of the course may also attend this part -- when necessary, we will have some additional excersises in order to fill gaps. Students are expected to be familiar with the basic notions of mathematics and with basic proof techniques, as taught in the mathematics courses of the first year.


Winter Semester 2015.


Please register for the course via the KUSSS system.

Course Materials

Maintained by Nikolaj Popov