[Linguaggi Formali e Automi]

[4mac07]

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?

[onlyReferee]

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.

[4mac07]

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

[onlyReferee]

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.

[4mac07]

Grazie ora e' tutto piu' chiaro!
Se dovessi avere altri esercizi in cui ho difficolta' posso scrivere ancora su questo thread?

[onlyReferee]

Certamente
Se gli esercizi sono sulla falsa riga di questo posta pure qui, altrimenti meglio aprire un altro thread .

[4mac07]

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?

[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 ,

[4mac07]

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.

[onlyReferee]

Esatto