Automi a stati finit...ho capito bene?

D4rkAng3l · 12-12-2004, 11:37

Ciao e grazie a tutti coloro che potranno aitarmi.
All'uni (informatica) stò studiando gli automi a stiati finiti nel corso di architetture 1 e sono un po' inguaiato perchè a causa dei ritardi provocati dagli scioperi l'assistente ha dovuto spiegare in 2 ore che cos'è un circuito sequenziale, teoria base degli automi, macchine di mealy e macchine di moore, passaggio dall'una all'altra e viceversa e minimizzazioni di tali macchine...stò per suicidarmi....

Ditemi se ho capito bene quello che mi sono riletto sulle dispense fino ad ora....

1) Un circuito sequenziale detto I(t) l'insieme degli input in un certo tempo t, O(t) lin'insieme degli output in quel tempo t, ed M una funzione di I(t-1),I(t-2),.....I(t-n) detta memoria...allora ho

o(i) = F(I(t), M(t)) considerando o(i) € O cioè o(i) è solo un uscita e non l'insieme delle uscite...

Vabbè tutta questa pappardella semplicemente per dire che in una macchina combinatoria l'output ad un tempo t dipende sia dagli ingressi al tempo t sia dagli ingressi immessi precedentemente...

Se voglio fare un circuito che se riceve in ingresso 0 produce in uscia 0, ma se riceve in ingresso 1 produce in uscita 1 solo se l'input precedente era 1...
Faccio la tabella:

I(t) I(t-1) O(t)
0 0 0
0 1 0
1 0 0
1 1 1

e faccio una funzione combinatoria AND tra l'ingresso attuale I(t) e il valore dell'ingresso precedente presente in memoria M(t)=I(t-1)

Fino quà credo di aver capito...ditemi voi se ho sparato qualche minchiata....

Il problema SERIO per me sono questi maledetti automi a stati finiti....

Da quello che ho capito sono un modello per rappresentare un sistema con input e output finiti e il sistema può trovarsi in differenti STATI che rappresentano la condizione in cui si trova il sistema in un preciso momento considerando gli input precedentemente ricevuti dal sistema...oddio mi sa che è un po' impicciato...giusto come concetto?

Per esempio se voglio fare un circuito che riconosce stringhe contenenti la sequenza 001 oltre al valore correntemente immesso ho i 2 valori precedenti che devono essere memorizzati perchè potrebbero trovarsi in condizioni differenti....in questo caso gli stati sono 2 per M=I(t-1)=0 e per M=I(t-1)=1

In un automa a stati finiti devo sapere lo stato in cui si trova il sistema in un determinato momento per determinare il comportamento a fronte di successivi input....e quando gli arriva un nuovo input con il modello a pallette degli automi posso vedere facilmente in che altro stato transita tenedno conto della storia dei precedenti input...giusto?

La cosa che proprio non mi entra nella capoccia è la definizione formale di automa a stati finiti....cioè magari l'ho pure capita ma non riesco a fissarla....

Da quello che so è una quintupla (Q,SIGMA,delta, q0,F) dove:

Q: è un insieme finito di stati...ma è l'insieme di stati che può assumere il mio grafico a pallette? Il numero di pallette per inenderci?

SIGMA: è un alfabeto finito di simboli...sarebbe i simboli che possono arrivargli in input? Per esempio nell'esempio del riconoscitore di stringhe 001 i valori o 0 o 1 che gli arrivano in input?

delta: Funzione di transizione...sarebbe la funzione che gli dice dato un determinato astato e un determinato simbolo in input ai a ques'taltro stato?

q0: stato inziiale...vabbè lo stato di partenza di default?

F: set di stati finali....che è?gli stati che possono essere assunti alla fine?cioè?

Oddio è un po' lungo...grazie a tutti..stò in paranoia....il primo esnoero dovrebbe essere andato bene e non vorrei non passare ils econdo...questa parte la odio...non m'entra

^TiGeRShArK^ · 12-12-2004, 19:33

ah quanti bei ricordi....
dunque l'insieme degli stati rappresenta TUTTI gli stati ke può assumere il tuo automa...non ho capito ke intendi con le pallette, cmq vedo si spiegarlo meglio + avanti...
x Sigma hai capito, è, se non ricordo male, i possibili valori che possono essere utilizzati dal tuo automa....
delta gli dice COME effettuare la transizione....
ad esempio tu sei in uno stato A e viene verificata la condizione alpha..... nell'elenco delle transizioni di stato di A prima avevi specificato ke non appena viene verificata la condizione alpha lo stato dell'automa deve diventare B, allora in questo caso al verificarsi della condizione il sistema passerà allo stato B. Non è detto ke ciò debba sempre avvenire.... se 6 nello stato C può essere ke hai definito delta(alpha) in modo da andare allo stato E.... e così via...
ogni stato ha la sua definizione delle transizioni.
Q0 è lo stato in cui si trova il sistema alla sua creazione, mentre lo stato (o gli stati) finali sono quelli ke fanno terminare l'agente non appena esso si trovi in uno di questi stati.

