MATE5225 Automata and Formal Languages (10 cr)
Cooperation network course
Network: Cross-institutional studies in advanced courses in mathematics and statistics
This course is offered through the Network for Advanced Studies in Mathematics. These studies are available for the following degree students:
- Bachelor's Degree Programme in Mathematics
- Master's Degree Programme in Mathematics
- Bachelor's Degree Programme in Mathematics (Subject Teacher)
- Master's Degree Programme in Mathematics (Subject Teacher)
- Bachelor's Degree Programme in Mathematics, Chemistry or Physics Subject Teacher Education and Primary Teacher Education (Specialication in Mathematics)
- Master's Degree Programme in Mathematics, Chemistry or Physics Subject Teacher Education and Primary Teacher Education (Specialication in Mathematics)
- Doctoral Programme in Mathematics and Statistics
- Doctoral Programme in Mathematics and Science (Specialication in Mathematics)
Grading scale:
0-5
Description
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.
Learning outcomes
To learn the fundamental concepts of formal languages, automata theory and computation theory, such as deterministic and non-deterministic finite automata, regular expressions, context-free grammars, pushdown automata and Turing machines. To be able to compare their generative powers. To learn structural properties and pumping lemmas, basic closure properties and decision algorithms To understand the notion of undecidability, and to be able to prove algorithmic problems undecidable.
Additional information
Preceding studies
mathematical maturity
Course will be given every other autumn (in even years).
Description of prerequisites
Mathematical maturity