MATE5225 Automata and Formal Languages 10 ECTS
Organised by
Mathematics
Person in charge
Department of Mathematics and Statistics, Jarkko Kari
Planned organizing times
Period(s) I II III IV
2016–2017 X X
Preceding studies
mathematical maturity

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.

Teaching methods

Teaching method Contact Online
Lectures 56 h 0 h
Exercises 26 h 0 h

Teaching language

English

Modes of study

Option 1
Available for:
  • Degree Programme Students
  • Other Students
  • Doctoral Students
  • Exchange Students
Exercise(s)
  • In English
Written exam
  • In English
Participation in classroom work
  • In English

or weekly exercises and midterm exams

Evaluation

Numeric 0-5.

Study materials

lecture notes

Belongs to following study modules

Department of Mathematics and Statistics
Department of Future Technologies
2016–2017
Teaching
Archived Teaching Schedule. Please refer to current Teaching Shedule.
Department of Mathematics and Statistics
DP in Mathematics and Statistics
DP in Mathematics
DP in Statistics
MDP in Information Security and Cryptography
Finnish Study Modules