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.
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.
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 SyllabusDate | 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 |
Projects (last updated March 31st, 2020) |
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) |