### Description

The course provides an introduction to formal languages and automata theory.### Schedule

week | date | topics | slides | solutions |
---|---|---|---|---|

01 | 05.10 & 09.10 | deterministic finite automata, closure properties | pdf (x1, x4) | |

02 | 12.10 & 23.10 | nondeterministic finite automata, ϵ-transitions, closure properties | pdf (x1, x4) | |

03 | 19.10 & 30.10 | regular expressions, homomorphisms | pdf (x1, x4) | |

04 | ||||

05 | 09.11 & 13.11 | state minimization, Myhill-Nerode relations | pdf (x1, x4) | |

06 | 16.11 & 20.11 | derivatives, Kleene algebra, equivalence of regular expressions | pdf (x1, x4) | |

07 | 23.11 & 27.11 | equivalence of finite automata, context-free grammars, ambiguity | pdf (x1, x4) | |

08 | 30.11 & 04.12 | Chomsky normal form, pumping lemma, CKY algorithm | pdf (x1, x4) | |

09 | 07.12 & 11.12 | Ogden's lemma, pushdown automata, closure properties | pdf (x1, x4) | |

10 | 14.12 & 18.12 | Turing machines, diagonalization | pdf (x1, x4) | |

11 | ||||

12 | 11.01 & 15.01 | diagonalization, reduction | pdf (x1, x4) | |

13 | 18.01 & 22.01 | reduction, Rice's theorem, unrestricted grammars | pdf (x1, x4) | |

14 | 25.01 & 29.01 | Rice's theorem, Post correspondence problem | pdf (x1, x4) | |

01.02 | 1st exam solution | |||

25.02 | 2nd exam solution | |||

27.09 | 3rd exam solution |

### Literature

The course is largely based on the following book:-
Dexter Kozen,

*Automata and Computability*, Springer-Verlag, 1997, ISBN 0-387-94907-0

#### Further Reading

Numerous other books exist that cover more or less the same material. The following are recommended:-
John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman,
*Introduction to Automata Theory, Languages, and Computation (3rd edition)*, Addison Wesley, 2007, ISBN 9780321462251 -
Elaine Rich,
*Automata, Computability, and Complexity*, Pearson Education, 2008, ISBN 9780132288064