Minimizzare un automa a stati finiti
Ciao a tutti, sto cercando di capire come si minimizza un automa.
Ho trovato questo sito (http://www.inrialpes.fr/vasy/people/Gor ... imise.html) dove viene spiegato molto bene
Penso di aver capito la "teoria" ma quando ho cercato di fare l'esempio li proposto ho notato qualcosa di sbagliato nel mio ragionamento
Allo step 3 c'è scritto che la matrice D(0) è:
$$\begin{array} {|r|r|}
\hline
F & T & F & F \\
\hline
T & T & T & T \\
\hline
F & T & F & F \\
\hline
F & T & F & F \\
\hline
\end{array}$$
Ma a me viene questa matrice qui, diversa dalla sua:
$$\begin{array} {|r|r|}
\hline
D(0) & 1 & 2 & 3 & 4\\
\hline
1 & T & T & F & F \\
\hline
2 & T & T & T & T \\
\hline
3 & F & T & T & F \\
\hline
4 & F & T & F & T \\
\hline
\end{array}$$
Dove sbaglio?
Grazie
Ho trovato questo sito (http://www.inrialpes.fr/vasy/people/Gor ... imise.html) dove viene spiegato molto bene
Penso di aver capito la "teoria" ma quando ho cercato di fare l'esempio li proposto ho notato qualcosa di sbagliato nel mio ragionamento
Allo step 3 c'è scritto che la matrice D(0) è:
$$\begin{array} {|r|r|}
\hline
F & T & F & F \\
\hline
T & T & T & T \\
\hline
F & T & F & F \\
\hline
F & T & F & F \\
\hline
\end{array}$$
Ma a me viene questa matrice qui, diversa dalla sua:
$$\begin{array} {|r|r|}
\hline
D(0) & 1 & 2 & 3 & 4\\
\hline
1 & T & T & F & F \\
\hline
2 & T & T & T & T \\
\hline
3 & F & T & T & F \\
\hline
4 & F & T & F & T \\
\hline
\end{array}$$
Dove sbaglio?
Grazie
Risposte
Ciao vfldj 
Nello step 3 bisogna che consideri se nelle varie coppie di stati ve ne è uno ed uno solo che è stato finale nel tuo automa. In tal caso metti $T$ nella corrispondente cella della matrice, altrimenti $F$. Banalmente ci si accorge subito che le celle $D_{i, i}$ (diagonale principale della matrice) saranno sempre $F$. Per gli altri stati basta che procedi un passo per volta verificando le varie coppie di stati. Ad esempio le coppie $D_{2, i}, i \ne 2$ saranno tutte $T$ poiché $2$ è stato finale, Puoi velocizzare la scrittura della matrice notando che la stessa è simmetrica.
Spero di esserti stato d'aiuto.
Nello step 3 bisogna che consideri se nelle varie coppie di stati ve ne è uno ed uno solo che è stato finale nel tuo automa. In tal caso metti $T$ nella corrispondente cella della matrice, altrimenti $F$. Banalmente ci si accorge subito che le celle $D_{i, i}$ (diagonale principale della matrice) saranno sempre $F$. Per gli altri stati basta che procedi un passo per volta verificando le varie coppie di stati. Ad esempio le coppie $D_{2, i}, i \ne 2$ saranno tutte $T$ poiché $2$ è stato finale, Puoi velocizzare la scrittura della matrice notando che la stessa è simmetrica.
Spero di esserti stato d'aiuto.
"onlyReferee":
Ciao vfldj
Nello step 3 bisogna che consideri se nelle varie coppie di stati ve ne è uno ed uno solo che è stato finale nel tuo automa. In tal caso metti $T$ nella corrispondente cella della matrice, altrimenti $F$. Banalmente ci si accorge subito che le celle $D_{i, i}$ (diagonale principale della matrice) saranno sempre $F$. Per gli altri stati basta che procedi un passo per volta verificando le varie coppie di stati. Ad esempio le coppie $D_{2, i}, i \ne 2$ saranno tutte $T$ poiché $2$ è stato finale, Puoi velocizzare la scrittura della matrice notando che la stessa è simmetrica.
Spero di esserti stato d'aiuto.
Mi sento un deficiente.. Ho sbagliato io... Comunque grazie!
Stai sereno, può capitare 
.
Di nulla, chiedi pure se hai bisogno.
.Di nulla, chiedi pure se hai bisogno.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo