Formal Languages and Formal Grammars


RISC-Linz logo 


Short Description


In this course we introduce and study the basic abstract models of computation, namely finite state machines, push down machines, and formal grammars, and their relationships to formal languages. It is also discussed how the abstract computing devices are used to process languages, and hence to solve problems that are of practical relevance. The notion of a formal grammar arises from the need to formalize the informal notions of grammar and language. Many formal grammars were invented and they can be ordered in a natural hierarchy.


There are no special prerequisites in terms of specific courses to attend. 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.




Summer Semester 2008 – 2009.

·             Number: 326.00E

·             Title: Formal Languages and Formal Grammars

·             Lecturer: Nikolaj Popov

·             Time: Thursday, 14:30 – 16:00 

·             Place: T-112

·             Language: English

·             First lecture: March 12


Please register for the course via the KUSSS system.


·             Basic notions: sets, relations, functions, groups, semigroups, fields, Kleene algebras, etc. (Only introduction.)

·             Basic principles and notions in Combinatorics. (Only introduction.)

·             Graphs and multigraphs.

·             Regular Languages and Finite Automata.

·             Context Free Languages and Pushdown Automata.

·             Turing Machines. Church-Turing thesis.

·             Hierarchy of Languages and Automata.

·             Decidable and Undecidable problems.





Maintainer: Nikolaj Popov

 [RISC-Linz] [University] [Search]