TIEA241 Automatons and Formal Languages (5 cr)

Study level:
Intermediate studies
Grading scale:
0-5
Language:
Finnish
Responsible organisation:
Faculty of Information Technology
Curriculum periods:
2017-2018, 2018-2019, 2019-2020

Description

Sisältö

Äärelliset automaatit ja säännölliset kielet, kieliopit ja kontekstittomat kielet, pinoautomaatti, rekursiivisesti etenevä jäsentäminen, kontekstiset ja rajoittamattomat kieliopit, Turingin koneet, ratkeavuus ja puoliratkeavuus.

Suoritustavat

Kirjalliset oppimistehtävät tai tentti.

Arviointiperusteet

Kurssi arvioidaan oppimistehtävien tai tentin perusteella. Läsnäolopakkoa ei ole.

Learning outcomes

Opintojakson suoritettuaan opiskelija osaa selostaa seuraavien käsitteiden keskeisen sisällön ja niiden väliset erot: äärellinen automaatti, pinoautomaatti, Turingin kone; deterministinen ja epädeterministinen automaatti; säännöllinen lauseke; säännöllinen, kontekstiton, kontekstinen ja yleinen kielioppi; säännöllinen, kontekstiton, laskettava ja laskettavasti lueteltava kieli; sekä päätösongelma, puoliratkeava päätösongelma ja ratkeava päätösongelma. Lisäksi opiskelija osaa soveltaa osaa seuraavista abstraktioista ohjelmointitehtävissä: säännölliset lausekkeet, äärelliset automaatit, kontekstittomat kieliopit, pinoautomaatit. Lisäksi opiskelija osaa tulkita tietojenkäsittelyteoreettisia määritelmiä kurssin sisältöihin kuuluville käsitteille sekä laatia yksinkertaisia tietojenkäsittelyteoreettisia todistuksia.

Description of prerequisites

ohjelmointitaito (esimerkiksi Ohjelmointi 1, Ohjelmointi 2 ja Algoritmit
1) sekä abstraktin matematiikan kielen ja todistustekniikoiden alkeiden
osaaminen (esimerkiksi TIEP1020 Diskreetit rakenteet tai matematiikan
aineopintoja)

Study materials

Sipser: Introduction to the Theory of Computation (3nd international ed). Thompson 2006. ISBN 0-619-32764-2.
Osin myös Aho, Lam, Sethi, Ullman: Compilers – Principles, Techniques, , Tools (2nd ed). Addison Wesley 2007.

Completion methods

Method 1

Select all marked parts
Parts of the completion methods
x

Teaching (5 cr)

Type:
Participation in teaching
Grading scale:
0-5
Language:
Finnish

Teaching