Costruire automa che accetti un determinato linguaggio
Salve a tutti,
avrei bisogno di un aiuto col seguente esercizio:
Costruire un automa a stati finiti che accetti il linguaggio L formato da tutte le stringhe sull'alfabeto {a,b,c} che iniziano con il simbolo "c" e terminano con il simbolo "a" e contengono esattamente tre occorrenze del simbolo "a".
Io l'ho svolto così:
http://imageshack.us/photo/my-images/36/this.JPG/
è corretta come soluzione?
Grazie.
avrei bisogno di un aiuto col seguente esercizio:
Costruire un automa a stati finiti che accetti il linguaggio L formato da tutte le stringhe sull'alfabeto {a,b,c} che iniziano con il simbolo "c" e terminano con il simbolo "a" e contengono esattamente tre occorrenze del simbolo "a".
Io l'ho svolto così:
http://imageshack.us/photo/my-images/36/this.JPG/
è corretta come soluzione?
Grazie.
Risposte
Ciao krak!
Un piacere rivederti
. L'automa è molto più semplice di quanto immagini. Innanzitutto ti faccio notare che, date le specifiche richieste, $\epsilon$ (la stringa vuota) non appartiene al linguaggio che l'automa deve riconoscere e pertanto la transazione da 0 a 5 di sicuro non c'è. Secondo punto: una volta che noi abbiamo avuto in input $c$ da 1 (ossia il carattere iniziale della stringa) abbiamo interesse a sapere quante $b$ e $c$ verranno inserite? Chiaramente no poiché noi vogliamo essere sicuri che siano inserite esattamente tre $a$ di cui una di queste deve trovarsi in posizione finale della stringa. A questo punto ti chiederai se lo stato 3 che hai inserito sia realmente necessario o meno. Ti lascio pensare intanto.
Spero di averti dato un aiuto.
Un piacere rivederti
. L'automa è molto più semplice di quanto immagini. Innanzitutto ti faccio notare che, date le specifiche richieste, $\epsilon$ (la stringa vuota) non appartiene al linguaggio che l'automa deve riconoscere e pertanto la transazione da 0 a 5 di sicuro non c'è. Secondo punto: una volta che noi abbiamo avuto in input $c$ da 1 (ossia il carattere iniziale della stringa) abbiamo interesse a sapere quante $b$ e $c$ verranno inserite? Chiaramente no poiché noi vogliamo essere sicuri che siano inserite esattamente tre $a$ di cui una di queste deve trovarsi in posizione finale della stringa. A questo punto ti chiederai se lo stato 3 che hai inserito sia realmente necessario o meno. Ti lascio pensare intanto.Spero di averti dato un aiuto.
Piacere mio onlyReferee 
in effetti non mi interessa sapere quante \(\displaystyle b \) e \(\displaystyle c \) verranno inserite, e quindi potrei rappresentare l'automa direttamente con il linguaggio finale richiesto? cioè:
http://imageshack.us/photo/my-images/845/a5vr.jpg/
Il mio dubbio è, siccome nell'esercizio dice che il linguaggio L è formato dalle stringhe sull'alfabeto {a,b,c,} e quindi è necessario far comparire \(\displaystyle b \) nell'automa? oppure posso anche omettere la rappresentazione di \(\displaystyle b \) (dato che non mi serve) e produrre l'automa come nel link sopra?
Sempre grazie.
in effetti non mi interessa sapere quante \(\displaystyle b \) e \(\displaystyle c \) verranno inserite, e quindi potrei rappresentare l'automa direttamente con il linguaggio finale richiesto? cioè:
http://imageshack.us/photo/my-images/845/a5vr.jpg/
Il mio dubbio è, siccome nell'esercizio dice che il linguaggio L è formato dalle stringhe sull'alfabeto {a,b,c,} e quindi è necessario far comparire \(\displaystyle b \) nell'automa? oppure posso anche omettere la rappresentazione di \(\displaystyle b \) (dato che non mi serve) e produrre l'automa come nel link sopra?
Sempre grazie.
Ciao krak!
No, l'automa che mi hai presentato nell'ultima immagine non ha senso se ci pensi: questo automa riconosce una ed una sola stringa, ossia $caaa$
Ha senso secondo te costruire un automa che accetta una sola stringa anziché tutte le possibili stringhe generabili a partire da un dato linguaggio L 
Evidentemente la risposta è no.
Quando ti viene dato un alfabeto a partire dal quale si vogliono costruire delle stringhe secondo dei vincoli appositi dati appunto dal linguaggio che si vuole riconoscere l'importante è rispettare questi. In ogni momento però puoi avere potenzialmente in input tutti i simboli appartenenti al tuo alfabeto. E' più chiaro adesso
No, l'automa che mi hai presentato nell'ultima immagine non ha senso se ci pensi: questo automa riconosce una ed una sola stringa, ossia $caaa$
Ha senso secondo te costruire un automa che accetta una sola stringa anziché tutte le possibili stringhe generabili a partire da un dato linguaggio L Evidentemente la risposta è no.Quando ti viene dato un alfabeto a partire dal quale si vogliono costruire delle stringhe secondo dei vincoli appositi dati appunto dal linguaggio che si vuole riconoscere l'importante è rispettare questi. In ogni momento però puoi avere potenzialmente in input tutti i simboli appartenenti al tuo alfabeto. E' più chiaro adesso
Ciao onlyReferee,
si adesso mi è un pò più chiaro.
Ho ridisegnato l'automa in modo che adesso si ha la possibilità di avere in input anche le altre lettere.
Ecco l'automa:
http://imageshack.us/photo/my-images/585/ycgu.jpg/
Sempre grazie.
si adesso mi è un pò più chiaro.
Ho ridisegnato l'automa in modo che adesso si ha la possibilità di avere in input anche le altre lettere.
Ecco l'automa:
http://imageshack.us/photo/my-images/585/ycgu.jpg/
Sempre grazie.
Perfetto, krak! Questa volta l'automa era molto piú semplice dell'ultimo che mi hai proposto e difatti arrivare al risultato corretto é stato molto piú semplice.
Ci sono riuscito come sempre grazie al tuo aiuto onlyReferee 
A presto
A presto
Ciao,
continuando con la stessa tipologia ho svolto anche quest'altro esercizio a mò di esercitazione.
Costruire un automa a stati finiti che accetti il linguaggio L formato da tutte le stringhe sull'alfabeto {a,b} che contengono esattamente due occorrenze della stringa "ba" oppure contengono un numero pari di "a".
Ecco l'automa che ho ricavato:
http://imageshack.us/photo/my-images/801/qxs5.jpg/
E' corretto?
Sempre grazie.
continuando con la stessa tipologia ho svolto anche quest'altro esercizio a mò di esercitazione.
Costruire un automa a stati finiti che accetti il linguaggio L formato da tutte le stringhe sull'alfabeto {a,b} che contengono esattamente due occorrenze della stringa "ba" oppure contengono un numero pari di "a".
Ecco l'automa che ho ricavato:
http://imageshack.us/photo/my-images/801/qxs5.jpg/
E' corretto?
Sempre grazie.
Ciao krak!
Alla prima parte (quella più in alto) manca ancora qualcosa: in 1, 2, 3 e 4 nessuno ci impedisce di ciclare più volte sullo stesso stato con (nell'ordine) $a, b, a, b$ (le due occorrenze di $ba$ non è detto debbano essere consecutive e presenti all'inizio della stringa da riconoscere, almeno questo non è specificato). Il fatto di avere di accettazione 9 o 5 non cambia nulla (così come fai te ti ritrovi ad avere un unico stato di accettazione io ho preferito avere uno stato in meno e risparmiare sulle epsilon mosse).
Riguardo alla seconda parte (più in basso): analogo discorso per lo stato 6 in base a quanto detto sopra (nessun ci può impedire di ciclare con $b$ su sé stesso). Inoltre la epsilon-mossa da 8 a 6 la puoi tranquillamente evitare (lascio a te capire come, è semplicissimo).
Spero di esserti stato d'aiuto anche questa volta.
Nuovamente prego .
Alla prima parte (quella più in alto) manca ancora qualcosa: in 1, 2, 3 e 4 nessuno ci impedisce di ciclare più volte sullo stesso stato con (nell'ordine) $a, b, a, b$ (le due occorrenze di $ba$ non è detto debbano essere consecutive e presenti all'inizio della stringa da riconoscere, almeno questo non è specificato). Il fatto di avere di accettazione 9 o 5 non cambia nulla (così come fai te ti ritrovi ad avere un unico stato di accettazione io ho preferito avere uno stato in meno e risparmiare sulle epsilon mosse).
Riguardo alla seconda parte (più in basso): analogo discorso per lo stato 6 in base a quanto detto sopra (nessun ci può impedire di ciclare con $b$ su sé stesso). Inoltre la epsilon-mossa da 8 a 6 la puoi tranquillamente evitare (lascio a te capire come, è semplicissimo).
Spero di esserti stato d'aiuto anche questa volta.
Nuovamente prego
.
Ciao onlyReferee,
in effetti grazie al tuo aiuto ragiono su cose che a primo impatto non mi vengono in mente o non ci faccio caso.
Ecco l'automa adesso:
http://imageshack.us/photo/my-images/10/f77z.jpg/
Grazie!
in effetti grazie al tuo aiuto ragiono su cose che a primo impatto non mi vengono in mente o non ci faccio caso.
Ecco l'automa adesso:
http://imageshack.us/photo/my-images/10/f77z.jpg/
Grazie!
Mmmm, ok la parte sopra. Nella seconda però in teoria con l'automa attuale puoi accettare stringhe con un numero dispari di $a$ quindi non va ancora bene. Ritenta, sarai più fortunato!
Ciao onlyReferee,
ho sistemato la parte di sotto
http://imageshack.us/photo/my-images/189/sq9w.jpg/
Corretto adesso?
Grazie.
ho sistemato la parte di sotto
http://imageshack.us/photo/my-images/189/sq9w.jpg/
Corretto adesso?
Grazie.
Ok, krak, va bene.
Prego!
Prego!
Ciao
continuando con la stessa tipologia di esercizi, ho svolto anche quest'altro:
Costruire un automa a stati finiti che accetti il linguaggio L formato da tutte le stringhe sull'alfabeto {a,b} che contengono:
un numero di occorrenze del simbolo "a" pari a un multiplo positivo di 3
oppure
un numero di occorrenze del simbolo "b" pari a un multiplo positivo di 2.
Ecco come l'ho svolto io:
http://imageshack.us/photo/my-images/202/i66t.jpg/
Corretto?
Sempre grazie.
continuando con la stessa tipologia di esercizi, ho svolto anche quest'altro:
Costruire un automa a stati finiti che accetti il linguaggio L formato da tutte le stringhe sull'alfabeto {a,b} che contengono:
un numero di occorrenze del simbolo "a" pari a un multiplo positivo di 3
oppure
un numero di occorrenze del simbolo "b" pari a un multiplo positivo di 2.
Ecco come l'ho svolto io:
http://imageshack.us/photo/my-images/202/i66t.jpg/
Corretto?
Sempre grazie.
Ciao krak!
La parte sotto è corretta. Nella prima penso tu abbia commesso una svista perché con la versione attuale vengono accettate anche stringhe contenenti un numero di $a$ pari ad un non multiplo di tre (ad esempio $aa$). Ricontrolla bene...
La parte sotto è corretta. Nella prima penso tu abbia commesso una svista perché con la versione attuale vengono accettate anche stringhe contenenti un numero di $a$ pari ad un non multiplo di tre (ad esempio $aa$). Ricontrolla bene...
Ciao onlyReferee,
si in effetti nella parte superiore ho dimenticato a disegnare uno stato.
Ecco l'automa:
http://imageshack.us/photo/my-images/43/3hf6.jpg/
Grazie mille!
si in effetti nella parte superiore ho dimenticato a disegnare uno stato.
Ecco l'automa:
http://imageshack.us/photo/my-images/43/3hf6.jpg/
Grazie mille!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
