automatteori

automatteori, matematisk baseret teori for formelle sprog. Automatteorien har mange anvendelser, såvel praktiske som teoretiske. Blandt de vigtigste anvendelser af dens begreber og modeller kan nævnes analyse og genkendelse af naturligt sprog samt konstruktion af programmeringssprog og programmeringssystemer til computere. Anvendelserne af teoriens resultater falder hovedsagelig inden for teoretisk datalogi og matematisk logik.

Et formelt sprog er en mængde (som regel uendelig) af tegnfølger, hvis enkelttegn stammer fra en endelig symbolmængde, et såkaldt alfabet. Det formelle sprog kan frembringes af en formel grammatik og genkendes af en automat.

En formel grammatik indeholder genskrivningsregler af formen a ⇒ b, hvor a og b er følger af symboler. Det formelle sprog, der frembringes af grammatikken, består af de tegnfølger over sprogets alfabet, der kan frembringes ved — ud fra et givet startsymbol — gentagent at udvælge en genskrivningsregel og erstatte en forekomst af dens venstreside med højresiden.

En automat er i en vis forstand det modsatte af en grammatik, idet den i stedet for at frembringe bestemte tegnfølger skal kunne læse en vilkårlig tegnfølge og afgøre, om den tilhører et givet formelt sprog. Automater er matematiske modeller af maskiner, der består af en læsemekanisme, der kan læse enkelttegn, en endelig (og begrænset) kontrolhukommelse samt evt. en ubegrænset hjælpehukommelse. Automaten læser en tegnfølge og beslutter, baseret på indholdet af sine hukommelser, enten at godkende eller afvise den.

Automater klassificeres efter, hvilken type hjælpehukommelse de udstyres med; grammatikker efter, hvor generelle deres genskrivningsregler er. Nogle af automatteoriens fundamentale resultater viser, hvorledes naturlige klasser af grammatikker frembringer de samme formelle sprog, som kan genkendes af tilsvarende naturlige klasser af automater. Ét sådant resultat er, at grammatikker i deres fulde generalitet frembringer samme klasse af formelle sprog, som genkendes af automater i deres fulde generalitet. Der er tale om den klasse af formelle sprog, som genkendes af såkaldte Turingmaskiner.

Definitionen af automater kan udvides, så de i stedet for endelige tegnfølger genkender uendelige tegnfølger. Disse udvidede modeller spiller en vigtig rolle for udviklingen af metoder og værktøjer til at arbejde med datamatiske systemer, der består af parallelle, kommunikerende processer.