Gli automi a stati finiti sono uno strumente ESTREMAMENTE potente per ... i parser dei compilatori possono essere programmati usando automi a stati finiti....

Ora provo a farti un esempio (se riesco)...
devi scrivere un programma ke ti dica se in un distributore di sigarette l'importo è corretto, e accetta solo le monete per arrivare al totale, dato ke non torna resto...
Sei nello stato iniziale di attesa, hai a disposizione varie possibilità: 1€, 2€, 50c, 20c, 10c viene messa una monetina da 2€, quindi passi allo stato 2EURO, in cui viene incrementato il contatore totale di 2. A questo punto hai come possibilità solo 1€, 50c, 20c, 10c. Metti 1€, quindi passi allo stato 1EURO. Il totale viene incrementato di 1 e le possibilità sono 50c, 20c, 10c. A questo punto metti 50c e passando allo stato 50CENT sei arrivato al totale. Ci sarà una condizione ke dice ke quando totale=3.50 passi allo stato EROGAZIONE_MARLBORO_ROSSE

, qui il distributore ti da le sigarette, e quindi il sistema viene fatto tornare allo stato iniziale.
In questo particolare esempio non ci sono stati finali canonici, dato ke l'automa deve restare sempre in ciclo continuo.

Spero ke si sia capito qualcosa dato ke sono scarsissimo a spiegare.... e l'esempio era dovuto dato ke ho finito le marlboro e devo andarle a comprare + tardi

beppegrillo · 12-12-2004, 19:49

CROSS POSTING
hai capito bene

^TiGeRShArK^ · 13-12-2004, 00:13

beppegrillo · 13-12-2004, 00:16

Quote:

Originariamente inviato da ^TiGeRShArK^

http://forum.hwupgrade.it/showthread...hreadid=834652

^TiGeRShArK^ · 13-12-2004, 10:48

ah! ora ho capito

cionci · 13-12-2004, 17:14

E si chiude

12-12-2004, 11:37	#1
D4rkAng3l Bannato Iscritto dal: Mar 2004 Città: Roma Messaggi: 2688	Automi a stati finit...ho capito bene? Ciao e grazie a tutti coloro che potranno aitarmi. All'uni (informatica) stò studiando gli automi a stiati finiti nel corso di architetture 1 e sono un po' inguaiato perchè a causa dei ritardi provocati dagli scioperi l'assistente ha dovuto spiegare in 2 ore che cos'è un circuito sequenziale, teoria base degli automi, macchine di mealy e macchine di moore, passaggio dall'una all'altra e viceversa e minimizzazioni di tali macchine...stò per suicidarmi.... Ditemi se ho capito bene quello che mi sono riletto sulle dispense fino ad ora.... 1) Un circuito sequenziale detto I(t) l'insieme degli input in un certo tempo t, O(t) lin'insieme degli output in quel tempo t, ed M una funzione di I(t-1),I(t-2),.....I(t-n) detta memoria...allora ho o(i) = F(I(t), M(t)) considerando o(i) € O cioè o(i) è solo un uscita e non l'insieme delle uscite... Vabbè tutta questa pappardella semplicemente per dire che in una macchina combinatoria l'output ad un tempo t dipende sia dagli ingressi al tempo t sia dagli ingressi immessi precedentemente... Se voglio fare un circuito che se riceve in ingresso 0 produce in uscia 0, ma se riceve in ingresso 1 produce in uscita 1 solo se l'input precedente era 1... Faccio la tabella: I(t) I(t-1) O(t) 0 0 0 0 1 0 1 0 0 1 1 1 e faccio una funzione combinatoria AND tra l'ingresso attuale I(t) e il valore dell'ingresso precedente presente in memoria M(t)=I(t-1) Fino quà credo di aver capito...ditemi voi se ho sparato qualche minchiata.... Il problema SERIO per me sono questi maledetti automi a stati finiti.... Da quello che ho capito sono un modello per rappresentare un sistema con input e output finiti e il sistema può trovarsi in differenti STATI che rappresentano la condizione in cui si trova il sistema in un preciso momento considerando gli input precedentemente ricevuti dal sistema...oddio mi sa che è un po' impicciato...giusto come concetto? Per esempio se voglio fare un circuito che riconosce stringhe contenenti la sequenza 001 oltre al valore correntemente immesso ho i 2 valori precedenti che devono essere memorizzati perchè potrebbero trovarsi in condizioni differenti....in questo caso gli stati sono 2 per M=I(t-1)=0 e per M=I(t-1)=1 In un automa a stati finiti devo sapere lo stato in cui si trova il sistema in un determinato momento per determinare il comportamento a fronte di successivi input....e quando gli arriva un nuovo input con il modello a pallette degli automi posso vedere facilmente in che altro stato transita tenedno conto della storia dei precedenti input...giusto? La cosa che proprio non mi entra nella capoccia è la definizione formale di automa a stati finiti....cioè magari l'ho pure capita ma non riesco a fissarla.... Da quello che so è una quintupla (Q,SIGMA,delta, q0,F) dove: Q: è un insieme finito di stati...ma è l'insieme di stati che può assumere il mio grafico a pallette? Il numero di pallette per inenderci? SIGMA: è un alfabeto finito di simboli...sarebbe i simboli che possono arrivargli in input? Per esempio nell'esempio del riconoscitore di stringhe 001 i valori o 0 o 1 che gli arrivano in input? delta: Funzione di transizione...sarebbe la funzione che gli dice dato un determinato astato e un determinato simbolo in input ai a ques'taltro stato? q0: stato inziiale...vabbè lo stato di partenza di default? F: set di stati finali....che è?gli stati che possono essere assunti alla fine?cioè? Oddio è un po' lungo...grazie a tutti..stò in paranoia....il primo esnoero dovrebbe essere andato bene e non vorrei non passare ils econdo...questa parte la odio...non m'entra

