Formal Languages and Automata Theory (SS2020)





This is the webpage for the lecture and seminar of Formal Languages and Automata Theory (IE 1).

NEWS: The Midterm will be on May 21st, online, during the lecture. Topics are all from Courses 1 - 6 (included). You have to make sure you have a camera and a microphone which are switched on during the midterm. If you think you might have problems with this you have to announce me no later than May 18 and I will arrange an oral examinations. You have to write the solutions to the test on a notebook and your name and subject variant should be visible on each page. Or if you have a tablet and write with a pen, it is also accepted. The Midterm is 60 minutes and then you have 10 minutes to upload your exam in Google Classroom (code to be handed in by email). The subjects and the variants will be available on Google Classroom right before the examination.

Organisation

Course: Thursday, 4:20 - 5:50 PM, room AM

Seminar:

Language: English

Office hours: Thursday, 9:40 - 11:10 AM, or by appointment, in F109 / online.

Attendance and Grading

There is no mandatory attendance for the lecture or seminar, however, note that the final grade includes your activity during the semester.

The final grade is computed as follows (more details on the Syllabus): FG = 30% * M + 40% * E + 30% * S + (20% or 5%) * P, where:

If FG > 4.1 it is 5, > 5.1 it is 6, ..., > 9.1 it is 10.

For more details see the Syllabus

Tentative Schedule

Date Topic Slides Seminar
Week 1 Organizational Matters, Introduction to Formal Languages and Automata Theory Course 1 Homework 1
Week 2 Introduction to Formal Languages and Automata Theory (cont'd) Course 2 Homework 2
Week 3 Finite Automata/Finite State Machines Course 3 Homework 3
Week 4 Finite Automata/Finite State Machines (cont'd) Course 4 Homework 4
Week 5 Finite Automata/Finite State Machines (cont'd) Course 5 Homework 5
Week 6 Finite Automata/Finite State Machines (cont'd) Course 6 Homework 6
Week 7 Regular Expressions Course 7 Homework 7
Week 8 DFA minimization Course 8 Homework 8
Week 9 Properties of Regular Languagess Course 9 same homework
Week 10 & 11 Context-free Grammars. Push-down Automata Course 10 Homework 9
Week 12 Midterm
Week 13 Students Presentations Students Presentations/Seminar recoverings
Week 14 Students Presentations Students Presentations/Seminar recoverings

List of Projects

Projects (last updated March 31st, 2020)

Resources

Formal Languages, by Mircea Dragan, lecture notes
Dexter C. Kozen - Automata and Computability (on request)
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation (on request)