Costruire l'automa relativo all'espressione regolare

krak2
Costruire un automa a stati finiti denotato dalla seguente espressione regolare:
[(ac)* bbbca (cb)* ab]* U [(bbcc)* (b U a)* abca (ca)*]*

Questo è l'automa che ho ricavato:
http://imageshack.us/photo/my-images/14/8ri9.jpg/
E' corretto?
(la "e" sta per la \(\displaystyle \varepsilon \) di stringa vuota)
Grazie.

Risposte
onlyReferee
Ciao krak!
Starai mica seguendo il corso di linguaggi e compilatori all'università :P ? Scherzi a parte, analizzando la tua immagine, il branch iniziale con $\epsilon$ è corretto. Noto però già un errore nella parte superiore (che deduco debba riconoscere il primo linguaggio): con $(ca)^{\star}$ si intendono tutte le stringhe banali (ossia $\epsilon$ stessa, la stringa vuota) e non generate a partire dalla sequenza di simboli $ca$ (che può essere presa un numero arbitrario di volte anche zero, appunto). Il non determinismo è necessario solo con la epsilon-mossa iniziale. Avevo controllato se per caso si poteva semplificare tutta l'espressione relativa al linguaggio che deve riconoscere l'automa ma non mi pare si possano applicare dei procedimenti a tal fine.
Dopo che ho provato a farlo ti posso dire che uso cinque stati in meno di te ed utilizzo due stati di accettazione. Prova a rivedere il tuo automa alla luce di tutto ciò che così poi lo confrontiamo.
Spero di averti dato qualche consiglio utile.

krak2
Hai indovinato infatti onlyReferee :)
Ho riprovato a farlo, anche se sinceramente alcune cose non mi convincono molto soprattutto nella parte inferiore.
La parte superiore invece come ti sembra adesso?
Ecco l'automa:
http://imageshack.us/photo/my-images/34/e44.JPG/

Sempre grazie dell'aiuto.

onlyReferee
Quasi esatto, krak. Intanto ricorda che l'automa può accettare la stringa vuota (per definizione dell'operatore $\star$). Con la tua versione lo accetta ma devi fare due passaggi in più ergo gli stati 1 e 9 possono già essere di accettazione, no? Inoltre nel "branch" che riconosce la prima parte del linguaggio presta attenzione perché riconoscere $(ac)^{\star}$ è diverso da riconoscere $(a + c)^{\star}$. Lo stesso dicasi per tutte le altre espressioni tipo $(ac)^{\star}$.
Spero di averti fatto comprendere gli errori.

krak2
Ciao onlyReferee,
come al solito grazie al tuo aiuto cerco di capire gli errori che faccio.

Le espressioni del tipo (ac)* è corretto rappresentarle in questo modo?
http://imageshack.us/photo/my-images/30/spo0.JPG/

Dopo di che ho modificato tutto l'automa:
http://imageshack.us/photo/my-images/201/zqn1.jpg/

Come ti sembra adesso? Ci sono errori?
Grazie infinite.

onlyReferee
"krak":
Ciao onlyReferee,
come al solito grazie al tuo aiuto cerco di capire gli errori che faccio.

Di nulla, sempre un piacere.
"krak":

Le espressioni del tipo (ac)* è corretto rappresentarle in questo modo?
http://imageshack.us/photo/my-images/30/spo0.JPG/

No poiché puoi accettare anche la stringa nulla (il tuo automa attualmente non la accetta). Inoltre per ciclare (considerare più volte la stringa $ac$) basta che da 3 ritorni a 2 per mezzo di $a$ senza fare il giro per 4 e 0.
"krak":

Dopo di che ho modificato tutto l'automa:
http://imageshack.us/photo/my-images/201/zqn1.jpg/

Come ti sembra adesso? Ci sono errori?
Grazie infinite.

Non è ancora esatto. Vado di fretta ma noto subito che ci sono ancora gli stati 16 e 33 che non ti servono: la stringa nulla la puoi accettare direttamente in 1 e 17 se ci pensi :P .

