Total automat

I grunddefinitionen av en ändlig automat krävs det inte att det från alla tillstånd finns en övergång för alla symboler. En total automat är en automat som har definierade övergångar från alla tillstånd för alla symboler i inalfabetet.

Hur man konstruerar en total automat

Vi tar den här automaten A = (Q, Σ, δ, q₀, F):

Här är ingen övergång från tillståndet q₀ för bokstaven ”b” ritad. Om en sådan situation uppstår säger vi att automaten inte accepterar det givna indataordet. Ur formell synvinkel kan det dock vara olämpligt att övergångsfunktionen δ inte är definierad för vissa värden; här är den till exempel inte definierad för δ(q₀, b).

Det löser vi enkelt genom att konstruera en ekvivalent automat som har ett tillstånd till — till det tillståndet pekar de ”saknade” övergångarna, det tillståndet är inte ett sluttillstånd och vid all fortsatt indata stannar automaten kvar i det. Den här automaten kallar vi en total automat. Den ändrade ekvivalenta automaten kan se ut så här:

Vi lade till tillståndet q_fail. Från de övriga tillstånden drog vi en övergång till det om och endast om det inte fanns någon övergång där tidigare. Det här tillståndet är inte ett sluttillstånd, och automaten stannar kvar i det för all fortsatt indata. Om vi i den föregående automaten stötte på en saknad övergång, finns det här ingen saknad övergång, och automaten skulle hamna i tillståndet q_fail.

Vi kan alltså alltid utan inskränkning anta att automaten har definierade övergångar för alla kombinationer av tillstånd och bokstäver i alfabetet.

Definition

För en total automat A = (Q, Σ, δ, q₀, F) gäller alltså att

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

Källor

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