Indietro

ⓘ Automa a stati finiti




Automa a stati finiti
                                     

ⓘ Automa a stati finiti

Un automa a stati finiti o macchina a stati finiti è un tipo di automa che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi. Grazie alla sua semplicità e chiarezza questo modello è molto diffuso nellingegneria e nelle scienze, soprattutto nel campo dellinformatica e della ricerca operativa.

Un automa a stati finiti può essere utilizzato sia per modellare un sistema esistente che per modellare un nuovo sistema formale in grado di risolvere alcuni problemi esistenti. A questultima categoria appartengono i cosiddetti riconoscitori di linguaggi e i traduttori. La rappresentazione grafica di un automa a stati finiti è il grafo.

                                     

1. Descrizione

Nello specifico, con gli automi a stati finiti, si possono modellare tutti i sistemi che possiedono le seguenti caratteristiche:

  • Discretezza: caratteristica che indica che le variabili dingresso e gli stati del sistema da modellare possono essere espressi con valori discreti.
  • Simboli finiti: caratteristica che determina che il numero di simboli di ingresso e di stati sia rappresentabile da un numero finito.
  • Dinamicità: caratteristica di evolvere nel tempo passando da uno stato ad un altro.

Dal punto di vista pratico, il concetto di automa a stati finiti equivale a costruire 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. Lesame della stringa avviene un carattere alla volta attraverso precisi passi computazionali che comportano lavanzamento della testina. In sostanza un ASF è un caso particolare di macchina di Turing, utilizzato per lelaborazione 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.

                                     

2.1. Tipologie Automa a stati finiti deterministico

Un ASF deterministico si definisce come un sistema M = I, U, S, f, g {\displaystyle M=I,U,S,f,g}, dove

  • f: I × S → S {\displaystyle f:I\times S\rightarrow S} funzione di transizione degli stati interni successivi, che collega lo stato nellistante successivo al valore attuale dellingresso e dello stato, S t + 1 = f I t, S t) {\displaystyle St+1=fIt,St)}
  • g: I × S → U {\displaystyle g:I\times S\rightarrow U} funzione delle uscite eventualmente parziale, che collega luscita al valore attuale dellingresso e dello stato, U t = g I t, S t) {\displaystyle Ut=gIt,St)}
  • U = { u 1, u 2, …, u m } {\displaystyle U=\{u_{1},u_{2},\ldots,u_{m}\}} insieme finito dei possibili simboli in uscita
  • S = { s 1, s 2, …, s h } {\displaystyle S=\{s_{1},s_{2},\ldots,s_{h}\}} insieme finito degli stati
  • I = { i 1, i 2, …, i n } {\displaystyle I=\{i_{1},i_{2},\ldots,i_{n}\}} insieme finito dei possibili simboli in ingresso
                                     

2.2. Tipologie Automa a stati finiti non deterministico

Un ASF non deterministico si definisce come un sistema M = I, U, S, f, g {\displaystyle M=I,U,S,f,g}, dove

  • f: I × S → P S {\displaystyle f:I\times S\rightarrow {\mathcal {P}}S} funzione di transizione parziale degli stati interni successivi, che collega al valore attuale dellingresso e dello stato un sottoinsieme di S quindi ad un sottoinsieme di possibili stati in S.
  • S = { s 1, s 2, …, s h } {\displaystyle S=\{s_{1},s_{2},\ldots,s_{h}\}} insieme finito degli stati
  • U = { u 1, u 2, …, u m } {\displaystyle U=\{u_{1},u_{2},\ldots,u_{m}\}} insieme finito dei possibili simboli in uscita
  • I = { i 1, i 2, …, i n } {\displaystyle I=\{i_{1},i_{2},\ldots,i_{n}\}} insieme finito dei possibili simboli in ingresso
  • g: I × S → U {\displaystyle g:I\times S\rightarrow U} funzione delle uscite eventualmente parziale, che collega luscita al valore attuale dellingresso e dello stato, U t = f S t, I t) {\displaystyle Ut=fSt,It)}


                                     

2.3. Tipologie Differenza tra ASFD ed ASFND

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 qualsiasi 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 dalluno allaltro. Lidea è quella di unire in un unico stato collettivo gli stati s 1,s 2.,s k raggiungibili con lo stesso ingresso, ovvero quelli che causano lindeterminatezza dellautoma.

                                     

3. Rappresentazione della funzione di transizione di un ASFD

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

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

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

                                     

4. Relazioni con altri tipi di macchine

Reti di Petri

Un ASF può essere considerato un tipo particolare di rete di Petri.

Automa di Mealy e Automa di Moore

Nellautoma di Moore, la funzione f dipende solo dallo stato: f = S → U e dunque Ut = fSt). La macchina di Moore può essere dunque vista come una semplificazione del caso più generico, dove luscita dipende dallo stato e dagli ingressi. Questultimo tipo di automa è detto automa di Mealy.

                                     

5. Varie

  • Gli automi finiti, o anche automi a numero di stati finito, vengono spesso chiamati in modo errato "automi a stati finiti" a causa della traduzione inglese - italiano di FSA, ma non è lo stato ad essere finito, bensì il numero degli stati. Il concetto di stato finito ricorre in meccanica quantistica e non ha nulla a che vedere con la nozione di automa finito.
                                     
  • calcolo, un automa a stati finiti non deterministico ASFND, in inglese nondeterministic finite automaton, NFA è una macchina a stati finiti dove per ogni
  • teoria del calcolo, un automa a stati finiti deterministico ASFD o deterministic finite automaton DFA è un automa a stati finiti dove per ogni coppia
  • complessità di un automa è raggiunto dalla macchina di Turing, modello che generalizza gli automi a pila e a fortiori gli automi a stati finiti Un sottoassieme
  • macchina di Mealy è un automa a stati finiti i cui valori di uscita sono determinati dallo stato attuale e dall ingresso corrente, a differenza della macchina
  • gerarchia di Chomsky o accettato da un automa a stati finiti automa a stati finiti deterministico o automa a stati finiti non deterministico L insieme dei
  • Un automa a pila o Push Down Automa PDA è un tipo di macchina astratta, in particolare un automa la cui memoria di lavoro è costituita da una pila
  • macchina di Moore è un automa a stati finiti in cui le uscite sono determinate in funzione dei soli stati correnti e non anche dagli stati d ingresso, come
  • costruzione dell automa a stati finiti deterministico equivalente ad un automa a stati finiti non deterministico. Dato un automa a stati finiti non deterministico
  • in Java. JFLAP permette la conversione da automa a stati finiti non deterministico in automa a stati finiti deterministico, in grammatica formale o in
  • automa cellulare consiste di una griglia costituita da celle, per esempio un foglio a quadretti. La griglia può avere una qualunque dimensione finita
  • Teoria degli automi branca dell Informatica è detto minimizzazione di un DFA il procedimento che trasforma un dato automa a stati finiti deterministico