Information on the course

Automata, Language Theory and Complexity (2ITS90)

This is the information about the 5ects course Automata, Language Theory and Complexity 2ITS90, for the premaster program and homologation for the master Computer Science and Engineering.

The responsible lecturer is prof dr H. Zantema, Metaforum 6.078, tel 2749, h.zantema@tue.nl

The format:
The format of the course is mainly self study.
No regular lectures are given, only once a week there will be an online meeting where you may ask questions and some highlights will be presented.
These meetings are on Wednesday, 10:00 AM, starting on November 11, on Canvas Conference. The topics of these meetings will follow the week scheme below.

The material consists of the sections indicated below of the following book.

J.E. Hopcroft, R. Motwani and J.D. Ullman
Introduction to Automata Theory, Languages and Computation
Addison Wesley, Third edition, 2007.

An online series of 26 lectures on these topics by Jeffrey Ullman (one of the authors of the book) is available here at Youtube.

Answers of the exercises in the book marked by '*' are given here. Elaborations of some other exercises, representative to what you may expect for the examination, are given in Canvas, at Files.

Content:
The material of this course consists of the following sections of the book, to be divided over the 7 weeks of the course as follows:

Week 1:
2.2 DFAs
2.3 NFAs
2.5 epsilon-NFAs
3.1 Regular expressions
Week 2:
3.2 Finite automata and regular expressions
4.1 Pumping lemma for regular languages
4.2 Closure properties of regular languages
4.3 Decision properties of regular languages
Week 3:
5.1 Context free grammars
5.2 Parse trees
5.4 Ambiguity
Week 4:
6.1 PDA
6.2 Language of a PDA
6.3 Equivalence of PDA and CFG
Week 5:
7.1 Normal forms of CFG
7.2 Pumping lemma for CF languages
7.3 Closure properties of CF languages
Week 6:
8.2 Turing machines
9.1 A language that is not recursively enumerable
Week 7:
10.1 Classes P and NP
10.2 SAT is NP complete

Suggested exercises: (to be updated every week, videos of many solutions are found in Canvas Files)
week 1: 2.2.4, 2.2.5, 2.2.7 (page 53/54), 2.3.1 (page 65)
week 2: 3.2.1, 3.2.4 (page 107/108), 4.1.1 (page 131), 4.2.13 (page 149)
week 3: 5.1.1a, 5.1.2, 5.1.3 (page 182), 5.2.1 (page 193), 5.4.1 (page 215)
week 4: 6.2.1c, 6.2.2b (page 241), 6.3.2 (page 251)
week 5: 7.1.1 (page 275), 7.2.1 (page 286), 7.3.2 (page 297)
week 6: 8.2.1ab, 8.2.2ab (page 335,336)
week 7: 10.1.6a (page 437), 10.2.1 (page 447)

Assessment:
There will be a final exam only. The resulting grade will also be the final grade for the course.

Here you find a test examination.

Last change: January 6, 2021