Total automat

I grunndefinisjonen av endelig automat er det ikke nødvendig at det fra alle tilstander finnes en overgang for alle symboler. En total automat er en automat som har definerte overganger fra alle tilstander for alle symboler i inputalfabetet.

Hvordan konstruere en total automat

La oss ha denne automaten A = ⟨Q, Σ, δ, q₀, F⟩:

Her er det ikke tegnet noen overgang fra tilstanden q₀ for bokstaven «b». Hvis en slik situasjon oppstår, sier vi at automaten ikke aksepterer det gitte inputordet. Likevel kan det av hensyn til formaliseringen være upraktisk at overgangsfunksjonen δ ikke er definert for noen verdier; her er den for eksempel ikke definert for δ(q₀, b).

Det er lett å løse ved å konstruere en ekvivalent automat som har én tilstand ekstra — til denne tilstanden peker de «manglende» overgangene, tilstanden er ikke en sluttilstand, og alt videre input blir værende i denne tilstanden. Denne automaten kaller vi en total automat. Den endrede ekvivalente automaten kunne se slik ut:

Vi har lagt til tilstanden q_fail. Fra de andre tilstandene har vi laget en overgang til den hvis og bare hvis det ikke fantes noen overgang der fra før. Denne tilstanden er ikke en sluttilstand, og den går i løkke for alt videre input. Hvis vi i den forrige automaten støtte på en manglende overgang, er det ingen manglende overganger her, og automaten ville havnet i tilstanden q_fail.

Vi kan altså alltid uten tap av allmenngyldighet anta at automaten har definerte overganger for alle kombinasjoner av tilstander og tegn i alfabetet.

Definisjon

For en total automat A = ⟨Q, Σ, δ, q₀, F⟩ gjelder 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