[LFA] Ultimi dubbi
Clicca QUI per vedere il messaggio nel forum |
| ghily |
C'è qualche anima che riuscirebbe a spiegarmi come si passa da un automi a stati finiti non doterministico ad uno deterministico??
Non riesco a capire come trovare gli stati dell'automa deterministico....
Poi esempio 5.4 a pag.32 delle dispense:
Non dovrebbe essere X0 = aX0 + aX1 + e???
Per il resto sperimao che domani sia buona....
Chao
Roby |
| Bloody |
Provo a risponderti un po' in ritardo ma magari 6 rimandato al 21 come me...
(esempio dei pdf della Palano)
passaggio non deterministico -> deterministico
gli stati dell'automa deterministico sono l'insieme delle parti di quello non deterministico, cioè se tu hai
non det : stati q0, q1
det: q0, q1, q0q1 nello stesso stato, insiemevuoto
Gli stati dell'automa deterministico sono dunque:
- quelli dell'automa non deteministico
- le combinazioni tali che nel non deterministico gli stati, come qui q0 e q1, sono raggiunti dallo stesso segnale partendo dallo stesso stato, che nello schema a pag. 28 qui http://homes.dsi.unimi.it/~palano/cur/lfa-cap2.pdf quello sopra. Entrambi sono raggiunti dal segnale a che parte da q0.
passaggio automa a stati finiti -> espressione regolare
La prima equazione è
X0 = aX1 + bX0 + parolavuota ovvero
<linguaggio con stato iniziale in X0> =
sommatoria di <segnale che parte da X0><stato che quel segnale raggiunge>
difatti b parte da X0 e va in X0, a parte da X0 e va in X1, parolavuota parte da X0 e non raggiunge nulla perchè X0 è stato finale.
spero di non averti confuso troppo le idee.... :ciao: |
|
|
|
