PDA

View Full Version : [Generico] Automi (DFA, NFA) ed espressioni regolari

WarDuck
13-02-2010, 16:03
Ciao ragazzi, mi stavo esercitando un po' con gli automi e le espressioni regolari, tuttavia ho qualche dubbio che spero possiate chiarirmi...

Metto due immagini di un automa da cui estrarre l'espressione regolare, con lo svolgimento da me fatto.

Nel primo caso parto da un NFA (automa non-deterministico) ed estraggo l'espressione regolare che vedete, che stando alla mia interpretazione dovrebbe denotare tutte le sequenze di a e di b che finiscono per a e che presentano un numero di b pari (correggetemi se sbaglio).

Edit: non l'ho specificato ma entrambi gli automi partono dallo stato iniziale A

http://img341.imageshack.us/img341/5558/nfare.png

Edit: correggo, l'espressione regolare è [a*(ba*b)*]*a .

Nel secondo caso ho voluto fare una prova usando un DFA, quindi convertendo l'NFA in DFA:

http://img442.imageshack.us/img442/1125/dfare.png

Edit: correggo anche qui, ho toppato un po' di cose, ripeto i passaggi dal secondo in poi ->

[(e+aa*)(ba*b)]*aa*

su suggerimento di Gio Games: e+aa* = a* dunque ->

[a*(ba*b)]*aa*


La domanda è: queste due espressioni regolari denotano lo stesso linguaggio?

Ho un po' di dubbi anche sul procedimento che ho adottato...
Gio Games
13-02-2010, 17:43
Nel secondo caso credo che

[(e + aa*) (ba*b)]*aa* = [a*(ba*b)]*aa*

dato che (e + aa*) significa che possiamo avere la stringa vuota oppure una o più occorrenze di a, dunque zero o più occorrenze di a, che è la definizione di chiusura di Kleene.
monelli
13-02-2010, 19:33
Io ho dato un esame che non è tanto su sta roba...

Secondo me ottenuti i due DFA controlli le classi di equivalenza...

Se i due DFA sono equivalenti allora denotano lo stesso linguaggio, quindi anche le espressioni regolari denotano lo stesso linguaggio.
WarDuck
13-02-2010, 20:04
Io ho dato un esame che non è tanto su sta roba...

Secondo me ottenuti i due DFA controlli le classi di equivalenza...

Se i due DFA sono equivalenti allora denotano lo stesso linguaggio, quindi anche le espressioni regolari denotano lo stesso linguaggio.

Si la mia intenzione era quella di confrontare i due automi proprio dalle espressioni regolari :D.

Anche perché nn ho ben capito se è possibile applicare lo stesso algoritmo su NFA e DFA, e proprio per questo motivo volevo verificare l'equivalenza tra le due espressioni.

@Gio Games: hai ragione, è possibile ottenere l'espressione che dici (ho corretto).
monelli
13-02-2010, 20:18
Si la mia intenzione era quella di confrontare i due automi proprio dalle espressioni regolari :D.


è più complicato operare sulle espressioni regolari e non sò se si può fare...


Anche perché nn ho ben capito se è possibile applicare lo stesso algoritmo su NFA e DFA, e proprio per questo motivo volevo verificare l'equivalenza tra le due espressioni.

L'algoritmo di equivalenza si applica solo ai DFA. Lo NFA lo devi convertire in DFA e minimizzare... Poi puoi applicare l'algoritmo.
WarDuck
13-02-2010, 20:27
è più complicato operare sulle espressioni regolari e non sò se si può fare...


L'algoritmo di equivalenza si applica solo ai DFA. Lo NFA lo devi convertire in DFA e minimizzare... Poi puoi applicare l'algoritmo.

Io parlo di passare dall'NFA alle RE, ed in realtà l'Hopcroft Ullman lo applica proprio su questi.

Il DFA che vedi nella seconda immagine è derivato dall'NFA della prima immagine. Gli automi dovrebbero essere equivalenti proprio perché ho applicato la power set construction per convertire l'NFA in DFA.

Il mio era un esercizio sulle regular expression.
monelli
13-02-2010, 20:50
Bon scusa non avevo capito...

Tu sei passato dal NFA al DFA, poi vuoi ricavare le espressioni regolari per vedere se sono equivalenti...
WarDuck
13-02-2010, 21:19
Bon scusa non avevo capito...

Tu sei passato dal NFA al DFA, poi vuoi ricavare le espressioni regolari per vedere se sono equivalenti...

Esatto ;).