Theory of Computation, Winter semester 2010/11

Department of Computer Sciences, University of Salzburg

Lecturer:      Dr. A. Sokolova, ana.sokolova"at", office 2.17 (together with Prof. C.M. Kirsch)

Schedule:      Tuesdays 2pm-5pm, in T06

First meeting:     Tuesday, 5.10.2010, at 2pm, in T06

Language:      English

The course may also be taken by PhD students

Course description: We will cover elements from the theory of computation, in a detail appropriate to a master course. In particular we will introduce different models of computation (in an increasing order of expressivity). In short, the topics are: finite automata, regular languages, pumping lemma for regular languages, context free grammars, push-down automata, cf languages, pumping lemma for cf-languages, Turing machines, undecidability. Our focus will be on the expressivity of the different models of computation (classification of languages, pumping lemmas) and on Turing machines as the most expressive model. To this end, we will study the boundaries of computation and show undecidability results.

I quote an ETH-Zurich course announcement for a similair course:

Why a theory of computation? Nothing is more practical than a good theory! (end of quote)

Prerequisites: None. Knowledge of basics of theoretical computer science is an asset. The course is somewhat complementary to the course "Theoretische Informatik" which mainly focuses on recursive functions as a model of computation. We will focus on automata and Turing machines instead.

Exam: This is a VP course. There will be two tests during the semester, and an additional exam at the end of the semester. The exam is written consisting of several excersises from the material covered during the course. Additionally, there will be homeworks, which will also contribute to the final grade. First text exam: Tuesday 21.12.2010 during class (2pm-5pm). The material for the first test is up to PDA (without them). Second text exam: Thursday 3.2.2011 in T06 (1pm-4pm).

Additional exam date(s):t.b.a.

  • Week 1: Tuesday 5.10.20, first meeting, introduction.
  • Week 2: Tuesday 12.10.2010, finite automata.
  • Week 3: Tuesday 19.10.2010, nondeterminism. (Due to holidays no class on 26.10.2010 and 2.11.2010.)
  • Week 4: Tuesday 9.11.2010, closure properties, regular expressions, equivalence of regular expressions and finite automata (Theorem of Kleene).
  • Week 5: Tuesday 16.11.2010, Kleene's theorem (continued), non-regular languages.
  • Week 6: Tuesday 23.11.2010, non-regular languages, examples, context-free languages.
  • Week 7: Tuesday 30.11.2010, context-free grammars, regular grammars.
  • Week 8: Tuesday 7.12.2010, push-down automata.
  • Week 9: Tuesday 14.12.2010, discussion, questions and answers, example exam problems.
  • Week 10: Tuesday 21.12.2010, exam test 1 during class. (Due to Christmas break no classes on 28.12.2010 and 4.1.2011)
  • Week 11: Tuesday 11.1.2011, properties of context-free languages, deterministic push-down automata.
  • Week 12: Tuesday 18.1.2011, Turing machines.
  • Week 13: Tuesday 25.1.2011, Church-Turing thesis, decidable/undecidable languages.
  • Week 14: Tuesday 1.2.2011, 1pm-3pm, extra class: exercises, discussion, questions, examples of exam problems. Thursday 3.2.2011, 1pm-4pm exam test 2.
    Results from the exam(s) and homeworks

    Student ID Exam test 1 points (<= 100) Exam test 2 points (<= 100) Full exam points (if no tests) (<= 100) HW points Total (mark)
    ****949 99 82 - 9 1
    ****281 87 82 - 9 1
    ****168 53 82 - 8 2
    ****510 44 63 - 5 3