Automata and Formal Languages

Spring 2019


[Announcements] [General Information] [Homeworks] [Additional Material] [Schedule]

Announcements


General Information

Course name: Automata, Formal Languages and Applications
Course Instructor: Vangelis Paschos
TD Instructor: Michail Lampis.
Email: michail.lampis AT dauphine.fr
We meet on Mondays at 10:15-11:45 or 12:00-13:30 (two groups). Please come to your assigned group only, in order to avoid overcrowding.

The main topic of this class is Theoretical Computer Science and more precisely, the theory of Formal Languages. Topics we plan to cover are: Deterministic and Non-Deterministic Automata, Regular Languages and Expressions, Context-Free Grammars, and Turing machines. More information on the topics to be covered will appear in the schedule below (which will be updated during the semester). As part of the TD, students will be expected to complete a number of homework assignments.
The homeworks assigned during the TD count for 30% of the final grade. The final exam counts for the remaining 70%.

Homework Assignments

General policy: Students must work on their assignments individually. Assignments must be turned in on the day of the deadline, in person, on paper, before the start of the TD (because the solutions may be discussed in class).

Additional Material


TD Schedule

TD No. Date Topic Notes
1 Mon 28/1 Introduction, Mathematical Background Example exercises
2 Mon 4/2 Regular Expressions Examples and notes
3 Mon 11/2 Deterministic Finite Automata Examples and notes
4 Mon 18/2 Non-Deterministic Automata Examples and notes
5 Mon 25/2 Deterministic and Non-deterministic Automata See last week's notes
6 Mon 11/3 More NFAs See last week's notes
7 Mon 18/3 More NFAs and Myhill-Nerode theorem Examples and notes
8 Mon 25/3 Myhill-Nerode, Pumping Lemma Examples and notes
9 Mon 1/4 Pumping Lemma, Non-regular languages See last week's notes
10 Mon 8/4 Context-free grammars Examples and notes
11 Mon 15/4 Diagonalization, Turing machines Examples and notes
12 Mon 6/5 Halting problem, Revision