krak2
Ciao onlyReferee,
avendo ancora qualche problema con la costruzione degli automi, ne ho disegnato alcuni in modo che capisco dove sbaglio per poter risolvere al meglio quello iniziale.

(ac)*
http://imageshack.us/photo/my-images/545/oe9a.jpg/

(bc)+
http://imageshack.us/photo/my-images/823/r9pu.jpg/

(bbcc)*
http://imageshack.us/photo/my-images/707/g1m6.jpg/

(abcd)+
http://imageshack.us/photo/my-images/547/qxvy.jpg/

(b U a)*
http://imageshack.us/photo/my-images/209/tumm.jpg/

(b U a)+
http://imageshack.us/photo/my-images/845/3b3a.jpg/

Sono corretti?
Grazie mille!

onlyReferee
"krak":

[...]
(ac)*
http://imageshack.us/photo/my-images/545/oe9a.jpg/

Ok.
"krak":

(bc)+
http://imageshack.us/photo/my-images/823/r9pu.jpg/

Ok.
"krak":

(bbcc)*
http://imageshack.us/photo/my-images/707/g1m6.jpg/

No. Quello che hai realizzato te accetta anche la stringa $bc$ che non appartiene a questo linguaggio. Per quanto riguarda l'accettazione della stringa vuota ok. Per il resto bisogna far sì, aggiungendo almeno uno stato in più, che sia generata la stringa $bbcc$ ripetuta un qualsivoglia numero di volte.
"krak":

(abcd)+
http://imageshack.us/photo/my-images/547/qxvy.jpg/

Ok. Si può fare anche in un altro modo (né più semplice né complesso) ma anche quello da te proposto funziona.
"krak":

(b U a)*
http://imageshack.us/photo/my-images/209/tumm.jpg/

Ok.
"krak":

(b U a)+
http://imageshack.us/photo/my-images/845/3b3a.jpg/

Ok.
"krak":

Sono corretti?
Grazie mille!

Di nulla.

krak2
Ciao onlyReferee,
ho modificato la rappresentazione di (bbcc)*
http://imageshack.us/photo/my-images/713/j1sg.jpg/
E' corretto adesso?
Sempre grazie.

onlyReferee
No, non ancora. Con questo nuovo automa puoi generare anche la stringa $bcb$ che però non appartiene al linguaggio che vuoi l'automa riconosca. Il numero degli stati ora è corretto (ne hai quanti bastano per generare le possibili stringhe del linguaggio) ma le frecce (transizioni) ancora no. Pensa bene: bisogna dare la possibilità di ciclare più volte sull'intera stringa non su parti di essa come hai fatto te...

krak2

onlyReferee
No, continui a ciclare rispetto al singolo stato così ed accetti anche stringhe che non appertengono al linguaggio (puoi trovare facilmente numerosi controesempi). Le frecce da uno stato a lui stesso non ti servono. Nello stato 3 la freccia con etichetta $c$ che ti permette di tornare indietro non ti serve, caso mai la puoi far tornare allo stato iniziale (che è l'unico che ti serve anche per l'accettazione alla fin fine). Ti è più chiaro ora?

krak2
Vediamo se adesso è corretto.

(bbcc)*
http://imageshack.us/photo/my-images/820/2gpj.jpg/

onlyReferee
Metti solo 0 come stato d'accettazione (3 non può essere di accettazione), togli le frecce/etichette presenti in 0 e 3 che partono ed arrivano nello stesso stato e così diventa corretto.
PS: che fatica.

krak2
Ciao onlyReferee,
ho ripreso l'espressione regolare iniziale e ho costruito tutto l'automa con la speranza che sia giusto.
Ecco l'automa:
http://imageshack.us/photo/my-images/542/n4pi.jpg/

Grazie mille per la pazienza e aiuto che mi stai dando :oops:

onlyReferee
Di stati di accettazione sono sufficienti soltanto i due che hai più a sinistra (1 e 2, questo mi pareva di averlo accennato già qualche post fa). Noto ancora delle imprecisioni per riconoscere alcune espressioni dei due linguaggi. Consigli: prova di volta in volta a vedere se le stringhe richieste vengono generate correttamente o meno per ciascun linguaggio, poi appena hai fatto tutte le correzioni posti nuovamente...

