Automata and Formal Languages 2009/10

News | Dates | Grading | Content | Exercises | Exam | Material

21th February 2010:

You may look into your exams this Wednesday and Thursday at 2pm.

19th February 2010:

If you want to know your mark, feel free to send me an email to jan.kretinsky ``at'' in.tum.de with a subject ``AFL mark''. You will also be given a chance to have a look into your exam (probably next week, precise time will be announced shortly).

18th February 2010:

Your exams have been corrected and the results will be announced shortly. Due to Exercise 2 (b), the grading has been shifted by 1 point in your favour. The grade distribution is now almost uniform.

9th February 2010:

reminder: just as last year the exam will be open book, that is, you can bring all kinds of notes or books with you (but no computer).

1st February 2010:

The lecture on Feb 3 is cancelled.
The exercises on Feb 11 will be devoted to discussing your questions and older exams. There will be no Homework 13 released.

14th January 2010:

Under "Material" there is now a link to the chapters on automata on infinite words..

12th January 2010:

The lecture on 18th January and the exercises on 21st January are swapped.

22nd December 2009:

The programming project is definitively cancelled due to illness of the teaching assistant. The grade will be determined according to the written exam only.

18th December 2009:

Yesterday in the problem class I showed how to use BDDs to compute the set of reachable states of a toy program. I've been asked to post the program and the DDcal file here. The program is

0: x:= (x + y) mod 2;
1: y:= 0;
2: end

So the program has three control locations, 0,1,2, which can be encoded with two bits pc0, pc1, (pc0 is the least significant bit) and two variables with range 0,1, modelled by two further bits, also called x,y. A state of the program is modelled as a valuation of pc0,pc1,x,y. A transition of the program is modelled as a valuation of pc0,pc1,x,y,npc0,npc1,nx,nx, were the "nXX" bits correspond to the values of the program counter and of the variables after the transition is executed.

The DDcal file is here. The transitions of the program are modelled by the boolean function TR. The set of initial states is IN = pc0' * pc1' * x, i.e., the set of all states in which control is at location 0, x has value 1, and y has an arbitrary value.

Enjoy.

1st December 2009:

Tomorrow (Dec 2) the lecture is cancelled due to Dies Academicus.

Next week, the lecture is moved from Wednesday (Dec 9) to Thursday (Dec 10) and the exercises are cancelled.

25. November 2009:

From Javier Esparza: Sorry again ... We have to cancel the lecture tomorrow, because I have to be examiner of a PhD thesis. Tomorrow Jan Kretinsky will again discuss exercises. In particular, he'll show how to construct an automaton accepting all numbers divisible by 3.

22. November 2009:

Professor Esparza has to go on Monday, November 23, on a trip. On Monday Jan Kretinsky will discuss exercises, and the lecture will be on Wednesday. We apologize for this sudden change.

13. November 2009:

A solution for the exercises discussing the syntactic monoind can be found here.

9. November 2009:

Some short announcements:

• As Professor Esparza is on a trip on Wednesday, the 9th of December, lecture and exercise swap time and place in that week.
• As we didn't discuss all exercises of sheet 2 last time, we are going to rearrange the exercises as follows:
  • Ex. 2.3, 3.1 and 3.2 are discussed on 12.11.
  • Ex. 3.3, 3.4, 4.1 and 4.2 are discussed on 19.11.
  • Ex. 2.2 is postponed until transducers have been introduced in the lecture.

30. October 2009:

Please note:

• The room for the exercises has changed. The exercises will take place in 02.13.010 from now on.
• The lecture on Monday, 01.11.09 is canceled.
• As the first exercise has been canceled, a version of exercise sheet 1 including solutions/proof sketches has been uploaded (see exercises).

28. October 2009:

• We are still looking for an adequate room for the lecture this Thursday. For now, we will meet in 03.09.014 at 16:00.
• A new version of the exercise sheet 2 has been uploaded as some of you might already know the former exercise 2.3 ;-).

27. October 2009:

This Thursday instead of the exercises a lecture will be given between 16:00 and 17:30. We are currently looking for an adequate room.

12. October 2009:

Welcome to the course "Automata Theory and Formal Languages"

The lecture on 10/19/2009 has been cancelled (SET-Einführungstage).
The first lecture will be on Wednesday, 10/21/2009.