Automat complet

În definiția de bază a automatului finit nu este necesar ca din toate stările să existe o tranziție pentru toate simbolurile. Automatul complet este un automat care are definite tranziții din toate stările pentru toate simbolurile alfabetului de intrare.

Cum construim un automat complet

Fie automatul A = ⟨Q, Σ, δ, q₀, F⟩:

Aici nu este desenată tranziția din starea q₀ pentru litera „b”. Dacă apare o astfel de situație, spunem că automatul nu acceptă cuvântul de intrare. Din punctul de vedere al formalizării, însă, s-ar putea să nu fie potrivit ca funcția de tranziție δ să nu fie definită pentru unele valori; aici, de exemplu, nu este definită δ(q₀, b).

Acest lucru se rezolvă ușor construind un automat echivalent care are o stare în plus – spre această stare vor duce tranzițiile „lipsă”, starea nu va fi finală, iar toate intrările următoare vor rămâne în buclă în această stare. Acest automat îl numim automat complet. Automatul echivalent modificat ar putea arăta astfel:

Am adăugat starea q_fail (stare de blocare). Din celelalte stări am dus o tranziție spre ea exact atunci când înainte nu exista acolo nicio tranziție. Această stare nu este finală și rămâne în buclă pentru toate intrările următoare. Dacă în automatul anterior am fi întâlnit o tranziție lipsă, aici nu mai există nicio tranziție lipsă, iar automatul ar ajunge în starea q_fail.

Putem deci presupune întotdeauna, fără a restrânge generalitatea, că automatul are definite tranziții pentru toate combinațiile de stări și caractere din alfabet.

Definiția

Pentru un automat complet A = ⟨Q, Σ, δ, q₀, F⟩ are deci loc

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

Surse

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