Total automat

I den grundlæggende definition af en endelig automat er det ikke nødvendigt, at der fra alle tilstande findes en overgang for alle symboler. En total automat er en automat, der har definerede overgange fra alle tilstande for alle symboler i inputalfabetet.

Sådan konstruerer vi en total automat

Vi ser på denne automat A = ⟨Q, Σ, δ, q₀, F⟩:

Her er der ikke tegnet nogen overgang fra tilstanden q₀ for bogstavet »b«. Hvis en sådan situation opstår, siger vi, at automaten ikke accepterer det givne inputord. Set ud fra formaliseringen er det dog ikke nødvendigvis hensigtsmæssigt, at overgangsfunktionen δ ikke er defineret for nogle værdier; her er den f.eks. ikke defineret for δ(q₀, b).

Det kan let løses ved, at vi konstruerer en ækvivalent automat, som har én tilstand ekstra — til denne tilstand peger de »manglende« overgange, tilstanden er ikke accepterende, og alle yderligere input bliver ved med at løbe rundt i denne tilstand. Denne automat kalder vi en total automat. Den ændrede ækvivalente automat kunne se sådan ud:

Vi tilføjede tilstanden q_fail. Fra de øvrige tilstande førte vi en overgang til den netop hvis der ikke tidligere fandtes en overgang. Denne tilstand er ikke accepterende og løber rundt for alle yderligere input. Hvis vi i den foregående automat stødte på en manglende overgang, er der her ingen manglende overgang, og automaten ville havne i tilstanden q_fail.

Vi kan altså altid uden tab af almenhed antage, at automaten har definerede overgange for alle kombinationer af tilstande og tegn fra alfabetet.

Definition

For en total automat A = ⟨Q, Σ, δ, q₀, F⟩ gælder altså, at

$$\mathrm{\forall }q\in Q\mathrm{\forall }a\in \mathrm{\Sigma }\mathrm{\exists }r\in Q:\delta (q,a)=r.$$

Kilder

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools