Automater och språk

Automater är matematiska maskiner, det vill säga abstrakta beräkningsapparater. Deras syfte är att fånga, studera och jämföra olika modeller och syn på det abstrakta begreppet beräkning och dess olika aspekter. Automaternas beräkningsstyrka kan karakteriseras genom språkklasserna (det vill säga mängderna av strängar över ett ändligt alfabet av symboler) som de kan känna igen. Viktiga begrepp inom datavetenskapen som tillstånd, ickedeterminism och minimeringfångas med den enkla modellen av ändliga automater, som känner igen klassen av reguljära språk. Automater utgör grunden för implementeringen av många programmeringsspråk, varvid parsning ar en typisk tillämpning. En annan viktig orsak till att studera automater är att fånga upp begreppet effektiv beräkningsförmåga, det vill säga att karakterisera begreppet beräkning som en process som kan implementeras fysiskt. Detta gör att följande viktiga fråga kan ställas:vilka problem kan avgöras på ett algoritmiskt sätt och vad är gränserna för detta?