Automa a stati finiti

Da Wikipedia, l'enciclopedia libera.

Un automa a stati finiti (ASF) è un sistema dinamico, invariante, discreto nell'avanzamento e nelle interazioni nel quale gli insiemi dei possibili valori di ingresso, uscita e stato sono insiemi finiti.

  • dinamico: evolve nel tempo passando da uno stato all'altro in funzione dei segnali d'ingresso e dello stato precedente;
  • invariante: a parità di condizioni iniziali il comportamento del sistema è sempre lo stesso;
  • discreto: le variabili d'ingresso, di stato, d'uscita, possono assumere solo valori discreti.

L' automa a stati finiti è un modello di calcolo semplice rappresentabile come un piccolo dispositivo, che mediante una testina legge una stringa di input su un nastro e la elabora, facendo uso di un meccanismo molto semplice di calcolo e di una memoria limitata. L'esame della stringa avviene un carattere alla volta attraverso precisi passi computazionali che comportano l'avanzamento della testina. In sostanza un ASF è un caso particolare di macchina di Turing, utilizzato per l'elaborazione di quei linguaggi che nelle Grammatiche di Chomsky sono definiti di Tipo 3 o Regolari. Distinguiamo due tipi di automi a stati finiti: gli automi a stati finiti deterministici (ASFD) e gli automi a stati finiti non deterministici ASFND.

Indice

[modifica] Definizione formale

Un automa finito o anche automa a numero di stati finito (vengono spesso chiamati in modo errato "automi a stati finiti" a causa della traduzione italiano - inglese di FSA (Finite State Automaton) ma la cosa finita non è lo stato ma il numero di stati. Il concetto di stato finito ricorre in meccanica quantistica (spazi di Hilbert) e non ha nulla a che vedere con la nozione di automa finito.

[modifica] Automa a stati finiti deterministico

Per approfondire, vedi la voce automa a stati finiti deterministico.

Un ASF deterministico si definisce come un sistema A = \left \langle I, U, S, f, g \right \rangle, dove

  • I = \{i_1, i_2, \ldots, i_n\} insieme finito dei possibili simboli in ingresso
  • U = \{u_1, u_2, \ldots, u_m\} insieme finito dei possibili simboli in uscita
  • S = \{s_1, s_2, \ldots, s_h\} insieme finito degli stati
  • f: I \times S \rightarrow U funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, U(t) = f(S(t), I(t)) \,\!
  • g: I \times S \rightarrow S funzione di transizione degli stati interni successivi, che collega lo stato nell'istante successivo al valore attuale dell'ingresso e dello stato, S(t+1) = g(S(t), I(t)) \,\!

[modifica] Automa a stati finiti non deterministico

Per approfondire, vedi la voce automa a stati finiti non deterministico.

Un ASF non deterministico si definisce come un sistema A = \left \langle I, U, S, f, g \right \rangle, dove

  • I = \{i_1, i_2, \ldots, i_n\} insieme finito dei possibili simboli in ingresso
  • U = \{u_1, u_2, \ldots, u_m\} insieme finito dei possibili simboli in uscita
  • S = \{s_1, s_2, \ldots, s_h\} insieme finito degli stati
  • f: I \times S \rightarrow U funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, U(t) = f(S(t), I(t)) \,\!
  • g: I \times S \rightarrow \mathcal{P} (S) funzione di transizione parziale degli stati interni successivi, che collega al valore attuale dell'ingresso e dello stato un sottoinsieme di S (quindi ad un sottoinsieme di possibili stati in S).

[modifica] Differenza tra ASFD ed ASFND

Sostanzialmente la differenza tra i due tipi di automi (già espressa dalle definizioni formali) consiste nel fatto che nei primi, in qualunque stato ci si trovi, per un qualsivoglia input, esisterà una ed una sola transizione, mentre nei secondi, almeno uno stato presenta più di una possibile computazione per determinati caratteri in ingresso. Da notare che il determinismo è un caso particolare di non determinismo, tuttavia, nel caso degli automi a stati finiti, è possibile passare agevolmente dall'uno all'altro. L'idea è quella di unire in un unico stato collettivo [s1,s2,...,sk] gli stati s1,s2,...,sk raggiungibili con lo stesso ingresso, ovvero quelli che causano l'indeterminatezza dell'automa.

[modifica] Rappresentazione della funzione di transizione di un ASFD

Diagramma di stato di una macchina di Mealy
Diagramma di stato di una macchina di Moore

Possiamo rappresentare gli automi a stati finiti con una tabella (tabella di transizione) o equivalentemente con una matrice (matrice di transizione). Alle righe associamo gli stati e alle colonne i simboli in input. Gli elementi della matrice rappresentano il risultato dell'applicazione della funzione di transizione.

g a b
s0 s0 s1
s1 s2 s2
s2 s2 s2

Un'altra rappresentazione molto usata è costituita dal diagramma degli stati, o grafo di transizione, che consiste nel rappresentare l'automa mediante un grafo orientato: i nodi rappresentano gli stati e gli archi le transizioni, etichettati col simbolo di input che genera la transizione. Si possono marcare lo stato iniziale con un arco entrante dal nulla, mentre gli stati finali con un doppio circolo.

A queste rappresentazioni poi va aggiunta la funzione di uscita corrispondente, i diagrammi di stato saranno modificati come si può vedere per le macchine di Mealy e di Moore

[modifica] Automa di Mealy e Automa di Moore

Nell'automa di Moore, la funzione f dipende solo dallo stato: f = S → U e dunque U(t) = f(S(t)). La macchina di Moore può essere dunque vista come una semplificazione del caso più generico, dove l'uscita dipende dallo stato e dagli ingressi. Quest'ultimo tipo di automa è detto automa di Mealy.

[modifica] Voci correlate

[modifica] Altri progetti

[modifica] Collegamenti esterni

  • DFA Implementazione, in linguaggio C(open source), di un automa a stati finiti deterministico per il riconoscimento di numeri reali


Teoria degli automi: linguaggi formali e grammatiche formali
Gerarchia di Chomsky Grammatica Linguaggio Automa minimo
Tipo-0 (illimitato) Ricorsivamente enumerabile Macchina di Turing
(illimitato) Ricorsivo Decider
Tipo-1 Sensibile al contesto Sensibile al contesto Automa lineare
Tipo-2 Libero dal contesto Libero dal contesto Automa a pila ND
Tipo-3 Regolare Regolare A stati finiti
Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante.
Estratto da "http://it.wikipedia.org/wiki/Automa_a_stati_finiti"
Strumenti personali