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!
What kind of knowledge can you acquire today that will serve for your entire career, that will still be valid in the year 2040? (Hint: concepts that have already survived half a century of CS development.)
Theory extracts the basic concepts that apply to any conceivable implementation of computing machines. These concepts are of timeless validity, in contrast to technology-specific and product-specific know-how.
A firm mastery of basic concepts is a great "data compression technique": many seemingly unrelated facts, presented in time-varying jargon, can be understood intuitively as instances of the same principle.
Additional literature links will also be assembled here if needed, during the semester.
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. Schedule:
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 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