Overgangsfunksjonen

Overgangsfunksjonen er en matematisk funksjon som beskriver hvordan systemets tilstand endres fra en tilstand til en annen som svar på en inndata eller tid. Begrepet er sentralt i formale systemer, som automata, og i generelle diskrete eller kontinuerlige dynamiske modeller.

I automata-teori brukes overgangsfunksjonen til å definere oppførselen til et automat eller en maskin. For et deterministisk endelig automat (DFA) er overgangsfunksjonen δ en total funksjon δ: Q × Σ → Q, der Q er mengden av tilstander og Σ alfabetet. Starttilstanden er q0 ∈ Q, og akseptant-tilstandene F ⊆ Q avgjør om et ord w ∈ Σ* blir akseptert ved å følge δ gjennom hele ordet og se om slutt-tilstanden er i F. For et nondeterministisk endelig automat (NFA) er δ i stedet δ: Q × Σ → P(Q), det vil si at fra en tilstand og et symbol kan man gå til flere mulige tilstander. Epsilon-overganger kan gjøres mulig ved δ: Q × (Σ ∪ {ε}) → P(Q), som lar tilstander kobles uten å lese et tegn.

Overgangsfunksjonen kan også beskrives som en tilstandsdiagram eller en overgangstabell, og den er grunnleggende for beregning av den språklige merkethet til et automat. I diskrete tids dynamiske systemer beskriver en tilsvarende funksjon hvordan state updateres: x_{t+1} = f(x_t, u_t), der x_t er tilstanden og u_t er kontroll- eller inngangsvektoren.

Innenfor stokastiske prosesser brukes ofte overgangsstrukturer som overgangskjerner (transition kernels) som gir sannsynligheter for å bevege seg mellom tilstander, noe som ligner en probabilistisk form for overgangsfunksjonen i automatiske modeller. Overgangsfunksjonen gir dermed en felles ramme for å modellere og analysere tilstandsforandringer i ulike systemer.