Täydellinen automaatti

Äärellisen automaatin perusmääritelmässä ei vaadita, että jokaisesta tilasta on siirtymä jokaiselle symbolille. Täydellinen automaatti on automaatti, jossa on määritelty siirtymät kaikista tiloista kaikille syöteaakkoston symboleille.

Täydellisen automaatin rakentaminen

Olkoon meillä automaatti A = (Q, Σ, δ, q₀, F):

Tässä ei ole piirretty siirtymää tilasta q₀ kirjaimelle ”b”. Jos tällainen tilanne tulee vastaan, sanomme, että automaatti ei hyväksy annettua syötesanaa. Formalisoinnin kannalta ei kuitenkaan välttämättä ole sopivaa, että siirtymäfunktiota δ ei ole määritelty joillekin arvoille; tässä se ei ole määritelty esimerkiksi arvolle δ(q₀, b).

Tämän voi helposti korjata rakentamalla ekvivalentin automaatin, jossa on yksi ylimääräinen tila — siihen johtavat ”puuttuvat” siirtymät, tämä tila ei ole lopputila, ja kaikki jatkosyötteet kiertävät tässä tilassa. Kutsumme tätä automaattia täydelliseksi automaatiksi. Muokattu ekvivalentti automaatti voisi näyttää tältä:

Lisäsimme tilan q_fail. Muista tiloista johtaa siihen siirtymä täsmälleen silloin, kun siirtymää ei aiemmin ollut. Tämä tila ei ole lopputila, ja se kiertää kaikilla jatkosyötteillä. Tässä automaatissa ei ole yhtään puuttuvaa siirtymää: siellä, missä edellisessä automaatissa olisi tullut vastaan puuttuva siirtymä, tämä automaatti päätyy tilaan q_fail.

Voimme siis aina yleisyyttä menettämättä olettaa, että automaatissa on määritelty siirtymät kaikille tilojen ja aakkoston merkkien yhdistelmille.

Määritelmä

Täydelliselle automaatille A = (Q, Σ, δ, q₀, F) siis pätee

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

Lähteet

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