Automatteori

Den här artikeln behöver källhänvisningar för att kunna verifieras. (2018-10) Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Inom automatteori studerar man matematiska modeller för utförande av beräkningar, allmänt kallade automater.

Gemensamt för modellerna är att alla accepterar en mängd indata, genomför beräkningen och redovisar resultatet genom att leverera en mängd utdata. Automaten startar i ett väldefinierat starttillstånd och genomgår en serie av tillståndsförändringar, kallade exekvering, enligt ett förutbestämt program. Om automaten under exekveringen når ett bestämt stopptillstånd så stannar automaten och utdata blir tillgänglig för en utomstående observatör.

Inom automatteorin studeras flera olika modeller för automater med olika egenskaper och olika beräkningsförmåga, de vanligaste modellerna är dock finita automater, stackautomater eller pushdown automater, samt Turingmaskiner.

Beräkningsmodellerna inom automatteori ligger som grund för imperativa programspråk.