Automi a stati finiti....ho capito bene?

[D4rkAng3l]

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

[Scoperchiatore]

Tutta la roba iniziale non l'ho fatta Considera che io la sto studiando in 4° anno! Difatti è stato un corso semplicissimo, ora il 2°modulo sembra esponenzialmente più complesso

Hai fatto le grammatiche e i linguaggi? Se li avessi fatti, ti sarebbe molto più semplice. Cmq...

Automa: è un oggetto matematico, una quintupla <Sigma, Q, Qo, F, delta> dove

Q: è un insieme finito di stati. Uno stato è rappresentato da una palletta nel grafo Quinid 5 stati vuol dire 5 pallette

SIGMA: è un alfabeto finito di simboli.
Se Sigma = {a,b,c,1} allora vuol dire che stai lavorando per fare in modo che l'autome riconosca un sottoinsieme del linguaggio generato da sigma*(la cui definizione è un po' articolata, ma che sarebbe {a, aa, aaa, aaaa, aab, bba, abbabbababbaba, acacacacaaaaaa, 1111aaaa, 11aaaacacacbbbb... } rendi i simboli del linguaggio, mischiali come vuoi e ripetendoli quanto vuoi, e hai ottenuto tutte le stringhe del linguaggio sigma* ovvero tutte le stringhe che puoi creare con quei 4 simboli: logicamente sono infinite)
L'automa riconosce un sottoinsieme di queste stringhe.

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? SI
Ad esempio: dallo stato qo con i simbolo a vai in q1, con b vai in q2, con c rimani in q0, con 1 vai in q4. La funzione si definisce o in modo formale (come una funzione a due variabili matematica) o con una tabella (dato che il numero di stati è finito, e i caratteri di sigma pure, puoi esplorare tutte le combinazioni statiXsimboli)

q0: stato inziiale...vabbè lo stato di partenza di default? SI, è sempre lo stesso

F: set di stati finali....che è?gli stati che possono essere assunti alla fine?cioè?
Cioè: l'automa funziona così: gli dai una stringa in ingresso appartenente a sigma* (dato il sigma di prima, valgono aaa,aaaaaa,ababababaaabababababab1bababab1ab11111bab o quel che cazzo vuoi formato da a b c 1) e lui riconosce se questa stringa attiene a delle regole di scrittura codificate nell'automa stesso. Se la stringa attiene a queste regole, finisce in uno degli stati finali, e quindi vuol dire che la stringa era "buona" e rispetta le regole che hai deciso TU COSTRUENDO L'AUTOMA. Ricorda che sti automi servono a qualcosa, non si fanno tanto per romperti i coglioni

Facciamo un esempio:



questo automa riconosce alcune stringhe composte di a e b messe come ti pare: precisamente riconosce:

aa, bb, abbba, baaaaaab, abba, baab, ....
mi sembra facile capire come queste stringhe hanno delle proprietà comuni:
se iniziano per a finiscono anche per a ed hanno in mezzo quante b vuoi (anche 0)
se iniziano per b finiscono anche per b ed hanno in mezzo quante a vuoi (anche 0)

ora, se tu inserisci una stringa di QUEL TIPO nell'automa, e segui il percorso mangiandoti le lettere ad una ad una, partendo dalla prima, arrivi a QF, lo stato finale Semplice no? . Parti sempre da Q0 (stato iniziale) indicato con quella freccia (dannata, sbagliai per colpa sua al compito )

Se provi a fare lo stesso con un altro tipo di stringa (ad esempio ab. ma anche abbbab, aaaaa, bbbbb, ovvero stringhe che non appartengono a quello schema che ti ho descritto sopra) non finisci in QF: questo vuoldire che l'automa non la risconosce

I trattini che vanno da a e b di Q2 verso la tabella ti dicono che per compilare quella tabella, ho visto semplicemente l'automa e ho scritto da ogni stato e con ogni simbolo dove arrivo.

Inoltre QP viene spesso chiamato stato pozzo, ovvero uno stato che, se ci arrivi, non ti ci muovi più, perchè hai "sforato" (ovvero, ormai non puoi più rispettare in nessun modo la tipologia di stringa che l'automa accetta)

L'automa lo costruiisci TU, quindi TU decidi cosa farli accettare e cosa no. Quindi ha un senso solo se ti può servire a qualcosa

NON CONFONDERE ciò che riconosce l'automa da sigma*! sigma* è TUTTO quello che si può rappresentare con quei i simboli di sigma, ma l'automa ne riconosce una parte (anche piccola, anche solo una stringa). Può anche riconoscerlo tutto, ma è un caso particolare.

[Scoperchiatore]

edit doppio

[D4rkAng3l]

Grazie mille,
ora mi è tutto molto più chiaro

Ciao
Andrea

[Scoperchiatore]

Originariamente inviato da D4rkAng3l
Grazie mille,
ora mi è tutto molto più chiaro

Ciao
Andrea

Bene, sono contento.
Ora puoi evitare di sprecare preziose energie nello studio degli ASF e dedicarle tutte per litigare con Maxmel riguardo la sua misoginia

[D4rkAng3l]

ahahahah sisisi, però è più importante il voto del secondo esonero che litigare con Maxmel....anche perchè dovrò capire parecchie altre cose sugli automi...grazie mille cmq