automaatide

Automaatide ehk automaatide teooria on abstraktsete arvutusmasinate uurimine. Need masinad modelleerivad, kuidas sisendi alusel liiguvad olekud ja milliseid keeli või probleeme arvutid saavad lahendada. Automaatteooria keskendub võimsuse ja piirangute mõistmisele: millised keeled on automaatidega recogniseeritavad ja millised probleemid on otsustatud.

Peamised tüübid on lõplikud automaadid (deterministlikud DFA-d ja mitte‑deterministlikud NFA-d), mis recogniseerivad regulaarkeeled; puskand automaadid (PDA-d), mis suudavad töötada kontekstivaarsete keeltega; lineaar-piiratatud automaadid (LBA-d), mis on piiratud mäluversioonid; ning Turingi masinad, mis modelleerivad üldist arvutust ning recogniseerivad rekursiivselt loetavaid keeli. Deterministlik ja mitte‑deterministlik lähenemine on oluline; DFA-d ja NFA-d on teoreetiliselt võrdväärsed regulaarkeelete mõttes, kuid erinevad kasutusviisidelt.

Rakendused: regulaarsed väljendid ja tekstiotsing põhinevad DFA- ja NFA-mudelitel; kontekstivaarsete keelte töötlemine on oluline parserites ja kompilaatorites; tarkvara verifikatsioon ja model checking kasutavad automaatide teooriat süsteemide õigsuse kontrollimiseks.

Ajalugu: ideed tulid 1930.–1950. aastatel Turingi, Churchi ja von Neumana tööde kaudu; Noam Chomsky tutvustas 1956. aastal formaalse keeleteooria raamistikku. Automaatteooria on mõjutanud nii teoreetilist arvutiteadust kui ka praktilisi tööriistu, nagu kompilaatorid ja tekstiotsinguaparaadid.