aksepttilstandene

Aksepttilstandene er en kategori av tilstander i en endelig automaton som bestemmer hvilke inndata som blir akseptert. I et deterministisk eller nondeterministisk endelig automaton spiller aksepttilstandene rollen som måltilstander for å avgjøre om en gitt streng blir akseptert.

Formelt sett består et deterministisk endelig automaton (DFA) av en tuple A = (Q, Σ, δ, q0, F) der Q er et endelig mengde tilstander, Σ er inngangsalfabetet, δ er overganger, q0 ∈ Q er starttilstanden og F ⊆ Q er settet av aksepttilstander. En streng w ∈ Σ* aksepteres dersom kjøringen δ*(q0, w) ender i en tilstand i F. For nondeterministiske automata (NFA) er δ en funksjon til potensmengden P(Q), og en streng aksepteres hvis det finnes en mulig kjøring fra q0 som ender i en aksepttilstand i F. Mange NFAs har også ε-transisjoner (gratis overganger uten symbol).

Et klassisk eksempel er et automaton som gjenkjenner strengene over {0, 1} som ender med bokstaven 1. Dette kan ha to tilstander: q0 (ikke-aksepterende) og q1 (aksepttilstand). Overganger: q0 på 0 går til q0, på 1 går til q1; q1 på 0 går til q0, på 1 går til q1. En streng aksepteres hvis slutt-tilstanden er q1.

Betydning: Aksepttilstander er kjernen i definisjonen av språket som et automaton gjenkjenner, L(A). Alle regulære språk kan erkjenneres av noen DFA eller NFA, og konvertering mellom disse formene og bygging av aksepttilstander er sentralt i automatteori og formelle språk.