Where academic tradition
meets the exciting future

Automata and Formal Languages (2016 Autumn)

Organisation: UTU / Dept. of Mathematics and Statistics

Credit Points: 10

Responsible Person: Jarkko Kari

Course code: MATE5225

Learning outcomes:
To learn the fundamental concepts of formal languages, automata theory and computation theory, such as finite automata, pushdown automata, context-free grammars and Turing machines. To learn their relationships and the basic closure properties. To understand the notion of undecidability, and to be able to prove algorithmic problems undecidable.

Contents:
Automata theory constitutes a cornerstone of mathematical computer science, and in particular finite automata have turned out to be very useful tools in many areas of discrete mathematics. Different models of automata in classical Chomsky hierarchy as well as corresponding grammars are considered and their generating power is compared. Basic undecidability results are proved.

7.9.–16.12.2016

Lectures:

  1. Wed 7.9.–14.12. weekly at 10–12
  2. Fri 9.9.–16.12. weekly at 10–12

Exercises:

  1. Mon 12.9.–12.12. weekly at 14–16