Vorlesungen Automaten und formale Sprachen Effiziente Algorithmen und Datenstrukturen I Randomisierte Algorithmen Parallele Algorithmen Seminar Ausgewählte Themen aus Effiziente Algorithmen Praktikum Algorithmen für Programmierwettbewerbe

Automata and Formal Languages

News

The exam review will take place on Monday, February 02 2015 between 10:00 and 12:00 in room 03.09.037. Please write an email to Moritz Fuchs if you want to attend.

Course

• Lecturer:
  Prof. Dr. Ernst W. Mayr
• Module:
  IN2041
• Area:
  4+2 hours per week in area III (Theoretical Computer Science)
  core course
• Time and Place:
  Tuesday, 08:30–10:00, 00.13.009A
  Friday, 10:15–11:45, 00.13.009A
• Exercises:
  2 hours per week exercises accompanying the lectures
  Tuesday, 12:15–13:45, 03.11.018
  Teaching Assistant: Moritz Fuchs
  
• Exam:
  Final exam: The final exam will take place on Wed February 11, 2015 from 11:30 to 14:30 in room MI HS3.
  Repeat exam (oral): Friday, April 10, 2015 from 9am in room MI 03.09.054.
  If you want to take the repeat exam, register on TUMonline by March 21!
  
  The times given represent the net examination time. Please attend 15 minutes before.
  The only aid permitted is an A4-page (two sides) containing notes handwritten by yourself (no printer output).
• Audience:
  graduate students of computer science
  students with computer science as minor
• ECTS: 8 Punkte
• Prerequisites:
  1st and 2nd year Theory Courses, in particular THEO.
• Recommended for:
  Extended knowledge in complexity theory
• Office Hours:
  look here

Course Contents

Automata on finite words

• Automata classes and conversions
• Regular expressions, deterministic and nondetermistic automata
• Conversion algorithms
• Minimization and reduction
• Minimizing DFAs
• Reducing NFAs
• Boolean operations and tests
• Implementation on DFAs
• Membership, complement, union, intersection, emptiness, universlaity, inclusion, equality.
• Implementation on NFAs
• Operations on relations
• Projection, join, post, pre.
• Operations on finite universes: decision diagrams.
• Automata and logic
• Applications: pattern-matching, verification, Presburger arithmetic

Automata on infinite words

• Automata classes and conversions
• Omega-regular expressions
• Buchi, Streett, and Rabin automata
• Boolean operations
• Union and intersection
• Complement
• Emptiness check
• Applications: verification using temporal logic

Slides