After successful completion of the course, students are able to classify formal languages relative to the Chomsky hierarchy, develop and adequately manipulate formal grammars, as well as recognize limits of computability. Moreover successful participants have a deeper understanding of basic concepts of classical logic and formal specification, in particular with respect to the syntax/semantics division. They can formalize relatively complex sentences in classical first order logic and can use the tableau calculus to find formal proofs. Finally, they can judge the partial and/or total correctness of simple programs and evaluate the correctness of rules for correctness proofs.
Specification of of formal languages: regular and context free languages (deepening), Chomsky hierarchy, finite automata (deepening), push-down auomata, Turing machines, computability, problem reduction, elements of complexity theory: P, NP; syntax/semantics division, model structures, terms and boolean expressions, syntax and semantics of a simple programming language, classical propositional and first order logic: logical consequence and implication, concep of a logical calculus, semantic tableaux with and without identity, basic properties of first order logic (undecidability, completeness etc.); reasoning about programs: Hoare calculus
The following information is for the (regular) German track of the course only. If you have to get credits for this course to be admitted for a master program in English, please contact Prof. Agata Ciabatoni <agata@logic.at>.
ECTS-Breakdown:
- 40 hours: lecture time
- 60 hours: exercises (homework - 4 blocks)
- 20 hours: four online tests (incl. preparation)
- 30 written examination (incl. preparation)
Total: 150 hours