12-12-2004, 19:33	#2
^TiGeRShArK^ Senior Member Iscritto dal: Jul 2002 Città: Reggio Calabria -> London Messaggi: 12112	ah quanti bei ricordi.... dunque l'insieme degli stati rappresenta TUTTI gli stati ke può assumere il tuo automa...non ho capito ke intendi con le pallette, cmq vedo si spiegarlo meglio + avanti... x Sigma hai capito, è, se non ricordo male, i possibili valori che possono essere utilizzati dal tuo automa.... delta gli dice COME effettuare la transizione.... ad esempio tu sei in uno stato A e viene verificata la condizione alpha..... nell'elenco delle transizioni di stato di A prima avevi specificato ke non appena viene verificata la condizione alpha lo stato dell'automa deve diventare B, allora in questo caso al verificarsi della condizione il sistema passerà allo stato B. Non è detto ke ciò debba sempre avvenire.... se 6 nello stato C può essere ke hai definito delta(alpha) in modo da andare allo stato E.... e così via... ogni stato ha la sua definizione delle transizioni. Q0 è lo stato in cui si trova il sistema alla sua creazione, mentre lo stato (o gli stati) finali sono quelli ke fanno terminare l'agente non appena esso si trovi in uno di questi stati. Gli automi a stati finiti sono uno strumente ESTREMAMENTE potente per ... i parser dei compilatori possono essere programmati usando automi a stati finiti.... Ora provo a farti un esempio (se riesco)... devi scrivere un programma ke ti dica se in un distributore di sigarette l'importo è corretto, e accetta solo le monete per arrivare al totale, dato ke non torna resto... Sei nello stato iniziale di attesa, hai a disposizione varie possibilità: 1€, 2€, 50c, 20c, 10c viene messa una monetina da 2€, quindi passi allo stato 2EURO, in cui viene incrementato il contatore totale di 2. A questo punto hai come possibilità solo 1€, 50c, 20c, 10c. Metti 1€, quindi passi allo stato 1EURO. Il totale viene incrementato di 1 e le possibilità sono 50c, 20c, 10c. A questo punto metti 50c e passando allo stato 50CENT sei arrivato al totale. Ci sarà una condizione ke dice ke quando totale=3.50 passi allo stato EROGAZIONE_MARLBORO_ROSSE , qui il distributore ti da le sigarette, e quindi il sistema viene fatto tornare allo stato iniziale. In questo particolare esempio non ci sono stati finali canonici, dato ke l'automa deve restare sempre in ciclo continuo. Spero ke si sia capito qualcosa dato ke sono scarsissimo a spiegare.... e l'esempio era dovuto dato ke ho finito le marlboro e devo andarle a comprare + tardi __________________

12-12-2004, 19:49	#3
beppegrillo Senior Member Iscritto dal: Mar 2004 Messaggi: 1455	CROSS POSTING hai capito bene __________________ Ciao ~ZeRO sTrEsS~

13-12-2004, 00:13	#4
^TiGeRShArK^ Senior Member Iscritto dal: Jul 2002 Città: Reggio Calabria -> London Messaggi: 12112	__________________

13-12-2004, 10:48	#6
^TiGeRShArK^ Senior Member Iscritto dal: Jul 2002 Città: Reggio Calabria -> London Messaggi: 12112	ah! ora ho capito __________________

13-12-2004, 17:14	#7
cionci Senior Member Iscritto dal: Apr 2000 Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29 Messaggi: 53971	E si chiude

Strumenti
Mostra una versione stampabile Invia questa pagina per email