Äärellinen automaatti

Finite Automaton
Äärellinen (deterministinen) (puoli)automaatti on systeemi
A = (S, I, f, s0, A)
missä 
S = {si} on äärellinen tilajoukko
I on tarkasteltava aakkosto (ja I* sen sanojen joukko)
f on kuvaus S × I → S, nk. tilansiirtofunktio
s0 ∈ S on alkutila
A ⊆ S on hyväksyvien tai hyväksyttävien tilojen joukko.

Automaatti koostuu siis tiloista ja siirtymistä tilojen välillä. 
Se tutkii käyttäjän antamia syötejonoja (sanoja) aakkonen kerrallaan vasemmalta oikealle, ja joko hyväksyy tai hylkää syötteen. 

Graafisissa esityksissä, nk. tiladiagrammeissa eli siirtymädiagrammeissa kuvaamme ympyröillä tiloja ja kaarilla tilojen välisiä siirtymiä. Hyväksyviä tiloja merkitään kahdella sisäkkäisellä ympyrällä. 
Syöte hyväksytään, mikäli syötteen analysoinnissa päädytään hyväksyvään tilaan, muutoin automaatti hylkää syötteen.

 A finite (deterministic) (semi-)automaton is a system
A = (S, I, f, s0, A)
where 
S = {si} is a finite state set
I is an alphabet set in question (and I* the word set)
f is a function S × I → S, so called state transition
s0 ∈ S is the start state
A ⊆ S is the set of accepting or acceptable states.

So an automaton consists of states and transitions between states.
It inquires alphabet input sequences (words) given by the user, letter by letter from left to right, and either it accepts or rejects the input. 

In graphical representations, so called state diagrams or transition diagrams we denote states by circles and transitions between states by edges (arcs). Accepting states are denotes by double circles. 
An input is accepted if the analysis ends in an accepting state, otherwise the automaton rejects the input.
Esimerkki Example
Alla olevassa automaatissa punaisten pallojen liikkeet kuvaavat siirtymistä tilojen välillä nappeja "a" ja "b" painettaessa ts. kun automaatti saa syötteekseen kirjaimen a tai b. Alkutilanteessa pallot ovat siirtymien lähtöpisteissä ja suunta on vasemmalta oikealle alinta kaarta (jossa siirrytään tilasta s2 tilaan s0) lukuunottamatta. Automaatin alkutila on s0 ja s2 on ainoa hyväksyvä tila.

Testaa, hyväksyykö automaatti syötteen "baa" ja tarkasta "Arvioi"-nappia painamalla, onko valitsemasi tulos oikein.

 In the automaton below the movement of the red balls corresponds transitions between states when the buttons "a" and "b" are pushed, i.e. when the automaton receives a or b as input. In the initial state the balls are at the start of the transition edges and will move from left to right except the lowest transition (in which the direction is from state s2 to s0). The start state is s0 and s2 is the only accepting state.

Test whether this automat accepts the input "baa" and check your choice by pushing the "Arvioi" (evaluate) button.
SYÖTE
INPUT		 HYVÄKSYY
ACCEPT		 HYLKÄÄ
REJECT
baa
Huomautus! Kun siirrytään tilasta toiseen, odota hetki, että animaatio ehtii loppuun asti. Jokaisella napin painalluksella pitäisi tapahtua yksi siirtymä (pallon liike). Jos näin ei käy, paina uudelleen.
 
Note! During the transition wait a while that the animation is finished. By every push of button one transition (ball movement) should happen. If this does not happen, bush the button again.
 
[GeoScript-File] [ GeoStyle-File]

Toinen harjoitus / Another Exercise