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 20.5.2008 during class (3pm-5pm).
The material for the first test is up to PDA (without them). Second text exam: Thursday 26.6.2008.
Additional exam date(s): Wednesday 2.7.2008 1pm and Tuesday 8.7.2008 3pm. Please notify me by email two days in advance in case you plan to attend these
exams.
Schedule: ! Note the different schedule in the first part of the semester (due to Easter break and travelling) !
Week 1: Tuesday 4.3.2008, 2pm (3pm), first meeting, introduction. Thursday 6.3.2008, 2pm-4pm ( one hour more! ), finite automata, book pages 31-47.
Week 2: Tuesday 11.3.2008, no class . Thursday 13.3.2008, 1pm - 3pm ( one hour more and earlier! ), finite automata, nondeterminism, book pages 47-57. Homework: Fill the missing details
in the proof of equivalence of NFA and DFA (the induction proof that L(M) = L(N) indeed).
Weeks of 18.3, 25.3 and 1.4, no class (Easter break and conference), the classes for the first week of April will be held in the next three weeks, see below.
Week 3: Tuesday 8.4 (usual time), examples of determinization, minimizing DFA, examples, closure under
regular operations, book pages 57-62. Thursday 10.4, 1pm-3pm ( one hour more and earlier! ), closure under regular
operations, examples, regular expressions, equivalence of regular expressions and finite automata (Theorem of Kleene),
book pages 62-73. HW: construct a minimal DFA that recognizes (ba)*(a U b)*aab.
Week 4: Tuesday 15.4 (usual time), equivalence of regular expressions and
finite automata (continued), examples, nonregular languages (discussion and examples), pumping lemma, book pages 73-78.
Thursday 17.4, 1pm-3pm ( one hour more and earlier! ), pumping lemma, examples of proving non-regular languages, book pages
78-82. HW: Show that the language of palindroms is nonregular.
Week 5: Tuesday 22.4 (usual time), nonregularity, more examples and problems from Chapter 1, book pages
82-99, and Thursday 24.4, 1pm-3pm ( one hour more and earlier! ) context-free languages, context-free grammars,
examples, book pages 99-105. HW: Design a grammar for the language L = {uavb | u, v \in {a,b}*, |u| = |v|}.
Week 6: Tuesday 29.4, regular languages are context-free, regular grammars, ambiguity, Chomsky
normal form, book pages 105-108, and Thursday 1.5. no class, holiday. HW: Think about a possible solution to
Problem 2.29 (inherently ambiguous language).
Week 7: Tuesday 6.5, Chomsky normal form (example), pushdown automata, book pages 108-115, Thursday 8.5, no
class (next week two hours on Thursday). HW: Construct a PDA and a grammar for the language
{w \in {a,b}* | #b(w) = 2#a(w)}.
Week 8: Tuesday 13.5, no class, holiday. Thursday 15.5, 1pm-3pm ( one hour more and earlier! ), Equivalence of
pushdown automata and context-free grammars, dicussion about the forthcoming test exam, book pages 115-123.
Week 9: Tuesday 20.5., exam test 1 during class. Thursday 22.5., no class, holiday.
Week 10: Tuesday 27.5., solving the exam problems, more examples. Thursday 29.5., pumping lemma for CF languages, book pages 123-127.
HW: Show that the language {a^i b^j c^k | 0 <= i <= j <= k} is not context free.
Week 11: Tuesday 3.6., properties of context-free languages, deterministic push down automata for
deterministic context-free languages. Thursday 5.6., more examples of (deterministic) push down automata
and grammars. Book pages 127-137. HW: Construct a DPDA for the language L = {a^ib^jc^k | i+k \neq j}.
Week 12: Tuesday 10.6 (usual time), Turing machines, examples. Book pages 137-147. Thursday 12.6, 1pm-3pm ( one hour more and earlier! ) variants of
Turing machines, equivalence. Book pages 148-152.
HW: Construct a Turing machine that recognizes the language of palindromes of odd lenght in alphabet {0,1}.
Week 13: Tuesday 17.6 (usual time), Church-Turing thesis, decidable languages. Book pages: 153-172.
Thursday 19.6, 1pm-3pm ( one hour more and earlier! ), the halting problem. Book pages 173-186.
Week 14: Tuesday 24.6 (usual time), exercises, discussion, questions, examples of exam problems. Thursday 26.6, 12am-3pm ( two hours more and earlier! ) exam test 2.