Luokkakoneet

Luokkakoneet ovat abstrakteja laskennallisia malleja, joita käytetään määrittämään, millaisiin kieliin syötteet kuuluvat. Ne ovat keskeinen käsite automaatioteoriassa ja muodostavat osan Chomskyn kielihierarkiasta. Luokkakoneet jaotellaan neljään pääkategoriaan sen mukaan, millaista muistia ja millaisia siirtymiä ne käyttävät.

Säännölliset kielet tunnistetaan finit automaateilla (DFA ja NFA). Näillä kielillä on rajallinen muistivarasto, ja ne ovat tehokkaasti analysoitavissa sekä sulkeutuneet monien operaation suhteen.

Kontekstuaaliset kielet tunnistetaan pushdown-automaatteilla, jotka käyttävät pinoa muistina. Näiden kielten esimerkkejä ovat suurimman osan ohjelmointikielien syntaksit.

Kontekstisidonnaiset kielet tunnistetaan lineaarisesti rajoitetuilla automaateilla (lineaarisesti rajatut automaatit). Niillä on enemmän muistia kuin kontekstuaalisilla automaateilla, mutta ne ovat silti rajoitettuja.

Rekursiivisesti numeroitavat kielet tunnistetaan Turing-koneilla, joiden muistia ei ole ennalta rajoitettu. Tämä luokka kattaa suurimman osan laskennallisista ongelmista.

Käytännössä luokkakoneiden tutkimus valaisee, mitkä ongelmat ovat ratkaistavissa automaattisesti ja millaiset rajoitukset kunkin mallin avulla muodostuvat. Luokkakoneet tarjoavat teoreettisen banin kieli- ja laskentatutkimukseen sekä sovelluksiin kuten kielten suunnitteluun ja ohjelmointikääntäjien syntaksianalyysiin.