Formal Languages and Computability (INF3, Autumn'05)

Lecturer: Jiri Srba (email: srba@cs.aau.dk, office: B2-203)

Course Description: The aim of this course is to introduce the main models and results in the theory of computation, with focus on those for the description of the syntax and semantics of formal languages, and associated algorithmic aspects. The course covers, amongst others, finite automata, regular languages, context-free grammars and languages, Turing machines, Church-Turing thesis, basic (un)decidability results, the complexity classes P and NP, NP-completeness, reductions. The working language of the course will be English.

Textbook: The main textbook will be Introduction to the Theory of Computation by Michael Sipser. The book is available at the local bookstore. Make sure you get the Second International Edition, ISBN 0-619-21764-2. There is an updated list of errata here.

Lectures and Exercises: The course will run in four-hour blocks. Each block will consist of combined activities: lecturing and supervised solving of exercises. These two activities can be interleaved several times during one block. Each week a list of exercises will be released. Students are supposed to prepare for the exercises by reading corresponding text from the textbook. Occasionally, some of the exercises will be marked as hand-in. Students are expected to solve them individually and the solutions will be corrected by the lecturer. Solutions of the exercises will be explained and discussed during the tutorials. The students are highly encouradged to take their own notes, both from the lectures and from the tutorials.

Exam: Individual and oral with preparation time. Marks will be given according to the standard scale 00 - 13. Duration of the exam is 20 minutes. The students can choose to hold the exam in either English, Danish or Czech. Final list of exam questions:
  1. Finite automata: deterministic, nondeterministic finite automata and their equivalence, closure properties.
  2. Regular expressions and their connection with finite automata.
  3. The Pumping Lemma for regular languages and its applications.
  4. Context-free grammars and pushdown automata, closure properties of context-free languages.
  5. Turing machine and its variants, Church-Turing Thesis, decidable and recognizable languages (definitions and closure properties).
  6. The undecidability of ATM and HALTTM.
  7. Reductions in the computability theory (computable functions, mapping reducibility and its properties and use in undecidability proofs).
  8. The complexity class P: definition, examples, polynomial-time equivalence of deterministic models and closure properties.
  9. The complexity class NP: definition, examples, the concept of polynomial time reduction and NP-completeness.
Syllabus: Course web-page from the year 2004 is here.

Anonymous Feedback Form (can be accessed only from the domain cs.aau.dk)
(The students are very encouraged to notify the lecturer about any problem as soon as possible and to send suggestions for improvements. Positive feedback is also welcome.)

Lecture Plan (calendar is available here):

Before the first lecture the students are asked to read Chapter 0 of the main textbook in order to refresh their knowledge from the discrete mathematics course and solve the exercises: 0.2, 0.3, 0.4, 0.5, 0.7, 0.10 and 0.11. This will be essential for a smooth start of the course. Any potential problems/questions will be answered during the first lecture.

Date
 Time
 Place
 Link
 Exercises
 Remark
5.9.2005 (Mon) 14:30-16:15 C3-204 Lecture 1 No exercises this time.
12.9.2005 (Mon) 12:30-16:15 C3-204 Lecture 2 Ex 1.1 and Ex. 1.6 (a. b. g. i. m. n.) Hand-in Ex. 1.6. d.
19.9.2005 (Mon) 12:30-16:15 NJ6A-1.44 Lecture 3 Ex. 1.4 b., 1.5 g., 1.7 b.c., 1.16, 1.11, (1.14)
Hand-in Ex. 1.17 a. b.
22.9.2005 (Thu) 12:30-16:15 KS03-4.128 Lecture 4 Ex. 1.7.e., 1.19 a.b.c.g., 1.20 a.b.d.j., 1.18 b., 1.21 b., (1.23)

26.9.2005 (Mon) 12:30-16:15 NJ6A-1.44 Lecture 5 Ex. 1.29 a.b., 1.46 d.b.
Hand-in Ex. 1.46 a.
3.10.2005 (Mon) 12:30-16:15 C3-204 Lecture 6 Ex. 2.1, 2.4, 2.14, 2.10

6.10.2005 (Thu) 12:30-16:15 KS03-2.132 Lecture 7 Ex. 2.9, 2.17, 2.15, (2.16)
Hand-in Ex. 2.6 d.
10.10.2005 (Mon) 12:30-16:15 KS03-2.132 Lecture 8 Ex. 2.5 b. e., 2.7 a., 2.2, 2.30 b.

26.10.2005 (Wed) 8:15-12:00 B2-104 Lecture 9 Ex. 3.2 c.d., 3.1 b., 3.5, 3.8 a., 0*0+1*1

31.10.2005 (Mon) 12:30-16:15 NJ14 4-117 Lecture 10 Ex. 3.7, 3.8 b.c., 3.9, 3.12*, TEST

3.11.2005 (Thu) 12:30-16:15 C2-209 Lecture 11 Ex. 4.1 a.b.c.e., 4.3, 4.4
Hand-in Ex. 4.11
7.11.2005 (Mon) 12:30-16:15 KS03-2.132 Lecture 12 Reduce HALTTM to ETM and HALTTM to ATM, Ex. 5.10
Hand-in Ex. 5.9
14.11.2005 (Mon) 12:30-16:15 KS03-3.115 Lecture 13 TEST, Ex. 5.6, 5.5, 5.7, 5.13
Hand-in Ex. 5.4
17.11.2005 (Thu) 12:30-16:15 B2-109 Lecture 14 TEST, Ex. 7.1, 7.2, 7.6, 7.14, every reg.lang. is in P

21.11.2005 (Mon) 12:30-16:15 B2-109 Lecture 15 TEST, Ex. 7.7, 7.15, 7.9

19.1.2006 (Thu) 15:00-? A5-006 Spørgetime Questions should be sent by email 24 hours before the meeting