Teljes automata

A véges automata alapdefiníciójában nem szükséges, hogy minden állapotból minden szimbólumra legyen átmenet. A teljes automata olyan automata, amelynek minden állapotból definiált az átmenete a bemeneti ábécé minden szimbólumára.

Hogyan építsünk teljes automatát

Legyen adott ez az A = ⟨Q, Σ, δ, q₀, F⟩ automata:

Itt nincs berajzolva átmenet a q₀ állapotból a „b” betűre. Ha ilyen helyzet áll elő, azt mondjuk, hogy az automata nem fogadja el az adott bemeneti szót. Formalizálás szempontjából azonban nem biztos, hogy szerencsés, ha a δ átmeneti függvény bizonyos értékekre nincs definiálva; itt például δ(q₀, b) nincs definiálva.

Ezt könnyen megoldhatjuk úgy, hogy megszerkesztünk egy ekvivalens automatát, amelynek eggyel több állapota van – ebbe az állapotba mutatnak a „hiányzó” átmenetek, ez az állapot nem végállapot, és minden további bemenetre már ebben az állapotban marad. Ezt az automatát nevezzük teljes automatának. A módosított ekvivalens automata így nézhet ki:

Hozzáadtuk a q_fail állapotot. A többi állapotból akkor vezettünk bele átmenetet, ha előtte nem létezett ott átmenet. Ez az állapot nem végállapot, és minden további bemenetre önmagába fordul vissza. Ha tehát az előző automatában hiányzó átmenetbe ütköztünk, itt már nincs hiányzó átmenet, és az automata a q_fail állapotba kerülne.

Az általánosság megszorítása nélkül tehát mindig feltételezhetjük, hogy az automatának az állapotok és az ábécé karaktereinek minden kombinációjára definiáltak az átmenetei.

Definíció

A teljes A = ⟨Q, Σ, δ, q₀, F⟩ automatára tehát igaz, hogy

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

Források

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