ghily

rozzettino

User info:

Registered: Jul 2003
Posts: 718 (0.09 al dì)
Location: Settimo
Corso: Informatica spec
Anno: 2
Time Online: 13 Days, 1:05:36 [...]
Status: Offline

Post actions:

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

ex universitaria

User info:

Registered: Jan 2003
Posts: 1939 (0.25 al dì)
Location: milano trasferta
Corso: informatica
Anno: dottora :)
Time Online: 49 Days, 2:18:48 [...]
Status: Offline

Post actions:

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.