[Generico] Automi (DFA, NFA) ed espressioni regolari

[WarDuck]

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



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:



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]

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]

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]

Originariamente inviato da monelli

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 .

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]

Originariamente inviato da WarDuck

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

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

Originariamente inviato da WarDuck

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]

Originariamente inviato da monelli

è 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]

Bon scusa non avevo capito...

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

[WarDuck]

Originariamente inviato da monelli

Bon scusa non avevo capito...

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

Esatto .