Totale automaat

In de basisdefinitie van een eindige automaat hoeft er niet vanuit alle toestanden een overgang te bestaan voor alle symbolen. Een totale automaat is een automaat die vanuit alle toestanden voor alle symbolen van het invoeralfabet overgangen heeft gedefinieerd.

Hoe construeer je een totale automaat

Neem deze automaat A = ⟨Q, Σ, δ, q₀, F⟩:

Hier is geen overgang getekend vanuit toestand q₀ voor de letter “b”. Als zo'n situatie zich voordoet, zeggen we dat de automaat het invoerwoord niet accepteert. Met het oog op formalisering is het echter niet handig als de overgangsfunctie δ voor sommige waarden niet gedefinieerd is; hier is δ(q₀, b) bijvoorbeeld niet gedefinieerd.

Dat is eenvoudig op te lossen door een equivalente automaat te construeren met één toestand extra — de “ontbrekende” overgangen wijzen naar die toestand, die toestand is geen eindtoestand en alle verdere invoer blijft in die toestand rondlopen. Deze automaat noemen we een totale automaat. De aangepaste equivalente automaat zou er zo uit kunnen zien:

We hebben de toestand q_fail toegevoegd. Vanuit de andere toestanden hebben we er een overgang naartoe getekend dan en slechts dan als daar eerder geen overgang bestond. Deze toestand is geen eindtoestand en heeft een lus voor alle verdere invoer. Als we in de vorige automaat dus op een ontbrekende overgang stuitten, is er hier geen ontbrekende overgang meer en komt de automaat in toestand q_fail terecht.

Zonder beperking van de algemeenheid kunnen we dus altijd aannemen dat de automaat voor alle combinaties van toestanden en tekens uit het alfabet overgangen heeft gedefinieerd.

Definitie

Voor een totale automaat A = ⟨Q, Σ, δ, q₀, F⟩ geldt dus dat

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

Bronnen

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