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)
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.
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
Unpublished assessment item