Costruire l'automa relativo all'espressione regolare
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.
[(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
Ciao krak!
Starai mica seguendo il corso di linguaggi e compilatori all'università
? 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.
Starai mica seguendo il corso di linguaggi e compilatori all'università
? 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.
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.
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.
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.
Spero di averti fatto comprendere gli errori.
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.
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.
"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
.
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!
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!
"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.
Ciao onlyReferee,
ho modificato la rappresentazione di (bbcc)*
http://imageshack.us/photo/my-images/713/j1sg.jpg/
E' corretto adesso?
Sempre grazie.
ho modificato la rappresentazione di (bbcc)*
http://imageshack.us/photo/my-images/713/j1sg.jpg/
E' corretto adesso?
Sempre grazie.
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...
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?
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.
PS: che fatica.
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
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
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...
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
)
Infinite grazie.
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
)Infinite grazie.
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
.
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
.
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/
Non ho ben capito questo passaggio, nel senso che non so dove ho bisogno di un'altra \(\displaystyle b \)?
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 \)?
Sei ancora troppo affezionato alle epsilon-mosse .
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.
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 .
.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
.
Grazie dell'incoraggiamento onlyReferee, mi sta sembrando un parto questo automa, ma prima o poi grazie al tuo aiuto troverò la soluzione corretta
Ecco l'automa:
http://imageshack.us/photo/my-images/812/ewcs.jpg/
Ecco l'automa:
http://imageshack.us/photo/my-images/812/ewcs.jpg/
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
