Automatenmodellen

Automatenmodellen zijn abstracte computationele apparaten die worden gebruikt om de beschrijving van berekeningen en formele talen te bestuderen. Een automaat leest een invoerketen, verwerkt deze volgens een set regels en levert een besluit op als de invoer voltooid is. Ze dienen als wiskundige modellen van rekenprocessen en worden gebruikt om te bepalen welke talen door welke vorm van geheugen en proceskracht kunnen worden herkend of geproduceerd.

De meest basale klassen zijn eindige automaten, onderverdeeld in deterministische eindige automaten (DFA) en niet-deterministische eindige automaten (NFA). DFA's hebben voor elke toestand en elk symbool precies één overgang; NFAs kunnen meerdere mogelijkheden hebben. Zowel DFA als NFA herkennen precies de reguliere talen. Een NFA kan geconverteerd worden naar een equivalente DFA, maar het aantal toestanden kan exponentieel toenemen.

Voor contextvrije talen bestaan pushdown automaten (PDA), die een eindige toestand hebben plus een stapel als geheugen. PDA's met deterministische overweging hebben beperkte kracht en kunnen sommige maar niet alle contextvrije talen herkennen.

Verder naar krachtiger modellen: lineair begrensde automaten en Turingmachines. Turingmachines zijn onbeperkt geheugen en vormen de standaard voor volwaardige berekenbaarheid. Zij herkennen de recursief doorzoekbare talen; beslisproblemen als het halteren zijn in het algemeen onbepaald. Turingmachines leveren ook de basis voor de klassenschema van Chomsky: regulier, contextvrij, contextgevoelig en recursief vervulbaar.

Andere varianten bestaan, zoals Mealy- en Moore-machines die output genereren tijdens de transitie, probabilistische en quantum-automata die probabilistische of quantum-beslissingen introduceren, en twee- of meertapesystemen.

Toepassingen verschijnen in compilerontwerp, formele verificatie, parsing, linguïstiek en modelcontrole. Automatenmodellen vormen een fundamenteel kader voor theoretische en toegepaste informatica.