^^Automa a stati finiti

automa def formale

5-pla ordinata

A = (I, U, S, f:I×S→U, g: I×S→S) Ingressi, Uscite, Stati, U=f(I,S), S=g(I,S) 

1. I = {i1, i2, …in} insieme finito di ingressi
2. U = {u1, u2, …, um} insieme finito di uscite
3. S = {s1, s2, …, sh} insieme finito di stati
4. f= I×S→U  funzione uscite, che determina l’uscita in funzione valore attuale dell’ingresso e dello stato, u_t=f (s_t, i_t)
5. g= I×S→S funzione transizione (degli stati) che determina lo stato successivo in funzione del valore attuale di ingresso e stato, s_t+1=g(s_t, i_t)

4e5: La combinazione di ingressi e stati IxS determina:

• uscite
• stati successivi.

"A stati finiti/infiniti" l’insieme S degli stati è finito/infinito. Negli automi il numero di ingressi e uscite si considera sempre finito.

Riconosciamo che f e g sono funzioni di 2 variabili.

Condizioni iniziali il suo stato iniziale.

Evoluzione temporale dell'automa e' la successione dei suoi stati.

Per conoscere l'evoluzione dell'automa, bisogna conoscere:

• le sue condizioni iniziali
• i suoi input

raganwald.com/2018/02/23/forde.html

skorks.com/2011/09/why-developers-never-use-state-machines/

The definition of FSM (finite state machine) given in the wikipedia article is too general but does not entail the principles of its functioning. A boolean would be in logic terms only a sequential circuit at best, but definately not a state machine. A finite state machine has M inputs, N outputs, and k bits of state. Furthermore the k-bit feedback bus is not accesseble from the outside.

markshead/state-machines-computer-science

The understanding that finite state machines and regular expressions are functionally equivalent opens up some incredibly interesting uses for regular expression engines–particularly when it comes to creating business rules that can be changed without recompiling a system

Rappresentaz funzione-uscite e funzione-transizione.

Le funzioni di 2 variabili hanno una rpr standard come tabelle a doppia entrata.

Tabella di transizione  1 stato= 1riga, 1 ingresso=1 colonna. Detta anche "matrice degli stati"

Tabella delle uscite

Grafi di transizione  stati= cerchi da ciascuno dei quali partono tanti archi quanti sono gli ingressi.
Se le uscite sono riportate

• sugli archi sotto gli ingressi si dice automa di Mealy
• all’interno dei nodi sotto lo stato si dice automa di Moore.

Cosi' definito, un automa e':

invariante temporale il sistema astratto qui descritto modella l'evoluzione temporale di un sistema reale, ma non dipende esso stesso dal tempo. Es: la tabella di transizione e' sempre quella, non cambia al cambiare del tempo.
I sistemi reali, nella realta' non sono invarianti temporali, poiche' ad es si guastano; una parte del loro comportamento puo' essere modellata come invariante temporale.

discreto purtroppo si e' affermata questa parola, controsenso comune, il cui significato e' semplicemente "non continuo": i valori non variano con continuita', ma saltano da un valore all'altro.

dinamico: descrive l'evoluzione temporale di un sistema.

il sistema astratto qui descritto serve da modello del comportamento di un sistema reale al passare del tempo, ma non dipende esso stesso dal tempo.

Links

wp/State-transition_table

wp/Diagramma_di_stato_(informatica)

wp/List_of_graphical_methods

wp/Data-flow_diagram