[RISOLTO !][INFORMATICA TEORICA] Automi con ε transizioni
Ciao a tutti !
vi posto un esercizio con relativa soluzione, purtroppo la prof non sta rispondendo alla mia mail, quindi mi affido a voi
Io tendo a considerare gli stati uniti da ε transizioni come stati unici, quindI:
Lo stato A non dovrebbe riuscire a raggiungere sé stesso attraverso 'b' ?
E lo stato B non dovrebbe riuscire a raggiungere A utilizzando 'b' ?
Ciò è stato fatto ad esempio nello stato D che riesce a raggiungere sé stesso con 'b'.
Sbaglio qualcosa io o effettivamente la ε transizione fra A e B è gestita in maniera diversa rispetto a quella fra C e D ?
Vi ringrazio in anticipo per l'aiuto.
A presto !
vi posto un esercizio con relativa soluzione, purtroppo la prof non sta rispondendo alla mia mail, quindi mi affido a voi
Io tendo a considerare gli stati uniti da ε transizioni come stati unici, quindI:
Lo stato A non dovrebbe riuscire a raggiungere sé stesso attraverso 'b' ?
E lo stato B non dovrebbe riuscire a raggiungere A utilizzando 'b' ?
Ciò è stato fatto ad esempio nello stato D che riesce a raggiungere sé stesso con 'b'.
Sbaglio qualcosa io o effettivamente la ε transizione fra A e B è gestita in maniera diversa rispetto a quella fra C e D ?
Vi ringrazio in anticipo per l'aiuto.
A presto !
Risposte
Ciao Pickeroll 
Rispondo con ordine ai tuoi quesiti.
No perché puoi andare da $A$ a $B$ solo mediante la $\epsilon$-mossa che nel nuovo automa però non esiste più. Per non "perdere" gli stati in cui $A$ finisce tramite tale mossa noti infatti che $B$ è preservato sia per le mosse che partono da $A$ con $a$ che per quelle che partono dal medesimo stato con $b$ (e di conseguenza sono aggiunti anche gli stati per cui si parte da $B$ con $a$ $/$ $b$ alle rispettive transizioni di $A$ con $a$ $/$ $b$)
No, perché
Qui non ti si pone il problema delle $\epsilon$-mosse semplicemente perché B non ne ha e pertanto le transizioni rimangono tali e quali.
Perché bisogna andare a "recuperare" le eventuali $\epsilon$-mosse presente anche a partire dagli stati in cui si arriva, tutto qua. Se noti infatti da $D$ con $b$ vado anche in $C$ e da qui ho la $\epsilon$-mossa che mi riporta a $D$ e pertanto devo "conservarla".
Assolutamente no, spero infatti di averti svelato l'"arcano" che, se ora ti è chiaro, non sarà più tale per te
. Nei casi precedenti non venivano preservate le transazioni che dicevi per il semplice fatto che vedi già che quando capiti in $B$ o in $D$ non ci sono altre $\epsilon$-mosse da preservare (l'insieme delle stesse è vuoto).
Dimmi pure se non hai ancora capito o qualcosa non ti dovesse essere chiaro.
Rispondo con ordine ai tuoi quesiti.
"Pickeroll":
[...]
Io tendo a considerare gli stati uniti da ε transizioni come stati unici, quindI:
Lo stato A non dovrebbe riuscire a raggiungere sé stesso attraverso 'b' ?
[...]
No perché puoi andare da $A$ a $B$ solo mediante la $\epsilon$-mossa che nel nuovo automa però non esiste più. Per non "perdere" gli stati in cui $A$ finisce tramite tale mossa noti infatti che $B$ è preservato sia per le mosse che partono da $A$ con $a$ che per quelle che partono dal medesimo stato con $b$ (e di conseguenza sono aggiunti anche gli stati per cui si parte da $B$ con $a$ $/$ $b$ alle rispettive transizioni di $A$ con $a$ $/$ $b$)
"Pickeroll":
[...]
E lo stato B non dovrebbe riuscire a raggiungere A utilizzando 'b' ?
[...]
No, perché
Qui non ti si pone il problema delle $\epsilon$-mosse semplicemente perché B non ne ha e pertanto le transizioni rimangono tali e quali."Pickeroll":
[...]
Ciò è stato fatto ad esempio nello stato D che riesce a raggiungere sé stesso con 'b'.
[...]
Perché bisogna andare a "recuperare" le eventuali $\epsilon$-mosse presente anche a partire dagli stati in cui si arriva, tutto qua. Se noti infatti da $D$ con $b$ vado anche in $C$ e da qui ho la $\epsilon$-mossa che mi riporta a $D$ e pertanto devo "conservarla".
"Pickeroll":
[...]
Sbaglio qualcosa io o effettivamente la ε transizione fra A e B è gestita in maniera diversa rispetto a quella fra C e D ?
Vi ringrazio in anticipo per l'aiuto.
A presto !
Assolutamente no, spero infatti di averti svelato l'"arcano" che, se ora ti è chiaro, non sarà più tale per te
. Nei casi precedenti non venivano preservate le transazioni che dicevi per il semplice fatto che vedi già che quando capiti in $B$ o in $D$ non ci sono altre $\epsilon$-mosse da preservare (l'insieme delle stesse è vuoto).Dimmi pure se non hai ancora capito o qualcosa non ti dovesse essere chiaro.
Grazie mille, in seguito anche la prof mi ha risposto ed ho capito i miei errori.
Gentilissimo
!
Gentilissimo
!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo