Costruzione automa minimo
Ciao,
non capisco come si costruisce l'automa minimo.
Per esempio dato questo automa, so che quello minimo è il seguente:
ma non capisco i passaggi. Il prof ha scritto:
$-=^0 {q_0, q_1, q_2, q_3, q_4} {q_5}$ (fin qui ok, ha separato gli stati finali dai non finali)
$-=^1 {q_0} {q_1, q_2} {q_3, q_4} {q_5}$
$-=^2 {q_0} {q_1, q_2} {q_3, q_4} {q_5}$
Gli ultimi due passaggi non li ho capiti.. come divide gli insiemi? che ragionamento fa?
Grazie
PS: chiedo scusa per il disegno penoso ma l'ho fatto in fretta..
non capisco come si costruisce l'automa minimo.
Per esempio dato questo automa, so che quello minimo è il seguente:
ma non capisco i passaggi. Il prof ha scritto:
$-=^0 {q_0, q_1, q_2, q_3, q_4} {q_5}$ (fin qui ok, ha separato gli stati finali dai non finali)
$-=^1 {q_0} {q_1, q_2} {q_3, q_4} {q_5}$
$-=^2 {q_0} {q_1, q_2} {q_3, q_4} {q_5}$
Gli ultimi due passaggi non li ho capiti.. come divide gli insiemi? che ragionamento fa?
Grazie
PS: chiedo scusa per il disegno penoso ma l'ho fatto in fretta..
Risposte
Ciao,
non vedo tutta questa difficoltà. Elimina semplicemente q_2 e q_4 pechè rindondanti (li collassa nello stesso insieme).
non vedo tutta questa difficoltà. Elimina semplicemente q_2 e q_4 pechè rindondanti (li collassa nello stesso insieme).
Scusa ma non ho capito 
Ricapitoliamo: quale sistema ti è stato insegnato per ridurre un automa?
PS. Gli "ultimi due passaggi" che hai indicato sono identici (oppure ho capito male io).
PS. Gli "ultimi due passaggi" che hai indicato sono identici (oppure ho capito male io).
http://www.educ.di.unito.it/~dezani/LP/ ... 6/CAP5.pdf
Queste sono le slide da cui ho studiato.. Gli ultimi due è giusto che siano identici, non so il perchè ma è così.. Se c'è un altro metodo per costruire gli automi minimi, va benissimo
Queste sono le slide da cui ho studiato.. Gli ultimi due è giusto che siano identici, non so il perchè ma è così.. Se c'è un altro metodo per costruire gli automi minimi, va benissimo
Non c'è un 'altro' metodo. Consiglio di leggerti il messaggio
viewtopic.php?f=15&t=64396&start=10#p501031
contenuto nella sezione "Dispense etc" del forum; ivi sono riportati alcuni link verso dispense complete per quanto riguarda linguaggi, automi, parsing et al. Le slides che hai segnalato sono utili per accompagnare una lezione, non certo per studiare l'argomento. Personalmente consiglio le note online di J.Power (inglese).
Tornando al problema: a pagina 4 delle slides c'è scritto come fare, ovvero identificare gli stati equivalenti e metterli assieme. Riesci a vedere (nel tuo esempio) che gli stati q1 e q2 sono equivalenti, come lo sono q3 e q4? Spero di sì... e quindi magari ti stai solamente incartando su un formalismo di "passaggi".
viewtopic.php?f=15&t=64396&start=10#p501031
contenuto nella sezione "Dispense etc" del forum; ivi sono riportati alcuni link verso dispense complete per quanto riguarda linguaggi, automi, parsing et al. Le slides che hai segnalato sono utili per accompagnare una lezione, non certo per studiare l'argomento. Personalmente consiglio le note online di J.Power (inglese).
Tornando al problema: a pagina 4 delle slides c'è scritto come fare, ovvero identificare gli stati equivalenti e metterli assieme. Riesci a vedere (nel tuo esempio) che gli stati q1 e q2 sono equivalenti, come lo sono q3 e q4? Spero di sì... e quindi magari ti stai solamente incartando su un formalismo di "passaggi".
Grazie, gentilissimo.. Allora mi leggo le dispense che mi hai linkato e mi guardo anche gli esercizi. Grazie ancora
Questo è un procedimento scritto nelle dispense linkate:
We base our algorithm on partitioning the states using this criterion.
Initially start with two sets of states: the final, and the non-final states.
For each state-set created by the previous iteration, examine the transitions for each state and each input symbol. If they go to a different state-set for any two states, then these should be put into different state-sets for the next iteration.
We are finished when an iteration creates no new state-sets.
Non so se l'ho capito bene.. Io capisco che inizialmente scrivo in un insieme tutti gli stati finali e in un altro insieme quelli non finali.
Poi prendo ogni stato presente nell'insieme degli stati non finali e guardo in che altro stato va leggendo uno stesso carattere. Gli stati che vanno in stati uguali li metto insieme e gli altri li divido.. E vado avanti così finchè non riesco più a dividere gli insiemi..
Con l'esempio è più chiaro:
1) Il primo insieme rappresenta gli stati non finali, il secondo quelli finali: [size=140]${q_0,q_1,q_2,q_3,q_4}{q_5}$[/size]
2) Ora guardo leggendo il carattere $b$ in quali stati vanno tutti gli stati del primo insieme:
$q_0$ va in $q_1$, $q_1$ va in $q_2$, $q_2$ va in $q_1$, $q_3$ va in $q_5$ e $q_4$ va in $q_5$. Quindi raggruppo gli stati in questo modo: [size=140]${q_0}{q_1,q_2}{q_3,q_4}{q_5}$[/size]
3) Se faccio la stessa cosa sempre leggendo $b$ ottengo sempre${q_0}{q_1,q_2}{q_3,q_4}{q_5}$ quindi termino.
Dubbio: se al passo 2) avessi letto $c$ invece che $b$ avrei ottenuto una cosa diversa... quindi è sbagliato il mio ragionamento?
Grazie
We base our algorithm on partitioning the states using this criterion.
Initially start with two sets of states: the final, and the non-final states.
For each state-set created by the previous iteration, examine the transitions for each state and each input symbol. If they go to a different state-set for any two states, then these should be put into different state-sets for the next iteration.
We are finished when an iteration creates no new state-sets.
Non so se l'ho capito bene.. Io capisco che inizialmente scrivo in un insieme tutti gli stati finali e in un altro insieme quelli non finali.
Poi prendo ogni stato presente nell'insieme degli stati non finali e guardo in che altro stato va leggendo uno stesso carattere. Gli stati che vanno in stati uguali li metto insieme e gli altri li divido.. E vado avanti così finchè non riesco più a dividere gli insiemi..
Con l'esempio è più chiaro:
1) Il primo insieme rappresenta gli stati non finali, il secondo quelli finali: [size=140]${q_0,q_1,q_2,q_3,q_4}{q_5}$[/size]
2) Ora guardo leggendo il carattere $b$ in quali stati vanno tutti gli stati del primo insieme:
$q_0$ va in $q_1$, $q_1$ va in $q_2$, $q_2$ va in $q_1$, $q_3$ va in $q_5$ e $q_4$ va in $q_5$. Quindi raggruppo gli stati in questo modo: [size=140]${q_0}{q_1,q_2}{q_3,q_4}{q_5}$[/size]
3) Se faccio la stessa cosa sempre leggendo $b$ ottengo sempre${q_0}{q_1,q_2}{q_3,q_4}{q_5}$ quindi termino.
Dubbio: se al passo 2) avessi letto $c$ invece che $b$ avrei ottenuto una cosa diversa... quindi è sbagliato il mio ragionamento?
Grazie
"vfldj":
Questo è un procedimento scritto nelle dispense linkate:
We base our algorithm on partitioning the states using this criterion.
Initially start with two sets of states: the final, and the non-final states.
For each state-set created by the previous iteration, examine the transitions for each state and each input symbol. If they go to a different state-set for any two states, then these should be put into different state-sets for the next iteration.
We are finished when an iteration creates no new state-sets.
Non so se l'ho capito bene.. Io capisco che inizialmente scrivo in un insieme tutti gli stati finali e in un altro insieme quelli non finali.
Poi prendo ogni stato presente nell'insieme degli stati non finali e guardo in che altro stato va leggendo uno stesso carattere. Gli stati che vanno in stati uguali li metto insieme e gli altri li divido.. E vado avanti così finchè non riesco più a dividere gli insiemi..
Con l'esempio è più chiaro:
1) Il primo insieme rappresenta gli stati non finali, il secondo quelli finali: [size=140]${q_0,q_1,q_2,q_3,q_4}{q_5}$[/size]
2) Ora guardo leggendo il carattere $b$ in quali stati vanno tutti gli stati del primo insieme:
$q_0$ va in $q_1$, $q_1$ va in $q_2$, $q_2$ va in $q_1$, $q_3$ va in $q_5$ e $q_4$ va in $q_5$. Quindi raggruppo gli stati in questo modo: [size=140]${q_0}{q_1,q_2}{q_3,q_4}{q_5}$[/size]
3) Se faccio la stessa cosa sempre leggendo $b$ ottengo sempre${q_0}{q_1,q_2}{q_3,q_4}{q_5}$ quindi termino.
Dubbio: se al passo 2) avessi letto $c$ invece che $b$ avrei ottenuto una cosa diversa... quindi è sbagliato il mio ragionamento?
Grazie
Up
Per esempio, l'automa minimo di questo automa qual'è?
Dopo aver letto il procedimento a pag. 33 di http://www.cs.unicam.it/tesei/didattica ... 4Total.pdf ho fatto così:
Devo creare un dead state $d$ poichè non tutti gli stati hanno una transizione in un altro stato leggendo tutti i caratteri terminali della grammatica. Infatti, per esempio, li stato $d$ leggendo $0$ non transisce in nessun altro stato quindi lo faccio andare in $d$. Dove lo stato $d$ è uno stato con tre frecce che partono e arrivano sullo stesso $d$ leggendo i caratteri $0, 1$.
Il primo passo è semplicemente dividere gli stati finali da quelli non, quindi:
$-=_0 = {A,B,D,E,F,G,H}{C}$
Per il secondo passaggio faccio:
$move(A,0)=B$
$move(B,0)=G$
$move(D,0)=d$
$move(E,0)=H$
$move(F,0)=C$
$move(G,0)=G$
$move(H,0)=G$
da cui ottengo gli insiemi ${A,B,E,G,H}{D}{F}$ e
$move(A,1)=F$
$move(B,1)=C$
$move(D,1)=G$
$move(E,1)=F$
$move(F,1)=G$
$move(G,1)=E$
$move(H,1)=C$
da cui ottengo gli insiemi ${A,D,E,F,G}{B}{H}$.
Bene, ora mi blocco perchè i due gruppi di insiemi sono diversi, come si procede in questo caso?
PS: nel caso avessi automi con mosse spontanee dovrei fare anche i vari move leggendo $\epsilon$ (esempio $move(X,\epsilon)=Y$)?
Grazie! Sono un pò disperato, non ci capisco nulla di questa materia..
Dopo aver letto il procedimento a pag. 33 di http://www.cs.unicam.it/tesei/didattica ... 4Total.pdf ho fatto così:
Devo creare un dead state $d$ poichè non tutti gli stati hanno una transizione in un altro stato leggendo tutti i caratteri terminali della grammatica. Infatti, per esempio, li stato $d$ leggendo $0$ non transisce in nessun altro stato quindi lo faccio andare in $d$. Dove lo stato $d$ è uno stato con tre frecce che partono e arrivano sullo stesso $d$ leggendo i caratteri $0, 1$.
Il primo passo è semplicemente dividere gli stati finali da quelli non, quindi:
$-=_0 = {A,B,D,E,F,G,H}{C}$
Per il secondo passaggio faccio:
$move(A,0)=B$
$move(B,0)=G$
$move(D,0)=d$
$move(E,0)=H$
$move(F,0)=C$
$move(G,0)=G$
$move(H,0)=G$
da cui ottengo gli insiemi ${A,B,E,G,H}{D}{F}$ e
$move(A,1)=F$
$move(B,1)=C$
$move(D,1)=G$
$move(E,1)=F$
$move(F,1)=G$
$move(G,1)=E$
$move(H,1)=C$
da cui ottengo gli insiemi ${A,D,E,F,G}{B}{H}$.
Bene, ora mi blocco perchè i due gruppi di insiemi sono diversi, come si procede in questo caso?
PS: nel caso avessi automi con mosse spontanee dovrei fare anche i vari move leggendo $\epsilon$ (esempio $move(X,\epsilon)=Y$)?
Grazie! Sono un pò disperato, non ci capisco nulla di questa materia..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo