Automaatit ja formaalit kielet, Luento-opetus

Opintojakson suoritettuaan opiskelija tuntee automaattien ja formaalien kielten peruskäsitteet. Lisäksi hän osaa sekä suunnitella että toteuttaa automaatteja ja formaaleja kieliä erilaisia sovelluksia ja tietojenkäsittelyllisiä tehtäviä varten.

Äärelliset, deterministiset ja epädeterministiset automaatit sekä pinoautomaatit. Säännölliset lausekkeet ja kielet. Formaalien kielten peruskäsitteitä. Kieliopit ja Chomskyn kielihierarkia. Yhteysvapaat kielet. Esimerkkisovelluksia ja yleistyksiä.

Esitiedot

Johdatus matemaattiseen päättelyyn, tietorakenteet ja algoritmit, diskreetin matematiikan perusteet tai vastaavat tiedot.

Suositellut esitiedot

• Johdatus matemaattiseen päättelyyn, MTTMP2, 5op
• Diskreetti matematiikka, MATH.MA.210, 5op
• Tietorakenteet ja algoritmit 1, COMP.CS.300, 5op
• Tietorakenteet, TIETA6, 10op

1. Luentomateriaali ja automaattisesti arvioitavat tehtävät: https://plus.tuni.fi
   
2. Lisämateriaalina kiinnostuneille ohessa mainittu oppikirja.
   

Hopcroft, Motwani, Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2001.

Yleinen asteikko, 0-5