krak2
Ciao onlyReferee,
come mi hai consigliato, ho fatto tutte le correzioni e questo è l'automa che ho generato:
http://imageshack.us/photo/my-images/10/oqjo.jpg/

(non mi convince molto solo l'espressione \(\displaystyle (bbcc)* \) ,nello specifico l'accettazione della stringa vuota :roll: )

Infinite grazie.

onlyReferee
Allora, partiamo dalla parte superiore, ossia il primo linguaggio. Puoi andare direttamente da 1 a 4 con $a$ (hai messo una epsilon-mossa in più che non serve a nulla). Di conseguenza un ramo può partire direttamente da 1 ed andare a 6 (ti lascio indovinare con che simbolo, è facilissimo). Altra epsilon mossa inutile da 14 a 1 e da 12 a 10 (rivedi in particolare questo ultimo punto).
Passiamo alla parte inferiore. Stati 19 e 20: non ti serve un altro stato per $(a + b)^{\star}$. Da 2 serve una epsilon mossa ma hai bisogno anche di $b$ per generare $(b b c c)^{\star}$. Rivedi anche 25, 26, 27: c'è una epsilon mossa in più.
In buona sintesi diciamo che ti stai avvicinando alla soluzione :D .

krak2
Ciao onlyReferee,
grazie come sempre per il tuo efficace aiuto.

Per la parte superiore, ho risistemato tutto e adesso dovrebbe essere giusto:
http://imageshack.us/photo/my-images/801/m1t3.jpg/

Per quanto riguarda la parte inferiore:
Per gli stati 19 e 20, lo stato in più a cui ti riferisci è l'iterazione di \(\displaystyle b,a \) in 20? e quindi basta semplicemente questo?
http://imageshack.us/photo/my-images/13/m1j5.jpg/

"onlyReferee":
Da 2 serve una epsilon mossa ma hai bisogno anche di $ b $ per generare $ (b b c c)^{\star} $.

Non ho ben capito questo passaggio, nel senso che non so dove ho bisogno di un'altra \(\displaystyle b \)?

onlyReferee
Sei ancora troppo affezionato alle epsilon-mosse :P .
Iniziamo dalla parte superiore. E' quasi giusto... Della epsilon-mossa da 1 a 4 non te ne fai nulla. Inoltre da 1 a 5 ti serve una freccia con una $b$ (la prima parte del primo linguaggio, quella con $(ac)^{\star}$ potrebbe anche produrre una stringa vuota infatti). Lo stesso dicasi per gli stati da 8 a 11: da qui bisogna far partire una freccia con etichetta $a$ (il motivo è lo stesso descritto nella frase precedente). Peccato che non hai messo la freccia da 12 a 1 con etichetta $b$: nella penultima immagine avevi correttamente cancellato la freccia in più ma non avevi collegato quella che puntava allo stato rimosso allo stato d'accettazione, ossia 1.
"krak":

[quote="onlyReferee"]Da 2 serve una epsilon mossa ma hai bisogno anche di $ b $ per generare $ (b b c c)^{\star} $.

Non ho ben capito questo passaggio, nel senso che non so dove ho bisogno di un'altra \(\displaystyle b \)?[/quote]
Intendo dire che una epsilon-mossa ti serve, certo, ma non per entrare nella sequenza di stati che generano $ (b b c c)^{\star} $ (per bypassare eventualmente la generazione di questa stringa).
Forza, ci sei quasi. Ultimo consiglio: aggiungi solo gli stati necessari e costruisci tutto pezzo dopo pezzo verificando se tutto viene generato correttamente.
Figurati per l'aiuto :D .

krak2
Grazie dell'incoraggiamento onlyReferee, mi sta sembrando un parto questo automa, ma prima o poi grazie al tuo aiuto troverò la soluzione corretta :D

Ecco l'automa:
http://imageshack.us/photo/my-images/812/ewcs.jpg/

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.