automaattiteoriaan

Automaattiteoria on tietojenkäsittelyn teoreettinen ala, joka tutkii abstrakteja laskijoita ja niihin liittyviä laskentaprosesseja sekä formaleja kieliä. Tutkimuksessa määritellään, millaisia kieleitä erilaiset automaatit voivat tunnistaa ja miten laskenta voidaan mallintaa matemaattisesti.

Perusmallit ovat finite automaatit: deterministiset DFA ja ei-deterministiset NFA. Näillä koneilla on rajallinen muisti, ja ne tunnistavat säännölliset kielet. DFA:n tilasiirtymien rakenne on yksikäsitteinen, ja minkä tahansa NFA:n voi muuntaa DFA:ksi samaa kieltä tunnistaen.

Pushdown automaatit (PDA) laajentavat muistia pino-muistilla, mikä mahdollistaa kontekstuaalisten kielten tunnistamisen. PDA:lla voidaan toteuttaa syntaksin parsintamenetelmiä, ja ne ovat keskeisiä ohjelmointikielten syntaksin analyysissä.

Turingin koneet (TM) muodostavat yleisen laskennan mallin. Church-Turing-teesi liittää tämän mallin kaikkiin toteutettavissa oleviin laskemismenetelmiin. Keskeisiä käsitteitä ovat päättäväisyys ja semi-päätettävyys sekä tunnettu pysähtymisongelma.

Sovellukset ulottuvat ohjelmoinnista tekstin käsittelyyn ja ohjelmistojen varmentamiseen. Automaatit toimivat teoreettisena perusrakenteena kääntäjissä, parsinnassa, säännöstöjen mallinnuksessa sekä mallintamisen tarkastuksessa (model checking) sekä protokollien analyysissä.