Automatteori

Et eksempel på en enkel automat. Denne automaten aksepterer alle strenger av 0-er og 1-ere med et partal av 0-er.

Automatteori er i teoretisk informatikk studiet av abstrakte maskiner og de problema de er i stand til å løse. Automatteori er nært knytta til teorier om formelle språk, og automater er ofte klassifisert etter klassen av formelle språk de er i stand til å gjenkjenne.

Grunnleggende beskrivelse

En automat er en matematisk modell for en endelig tilstandsmaskin (engelsk: finite state machine, FSM). En FSM er en maskin som, når den får (en streng av) symboler som input, hopper gjennom ei serie av tilstander, etter en overføringsfunksjon (som kan uttrykkes som en tabell). I den vanlige «Mealy-varianten» av FSM-er, kan overføringsfunksjonen fortelle maskinen hvilken tilstand den skal gå til i neste steg, gitt en tilstand og et symbol.

Innputt blir lest, symbol for symbol, til det er lest helt til slutten. Man kan tenke på innputt som en teip med et ord skrevet på seg, og ordet blir lest med automatens lesehode, som flytter seg framover på teipen og leser ett symbol av gangen. Med en gang innputt er lest, eller brukt opp, sier man at automaten har stoppa.

Avhengig av tilstanden automaten stopper i, sier man at automaten aksepterer eller forkaster innputt. Hvis den stopper i en aksepterende tilstand, så aksepterer automaten innputt. Hvis automaten stopper i en forkastende tilstand, forkastes innputt. Settet av alle orda som automaten aksepterer, kalles det formelle språket som denne automaten aksepterer.

Litteratur

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman – Introduction to Automata Theory, Languages, and Computation (2nd Edition)
• Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Part One: Automata and Languages, kapittel 1–2, ss.29–122. Seksjon 4.1: Decidable Languages, ss.152–159. Seksjon 5.1: Undecidable Problems from Language Theory, ss.172–183.