Formal Languages and Machines (INF3, Autumn'07)

Lecturer: Jiri Srba (email: srba@cs.aau.dk, office: 1.2.32)

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, 2nd edition, 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 new Danish scale. Duration of the exam is 20 minutes. The students can choose to hold the exam in either English, Danish or Czech. 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, from 2005 is here, and from 2006 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
4.9.2007 (Tue) 12:30-15:00 0.2.11 Lecture 1 No exercises this time.
6.9.2007 (Thu) 12:30-16:15 0.2.11 Lecture 2 Ex 1.1 and Ex. 1.6 (a. b. g. i. m. n.) Hand-in Ex. 1.6. d.
13.9.2007 (Thu) 12:30-16:15 0.2.13 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.
18.9.2007 (Tue) 12:30-16:15 0.2.11 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)

25.9.2007 (Tue) 12:30-16:15 0.2.12 Lecture 5 Ex. 1.29 a.b., 1.46 d.b.
Hand-in Ex. 1.46 a.
2.10.2007 (Tue) 12:30-16:15 0.2.11 Lecture 6 Ex. 2.1, 2.4, 2.14, 2.10

9.10.2007 (Tue) 12:30-16:15 0.2.12 Lecture 7 Ex. 2.9, 2.17, 2.15, (2.16)
Hand-in Ex. 2.6 d.
23.10.2007 (Tue) 12:30-16:15 0.2.12 Lecture 8 Ex. 2.5 b. e., 2.7 a., 2.2, 2.30 b.

6.11.2007 (Tue) 12:30-16:15 0.2.12 Lecture 9 Ex. 3.2 c.d., 3.1 b., 3.5, 3.8 a., 0*0+1*1

15.11.2007 (Thu) 12:30-16:15 0.2.12 Lecture 10 Ex. 3.7, 3.8 b.c., 3.9, 3.12*, TEST

20.11.2007 (Tue) 12:30-16:15 0.2.12 Lecture 11 Ex. 4.1 a.b.c.e., 4.3, 4.4
Hand-in Ex. 4.11
27.11.2007 (Tue) 12:30-16:15 0.2.11 Lecture 12 Reduce HALTTM to ETM and HALTTM to ATM, Ex. 5.10
Hand-in Ex. 5.9
29.11.2007 (Thu) 12:30-16:15 0.2.11 Lecture 13 TEST, Ex. 5.6, 5.5, 5.7, 5.13
Hand-in Ex. 5.4
4.12.2007 (Tue) 12:30-16:15 0.2.11 Lecture 14 TEST, Ex. 7.1, 7.2, 7.6, 7.14, every reg.lang. is in P

6.12.2007 (Thu) 12:30-16:15 0.2.11 Lecture 15 TEST, Ex. 7.7, 7.15, 7.9

25.1.2007 (Fri) 12:30 - ? 0.2.12 Spørgetime Please, send questions by email 24 hours before the meeting.