[Linguaggi Formali e Automi]
Salve a tutti,
sono nuovo nel forum ma ho navigato spesso in questo sito in cerca di soluzioni per i vari problemi di matematica e statistica. Ora devo studiare per l'esame di Linguaggi Formali e ho dei dubbi su alcuni esercizi.
Sia Σ={4,5}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto Σ che, interpretate come numero in notazione decimale, rappresentano un
intero che diviso per 3 ha come resto 1.
L'automa dovrebbe contenere 3 stati che rappresentano i possibili resti della divisione per 3: 0, 1, 2.
Lo stato iniziale dovrebbe essere 0 in quanto all'inizio ho un resto di 0.
Lo stato finale dovrebbe essere 1 in quanto si accettano solo i numeri con resto 1.
Dopo queste considerazioni non so come continuare per determinare la funzione di transizione.
Qualcuno che ha un'idea?
sono nuovo nel forum ma ho navigato spesso in questo sito in cerca di soluzioni per i vari problemi di matematica e statistica. Ora devo studiare per l'esame di Linguaggi Formali e ho dei dubbi su alcuni esercizi.
Sia Σ={4,5}
Costruite un automa che accetti il linguaggio costituito da tutte le
stringhe sull'alfabeto Σ che, interpretate come numero in notazione decimale, rappresentano un
intero che diviso per 3 ha come resto 1.
L'automa dovrebbe contenere 3 stati che rappresentano i possibili resti della divisione per 3: 0, 1, 2.
Lo stato iniziale dovrebbe essere 0 in quanto all'inizio ho un resto di 0.
Lo stato finale dovrebbe essere 1 in quanto si accettano solo i numeri con resto 1.
Dopo queste considerazioni non so come continuare per determinare la funzione di transizione.
Qualcuno che ha un'idea?
Risposte
Ciao 4mac07 
I tre stati che puoi individuare in base al resto sono corretti. Quello iniziale no in quanto è richiesto dal problema che la nostra stringa in ingresso sia formata solo da $4$ e $5$. Pertanto c'è bisogno di uno stato iniziale (che è il nostro quarto stato) dal quale poi mi sposterò una volta che ho letto il simbolo iniziale (ossia $4$ oppure $5$). Ovviamente andranno completate le transizioni per i simboli del nostro alfabeto anche a partire dagli altri stati.
I tre stati che puoi individuare in base al resto sono corretti. Quello iniziale no in quanto è richiesto dal problema che la nostra stringa in ingresso sia formata solo da $4$ e $5$. Pertanto c'è bisogno di uno stato iniziale (che è il nostro quarto stato) dal quale poi mi sposterò una volta che ho letto il simbolo iniziale (ossia $4$ oppure $5$). Ovviamente andranno completate le transizioni per i simboli del nostro alfabeto anche a partire dagli altri stati.
Grazie per la risposta onlyReferee!
Non capisco come fare le transizioni tra i vari stati. Non devo memorizzare tutto il numero ma devo solo considerare il resto giusto?
Dallo stato iniziale:
leggo il simbolo 4, mi sposto sullo stato che ha resto 0.
leggo il simbolo 5, mi sposto sullo stato che ha resto 1.
Come si fa a considerare il numero 44, 45, 54, 55 e i successivi? quelli con tre simboli e piu'?
Non riesco a capire come considerare queste stringhe
Non capisco come fare le transizioni tra i vari stati. Non devo memorizzare tutto il numero ma devo solo considerare il resto giusto?
Dallo stato iniziale:
leggo il simbolo 4, mi sposto sullo stato che ha resto 0.
leggo il simbolo 5, mi sposto sullo stato che ha resto 1.
Come si fa a considerare il numero 44, 45, 54, 55 e i successivi? quelli con tre simboli e piu'?
Non riesco a capire come considerare queste stringhe
Ciao 4mac07
Dallo stato iniziale se leggi $4$ semmai ti sposti nello stato in cui il numero ha resto $1$ (che è anche stato finale), con $5$ invece in quello in cui il numero ha resto $2$.
In generale comunque l'idea più semplice è quella di sfruttare il criterio di divisibilità per tre per modellare le transizioni tra gli stati: "un numero è divisibile per tre se il numero ottenuto sommando le sue cifre è un multiplo di tre".
Dato inoltre che il nostro numero è composto dalle sole cifre $4, 5$ e che si ha $4 = 3 + 1$ e $5 = 3 + 2$ risulta ora semplice capire come muoversi tra gli stati in base al resto della divisione del numero per tre.
Dallo stato iniziale se leggi $4$ semmai ti sposti nello stato in cui il numero ha resto $1$ (che è anche stato finale), con $5$ invece in quello in cui il numero ha resto $2$.
In generale comunque l'idea più semplice è quella di sfruttare il criterio di divisibilità per tre per modellare le transizioni tra gli stati: "un numero è divisibile per tre se il numero ottenuto sommando le sue cifre è un multiplo di tre".
Dato inoltre che il nostro numero è composto dalle sole cifre $4, 5$ e che si ha $4 = 3 + 1$ e $5 = 3 + 2$ risulta ora semplice capire come muoversi tra gli stati in base al resto della divisione del numero per tre.
Grazie ora e' tutto piu' chiaro!
Se dovessi avere altri esercizi in cui ho difficolta' posso scrivere ancora su questo thread?
Se dovessi avere altri esercizi in cui ho difficolta' posso scrivere ancora su questo thread?
Certamente
Se gli esercizi sono sulla falsa riga di questo posta pure qui, altrimenti meglio aprire un altro thread
.
Se gli esercizi sono sulla falsa riga di questo posta pure qui, altrimenti meglio aprire un altro thread
.
Grazie onlyReferee:)
Sia Σ={a,b}
Scrivete un'espressione regolare per il linguaggio formato da tutte le stringhe
sull'alfabeto Σ in cui il primo e l'ultimo simbolo sono uguali. Disegnate poi un automa a
stati finiti nondeterministico.
Io ho scritto questa soluzione, cosa ne pensi?
Sia Σ={a,b}
Scrivete un'espressione regolare per il linguaggio formato da tutte le stringhe
sull'alfabeto Σ in cui il primo e l'ultimo simbolo sono uguali. Disegnate poi un automa a
stati finiti nondeterministico.
Io ho scritto questa soluzione, cosa ne pensi?
L'espressione regolare è corretta, l'automa anche. Ti faccio comunque notare che hai messo due frecce in più che di fatto non ti servono perché senza di esse l'automa riconosce comunque ciò che vogliamo. Vediamo se scopri quali sono queste due frecce 
,
,
"onlyReferee":
L'espressione regolare è corretta, l'automa anche. Ti faccio comunque notare che hai messo due frecce in più che di fatto non ti servono perché senza di esse l'automa riconosce comunque ciò che vogliamo. Vediamo se scopri quali sono queste due frecce
Stavo pensando che forse e' possibile rimuovere l'arco da q_3 a q_1 etichettato 'b' e l'arco da q_4 a q_2 etichettato 'a'.
Nel primo caso se vengono lette consecutivamente due 'a' l'automa si trova sia nello stato q_1 che nello stato q_3, se successivamente viene letta una 'b' allora l'automa si trova solo nello stato q_1. Se arriva una 'a' allora si trova di nuovo sia su q_1 che su q_3. Supponendo che l'input termini allora l'automa riconosce la stringa anche senza l'arco da q_3 a q_1 etichettato 'b'. Lo stesso vale per l'altro caso.
Esatto 
Nuovo esercizio:)
Sia Σ={a,b}. Costruite un automa nondeterministico che accetti il linguaggio costituito da tutte le stringhe sull'alfabeto Σ nelle quali il terzultimo e il penultimo simbolo sono uguali.
Esprimete questo linguaggio con un'espressione regolare.
L'espressione regolare a cui avevo pensato e' la seguente: (a+b)*(aa+bb)(a+b)
Riguardo all'NFA ho pensato a questa tabella delle transizioni che non e' ancora completa:
Il dubbio rimane sugli stati q_3 e q_4 in quanto non so come gestire il caso in cui arrivi l'ultimo simbolo in modo da accettare anche le stringhe che terminano con: '...aab' e '...bba'
Sia Σ={a,b}. Costruite un automa nondeterministico che accetti il linguaggio costituito da tutte le stringhe sull'alfabeto Σ nelle quali il terzultimo e il penultimo simbolo sono uguali.
Esprimete questo linguaggio con un'espressione regolare.
L'espressione regolare a cui avevo pensato e' la seguente: (a+b)*(aa+bb)(a+b)
Riguardo all'NFA ho pensato a questa tabella delle transizioni che non e' ancora completa:
| δ | a | b |
|---|---|---|
| {q_0,q_1} | {q_0,q_2} | q_1 |
| q_2 | q_2 | q_1 |
| *q_3 | q_3 | / |
Il dubbio rimane sugli stati q_3 e q_4 in quanto non so come gestire il caso in cui arrivi l'ultimo simbolo in modo da accettare anche le stringhe che terminano con: '...aab' e '...bba'
Ciao
Da $q_1$ non hai la necessità di andare a $q_2$ e viceversa (la parte precedente al terzultimo simbolo della stringa la puoi generare tutta con $q_0$). Da $q_2$ puoi andare direttamente in $q_3$ con $b$ (basta un solo stato che ci indica di aver ricevuto in input tutti i simboli della nostra stringa fino al penultimo). Per quanto detto nella frase precedente $q_3$ non può essere di accettazione. Infine da $q_3$ vai in $q_4$, stato finale, sia con $a$ che con $b$ (l'ultimo simbolo non ha vincoli).
Da $q_1$ non hai la necessità di andare a $q_2$ e viceversa (la parte precedente al terzultimo simbolo della stringa la puoi generare tutta con $q_0$). Da $q_2$ puoi andare direttamente in $q_3$ con $b$ (basta un solo stato che ci indica di aver ricevuto in input tutti i simboli della nostra stringa fino al penultimo). Per quanto detto nella frase precedente $q_3$ non può essere di accettazione. Infine da $q_3$ vai in $q_4$, stato finale, sia con $a$ che con $b$ (l'ultimo simbolo non ha vincoli).
Grazie mille onlyRefree! Il tuo parere mi e' molto utile per capire meglio
onlyRefree come interpreti questa consegna?
Sia Σ={a,b}. Costruite un automa che accetti l'insieme delle stringhe contenenti due a separate da un numero di simboli multiplo di 4.
Esprimete questo linguaggio con un'espressione regolare.
E' giusto secondo te pensare che le due 'a' siano separate da un numero multiplo di 4 simboli 'b'.
'aaaaaaaabbbba' viene accettata
'babbabaaaaaaa' non accettata
In pratica le 'b' devono essere multiplo di 4, giusto?
Sia Σ={a,b}. Costruite un automa che accetti l'insieme delle stringhe contenenti due a separate da un numero di simboli multiplo di 4.
Esprimete questo linguaggio con un'espressione regolare.
E' giusto secondo te pensare che le due 'a' siano separate da un numero multiplo di 4 simboli 'b'.
'aaaaaaaabbbba' viene accettata
'babbabaaaaaaa' non accettata
In pratica le 'b' devono essere multiplo di 4, giusto?
Ciao
No, i simboli tra le due $a$ (quella iniziale e quella finale) possono essere qualsiasi (sia $a$ che $b$) purché in quantità pari ad un multiplo di quattro. Pertanto l'automa dovrà riconoscere ad esempio le stringhe $a b b b b b b b ba$, $aaaaaa$, $a b a b b a b a a b b b b a$ e $a b b b b a a a a a$ ma non $aba$, $aaa$ e $a a b b a b a b a$.
Immagino ti sia richiesto di costruire un automa non deterministico.
No, i simboli tra le due $a$ (quella iniziale e quella finale) possono essere qualsiasi (sia $a$ che $b$) purché in quantità pari ad un multiplo di quattro. Pertanto l'automa dovrà riconoscere ad esempio le stringhe $a b b b b b b b ba$, $aaaaaa$, $a b a b b a b a a b b b b a$ e $a b b b b a a a a a$ ma non $aba$, $aaa$ e $a a b b a b a b a$.
Immagino ti sia richiesto di costruire un automa non deterministico.
Non e' specificato ma probabilmente e' non deterministico, lo devo rifare in quanto ho interpretato male.
L'espressione regolare diventa (a+b)*a(aaaa+bbbb)*a(a+b)*?
L'espressione regolare diventa (a+b)*a(aaaa+bbbb)*a(a+b)*?
No, questa espressione non è corretta. Innanzitutto hai una $a$ all'inizio ed una alla fine della stringa. Poi per creare la parte centrale della stringa devi avere una "base" composta da quattro espressioni consecutive in cui si può scegliere tra $a$ e $b$. Per avere multipli di quattro di questa base è sufficiente iterare la stessa.
Non sono sicuro di aver capito...la parte centrale di prima non va bene? a(aaaa+bbbb)*a
riconosce stringhe del tipo '...a aaaa a...' , '...a bbbb a...'
riconosce stringhe del tipo '...a aaaa a...' , '...a bbbb a...'
onlyRefree in base alle tue dritte ho prodotto questa soluzione, forse si puo' semplificare ma intanto funziona sugli input che hai suggerito.
Inoltre mi sorge un dubbio, sul testo del problema dice "stringhe contenenti due a separate da un numero di simboli multiplo di 4", può anche accettare che tra due 'a' i siano 'abab' / 'baba' / 'abba' / 'aabb' ecc oppure devono per forza essere 4 simboli uguali come detto precedentemente?
http://i60.tinypic.com/9qitn5.png
Inoltre mi sorge un dubbio, sul testo del problema dice "stringhe contenenti due a separate da un numero di simboli multiplo di 4", può anche accettare che tra due 'a' i siano 'abab' / 'baba' / 'abba' / 'aabb' ecc oppure devono per forza essere 4 simboli uguali come detto precedentemente?
http://i60.tinypic.com/9qitn5.png
Ciao
Perdona il ritardo nella risposta, sono stato via nel weekend. Comunque è corretto quanto hai descritto nel tuo ultimo post: quel gruppo centrale di simboli può essere composto sia da $a$ che da $b$.
Non so perché cliccando sull'url da te postato non vedo l'immagine...
Perdona il ritardo nella risposta, sono stato via nel weekend. Comunque è corretto quanto hai descritto nel tuo ultimo post: quel gruppo centrale di simboli può essere composto sia da $a$ che da $b$.
Non so perché cliccando sull'url da te postato non vedo l'immagine...
Immaginavo fossi via questi giorni, spero ti sia rilassato
Nell'immagine c'era una possibile soluzione fatta su JFLAP, tool che permette di costruire automi e testare gli input sull'automa, oltre a convertire nei vari formati l'automa stesso.
Ora ho cambiato di nuovo e ti posto una soluzione diversa. Tra due 'a' possono esserci simboli misti di 'a' e 'b', l'importante e' che dopo aver letto la prima 'a' e i 4 simboli il quinto sia una 'a'.
Ti passo ancora il link perché se carico l'immagine nel post viene tagliata una parte.
Mi sono accorto che il link di prima non va, e non capisco perche'...ti metto un'altra
immagine.
Fai tasto dx sull'immagine e poi vai su 'Apri immagine in un altro tab' per vederla tutta
http://i61.tinypic.com/2ia39zr.jpg
Nell'immagine c'era una possibile soluzione fatta su JFLAP, tool che permette di costruire automi e testare gli input sull'automa, oltre a convertire nei vari formati l'automa stesso.
Ora ho cambiato di nuovo e ti posto una soluzione diversa. Tra due 'a' possono esserci simboli misti di 'a' e 'b', l'importante e' che dopo aver letto la prima 'a' e i 4 simboli il quinto sia una 'a'.
Ti passo ancora il link perché se carico l'immagine nel post viene tagliata una parte.
Mi sono accorto che il link di prima non va, e non capisco perche'...ti metto un'altra
immagine.
Fai tasto dx sull'immagine e poi vai su 'Apri immagine in un altro tab' per vederla tutta
http://i61.tinypic.com/2ia39zr.jpg
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
