Automa a stati finiti
Da Wikipedia, l'enciclopedia libera.
Un automa a stati finiti è un sistema dinamico, invariante, discreto nell'avanzamento e nelle interazioni.
- 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
[modifica] Automa a stati finiti deterministico
Un automa a stati finiti deterministico si definisce come un sistema A = {I, U, S, f, g}, dove
- I = {i1, i2, ... in} è l'insieme finito dei possibili simboli in ingresso
- U = {u1, u2, ..., um} insieme finito dei possibili simboli in uscita
- S = {s1, s2, ..., sh} insieme finito degli stati
- f = I × S → 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 ×S → 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
Un automa a stati finiti non deterministico si definisce come un sistema A = {I, U, S, f, g}, dove
- I = {i1, i2, ... in} è l'insieme finito dei possibili simboli in ingresso
- U = {u1, u2, ..., um} insieme finito dei possibili simboli in uscita
- S = {s1, s2, ..., sh} insieme finito degli stati
- f = I × S → 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 ×S → P(S) funzione di transizione parziale degli stati interni successivi, che collega al valore attuale dell'ingresso e dello stato un sottoinsieme di 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] 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.
| Teoria degli automi: linguaggi formali e grammatiche formali | |||
|---|---|---|---|
| gerarchia di Chomsky |
Grammatiche | Linguaggi | automa minimo |
| Tipo-0 | (illimitato) | Ricorsivamente enumerabile | Macchina di Turing |
| (illimitato) | Ricorsivo | Decider | |
| Tipo-1 | Sensibile al contesto | Sensibile al contesto | Lineare-limitato |
| Tipo-2 | Context-free | Context-free | Automa a pila |
| Tipo-3 | Lineare (o Regolare) | Lineare (o Regolare) | A stati finiti |
| Ciascuna categoria di linguaggio o grammatica è un sottoinsieme del proprio sovrainsieme di categoria direttamente sottostante. | |||
