Automata and Formal Languages 2010/11

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

February 23

The solution to the exam has been released.

February 17

The exams have been corrected. You will receive a notification via TUMonline. You may have a look into your exams in the room 3.11.58 on Friday at 2 p.m.

February 8

Last year's exam can be found in the exercises section.

February 8

The final version of the lecture notes can be found here.

February 2

Please, choose a free time slot for your oral examination here

January 28

The DFS algorithms in the chapter on emptiness of Buechi automata (page 186) have been corrected, there was a potentially confusing mistake.

January 28

Homework sheet #12 has been released. No sheet is going to be released for the last exercise sesssion on Thursday Feb 10. Since the exam takes place the subsequent Tuesday, we shall instead discuss your questions, so prepare well!

January 19

The final states propagation along the padding has been fixed and new solutions to formulae 3, 4, 5 have been uploaded. If you discover other bugs, please let me know. A new formula 6 has been added. It is very simple, so try to understand this formula and its solution, you can then easily generate more examples for your testing by yourself. Furthermore, the most important exercises have been assigned a double star sign in the Exercises section. However, this of course does not mean that other exercises do not help you to pass the exam. On the contrary, if you can solve the unstarred exercises it indicates you will have no trouble in the exam;-)

And sorry for all the mess with the padding closure errors. I don't have any third-party solution that is guaranteed to be correct, so I have no other feedback than you. Therefore, the samples were incorrect at first. However, never try to produce the same results as me, instead always try to produce correct results;-)

January 19

Homework sheet #11 has been released.

January 12

Homework sheet #10 has been released.

January 5, 2011

Welcome to 2011. On Wednesday Jan 12, due to absence of prof. Esparza the lecture is replaced by exercises and the sheet #8 will be discussed. The homework sheet #9 has been released and will be discussed in the regular exercises on Thursday Jan 13.

Note the following mistake in the Skript. When projecting due to an existential quantification, a backward propagation of the final states along the padding letter is necessary (similalry as in the chapter on relations). Further discussion can take place in the exercises if necessary.

December 21

Homework sheet #8 has been released. (Sorry for forgetting to set the link last Wednesday.)

December 20

Some typos in the pattern-matching and teh verification chapter have been corrected. In the pattern-matching chapter, the recursive equation for overlap (page 126) has been corrected, as well as the programs derived from it. The range of the arrays has been changed from 0,...,m-1 to 1,..., n. The result is hopefully more readable.
In the verification chapter there was an "else" missing in the program of line 130.

December 16

If you have fixed your programming group write me (jan.kretinsky AT in.tum.de) an email with the subject AFL-SVN and a body containing your names and student-id numbers and I will reply with your login and password for your svn. By January 30 you should upload your final solution to this svn - https://svn.model.in.tum.de/stud/[your login]

December 15

Homework sheet #8 has been released. Exercises with two stars form a necessary part of your preparation for the exam. One starred ones are recommended. Exercises with no star are useful for deeper understanding.

December 15

The exam will take place on Feb 15 at 11 a.m. (not 11:30).

December 10

You can register for the exam through TUM-Online. If you want to take it, you must register before January 15. If you have problems with TUM-Online, then you can also register through the Info-Point.

December 8

The official statement of the programming assignment has been published.

December 1

Homework sheet #7 has been released.

December 1

A programming assignment section has been added.

December 1

Exercises in January will be prolonged by half an hour each in order to compensate for the loss of Dec 23.

November 29:

Exercises plan for the rest of the year 2010:

• Dec 1 (Wednesday): No lecture, we will discuss programming assignment and some exercises of 6th sheet.
• Dec 2: no exercises (Dies academicus)
• Dec 9: exercises will be shorter, approximately till 5 p.m. (I need to attend an extremely interesting talk on reachability problem in Petri nets)
• Dec 16: regular exercises (BDDs etc. and probably the last chance to raise questions or objections to the programming assignment before Christmas)
• Dec 23: no exercises

November 25:

Some small but irritating typos have been corrected in Chapter 10 (Presburger arithmetic). It is recommended to print the chapter again (perhaps next week, in case more typos are found).

November 25:

Homework sheet #6 has been released.

November 24:

I have just established an email account "afl_tum@yahoo.de" with password "passwort". Here you can anonymously send me emails to "jan.kretinsky@in.tum.de" with any feedback and criticism to the exercises. (If you want you can erase your mail from the Sent folder.) If I'm too fast or slow or don't explain something well, please inform me. I will try to do my best to improve the quality of the exercises. To that end, I need to know your opinion.

November 19:

A solution to Exercise 4.4 has appeared online. Due to the lack of time, we will only discuss it briefly. Please, read it in advance.

November 17:

The lecture on Nov 24 and the exercises on Nov 25 are swapped.

November 17:

Homework sheet #5 has been released.

November 10:

Figure 4.3. has been corrected, and also some typos. In particular, there was a typo in Lemma 4.4. At the end of the lemma instead of "q_2 not in F_2" it should say "q_2 in F_2". A new example (Figure 4.4.) has been added.

November 10:

Homework sheet #4 has been released.

November 5:

The exercises will take place in the Medizintechnik lecture hall from now on.

November 5:

At a student's request I'm making the slides available under `Material'.

November 3:

Homework sheet #3 has been released.

October 27:

Homework sheet #2 has been released.

October 25:

Two missing transitions have been added to Figure 2.2.

October 22:

Moritz Fuchs has found a mistake in algorithm NFAetoNFA, page 20 of the lecture notes (many thanks!). Line 11 should not say
if (q1,a,q3) not in d' then add (q1,a,q3) to W
but
if (q2,a,q3) not in d' then add (q2,a,q3) to W

October 20:

Homework sheet #1 has been released.

September 2011:

Welcome to the course "Automata Theory and Formal Languages"

We will post here all the news related to the course. If you're interested in taking the course,
check the menu points Content and Material; they give a pretty good idea of what the course is about.