MATE5225 Automata and Formal Languages (10 op)
Verkosto-opintojakso
Verkosto: Matematiikan ja tilastotieteen syventävien kurssien ristiinopiskelu
Tämä opintojakso on tarjolla Matematiikan syventävät opinnot -ristiinopiskeluverkostossa. Verkoston opinnot ovat tarjolla seuraaville opiskelijoille:
- Matematiikan kandidaattiohjelma
- Matematiikan maisteriohjelma
- Matematiikan aineenopettajien kandidaattiohjelma
- Matematiikan aineenopettajien maisteriohjelma
- Matematiikan, kemian tai fysiikan aineenopettajan ja luokanopettajan kandidaattiohjelma (matematiikan opintosuunta)
- Matematiikan, kemian tai fysiikan aineenopettajan ja luokanopettajan maisteriiohjelma (matematiikan opintosuunta)
- Matematiikan ja tilastotieteen tohtoriohjelma
- Matemaattisten tieteiden ja luonnontieteiden tohtoriohjelma (matematiikan opintosuunta)
Arviointiasteikko:
0-5
Kuvaus
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.
Osaamistavoitteet
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.
Lisätietoja
Preceding studies
mathematical maturity
Course will be given every other autumn (in even years).
Esitietojen kuvaus
Mathematical maturity