Newsgroup: it.scienza.informatica
Titolo: Automa.....

Ciao a tutti!!!!! Volevo chiedere se qualcuno è in grado di darmi una
mano....
Devo dimostrare che il seguente linguaggio è regolare: L | L contiene tutte
le stringhe tali che,se interpretate come numero intero(BINARIO),sono
divisibili per 5.
Allora,io l'automa che riconosce tali stringhe l'ho costruito,penso sia
giusto ma devo dimostrarlo(in modo induttivo..).
Il problema è trovare una certa proprietà sulla lunghezza oppure sul valore
delle stringhe binarie in modo da applicare il principio induttivo e
dimostrare la correttezza dell'automa per ogni stringa.
In sostanza: esiste una certa ricorrenza o proprietà nei numeri binari
modulo 5?

Vedi se riesci a implementare in una DFA il seguente algoritmo:
Le sequenze-resti . Criterio generale di divisibilità.
Nel descrivere il metodo di Pascal, abbiamo incontrato una sequenza di
numeri, data dai successivi resti modulo 7 delle potenze di 10:
.... 4 6 2 3 1
Tale sequenza può essere utilizzata per qualunque numero di cui si voglia
calcolare il resto modulo 7. Infatti, se si vuole calcolare il resto mod 7
di un altro numero, si dovranno sostituire le cifre nella prima riga, mentre
restano fissi i termini della seconda. Questi dunque costituiscono una
sequenza invariante.
Vediamo di saperne un po' di più. Per calcolare le varie cifre di una
sequenza-resti mod n, valgono le seguenti regole:
La prima cifra (a partire da destra) è sempre 1
Tutte le altre cifre si ottengono moltiplicando per 10 il valore precedente
e calcolando poi il resto modulo n del prodotto ottenuto.
1 mod 7 = 1
(1×10) mod 7 = 3
(3×10) mod 7 = 2
(2×10) mod 7 = 6
(6×10) mod 7 = 4
(4×10) mod 7 = 5
(5×10) mod 7 = 1
Nell'ultima riga abbiamo ottenuto di nuovo il resto 1, come per il primo
termine. E' chiaro perciò che, continuando a calcolare, si otterranno
periodicamente i resti precedenti. Si può pertanto concludere che il
criterio di divisibilità per 7 darà luogo ad una sequenza-resti periodica, i
cui termini (che vanno letti da destra verso sinistra) sono:
.... 5 4 6 2 3 1
Per vedere se un numero n qualsiasi è divisibile o no per 7, si procede
pertanto nel seguente modo:
Si scrivono su una riga le cifre del numero n;
Si scrivono sotto ciascuna di esse i numeri della sequenza-resti mod. 7 (a
partire da destra) nel numero richiesto;
Si moltiplicano i termini della prima riga per i corrispondenti nella
seconda.
Si sommano i prodotti così ottenuti
Si calcola il resto mod 7 del valore ottenuto.
Se il resto mod 7 è zero, allora il numero n è divisibile per 7.
La regola vista per il 7, vale per qualunque altro numero, di cui si vuole
determinare il criterio di divisibilità. E' sufficiente infatti sostituire 7
con k nel secondo, quinto e sesto punto. La regola resta perfettamente
valida. Essa costituisce quindi un criterio generale di divisibilità valido
per determinare se un qualsiasi numero n sia o no divisibile per un altro
numero k.
Facciamo alcuni esempi. Essi serviranno, oltre che a rafforzare la
conoscenza della regola, anche per comprendere meglio i criteri di
divisibilità, spesso messi nei testi scolastici senza alcuna
giustificazione. Esso sono inoltre considerate come altrettante regole
indipendenti, senza farle derivare tutte da un unico criterio generale. Gli
alunni vengono così indotti ad imparare le regole in modo mnemonico, senza
stimolare in loro capacità di osservazione e di analisi.
6 - Divisibilità per 2 e per 5.
Applicando al 2 e al 5 i primi due passi della regola, si ottiene la
sequenza:
.... 0 0 0 0 0 0 1
Moltiplicando le cifre di un qualsiasi numero per i rispettivi termini della
predetta sequenza, resterà solo l'ultima cifra. Tutte le altre cifre infatti
vengono moltiplicate per 0 e quindi si annullano. Ecco spiegato, in modo
razionale, il motivo per cui si guarda solo l'ultima cifra per vedere se un
numero è pari o dispari o per vedere se esso è divisibile per 5.