.dsy:it. (http://www.dsy.it/forum/)
- Linguaggi formali e automi (http://www.dsy.it/forum/forumdisplay.php?forumid=132)
-- [LFA] Ultimi dubbi (http://www.dsy.it/forum/showthread.php?threadid=11528)

[LFA] Ultimi dubbi

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

Re: [LFA] Ultimi dubbi

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....

__________________
I don't care if you're black, white, straight, bisexual, gay, lesbian, short, tall, fat, skinny, rich or poor. If you're nice to me, I'll be nice to you. Simple as that.