Contact
Teaching
 |
 |
|
| Automata and Formal Languages 2013/14 | ||
 |
 |
| News | Dates | Grading | Content | Exercises | Exam | Material |
10.03.2014
The list for the repetition exam can be found at the room 03.11.044. The repetition exams are oral. Possible dates are March 24th and 25th.25.02.2014
The inspection of the written exam (Klausureinsicht) will be on March 3rd at 2pm in room 03.11.051.5.02.2014
Contents of today's lecture: Carton-Michel automata (part 2)3.02.2014
Contents of today's lecture: Carton-Michel automata aka strongly unambiguous automata (part 1)31.01.2014
Exercise sheet 11 is online. We also provided solutions to selected exercises.28.01.2014
The lecture notes now include Angluin's learning algorithm.27.01.2014
Contents of today's lecture: From deterministic Muller automata to deterministic Rabin and deterministic parity automata, Landweber's characterization of deterministic omega-regular languages25.01.2014
Exercise sheet 10 is online.23.01.2014
Contents of today's lecture: Safra's construction (part 2), order vectors with hits23.01.2014
There will be a lecture from 14:30 to 16:00 in room 03.10.011 (this is the compensation for the skipped lecture on 23.12.2013).22.01.2014
Contents of today's lecture: Transformations between the various acceptance conditions, Safra's construction (part 1)20.01.2014
Contents of today's lecture: Klarlund's construction (part 2), other acceptance conditions for automata over infinite words17.01.2014
Exercise sheet 9 is online.15.01.2014
The lecture notes now include Hopcroft's minimization algorithm. I also put some German notes regarding omega-regular languages online.15.01.2014
Contents of today's lecture: Complementing Büchi automata using Klarlund's construction (part 1)13.01.2014
Contents of today's lecture: Complexity of Hopcroft's minimization algorithm, Michel's lower bound for complementing Büchi automata12.01.2014
Exercise sheet 8 is online.8.01.2014
Contents of today's lecture: Hopcroft's minimization algorithm, its correctness, implementation details2.01.2014
Exercise sheet 7 is online.23.12.2013
A small update of the lecture notes is online.23.12.2013
Today is no lecture. We will make up for it in 2014.19.12.2013
Contents of today's lecture: an application of Angluin's L*-algorithm to learning some Boolean functions, MSO logic over infinite words18.12.2013
Contents of today's lecture: linked pairs, a characterization of omega-recognizable languages in terms of infinite substitutions, from homomorphims to Büchi automata, decision problems for Büchi automata18.12.2013
The Hopcroft-Karp equivalence test for deterministic automata is now included in the lecture notes.11.12.2013
Some algorithms are now included in the lecture notes.11.12.2013
Contents of today's lecture: the syntactic semigroup is the minimal recognizer, omega-regular = recognizable by finite semigroup, omega-regular languages are closed under complement9.12.2013
Exercise sheet 6 is online.9.12.2013
Contents of today's lecture: omega-rational expressions define the omega-regular languages, ultimately periodic words, Ramsey's Theorem for infinite edge-labeled graphs, recognition by homomorphisms, factorization-lemma (using Ramsey's Theorem), Arnold's syntactic congruence, syntactic homomorphism4.12.2013
Contents of today's lecture: omega-regular languages, Büchi automata, deterministic Büchi automata are weaker than nondeterministic Büchi automata and they are not closed under complement, closure of (deterministic) omega-regular languages under union and intersection, omega-rational expressions2.12.2013
Exercise sheet 5 is online.21.11.2013
Exercise sheet 4 is online. The next tutorial will be on Wednesday, November 27th, at 12:00 in HS3 instead of the lecture. The Wednesday lecture will take place on Thursday, November 28th, at 12:15 in 02.13.010 as usually the exercises do.14.11.2013
The chapter on Kleene's Theorem is online.12.11.2013
The remainder of the chapter on rational sets is online.11.11.2013
The first half of the chapter on rational sets is online (see lecture notes).05.11.2013
Moore's algorithm is now included in the lecture notes.04.11.2013
The first part of the lecture notes is online.30.10.2013
The third exercise sheet is online.28.10.2013
The second exercise sheet is online.23.10.2013
The first exercise sheet is online.22.10.2013
I prepared a quick repetition of basic notation.08.10.2013
The lectures on 14.10 or 16.10 are cancelled. The first lecture will be on Monday, October 21.October 14 is a welcome day for first-term students. All lectures are cancelled.
The cancellation of the October 16 lecture is due to an administrative problem that prevents the instructor (Dr. Manfred Kufleitner, University of Stuttgart),to start his appointment as invited professor at TUM before the beginning of the term. We apologize for the inconveniences.