DFA AIUTO
Salve a tutti, ho un grande problema su questo esercizio.qualcuno può aiutarmi ? 
Dato l’alfabeto Σ = {0, 1} definire un DFA che accetta tutte e sole le stringhe w ∈ Σ∗ che hanno 1
come primo carattere, la cui lunghezza sia pari e il cui valore, interpretato come numero binario, sia
multiplo di 3.
Dato l’alfabeto Σ = {0, 1} definire un DFA che accetta tutte e sole le stringhe w ∈ Σ∗ che hanno 1
come primo carattere, la cui lunghezza sia pari e il cui valore, interpretato come numero binario, sia
multiplo di 3.
Risposte
"FOLLETTO86":
Salve a tutti, ho un grande problema su questo esercizio.qualcuno può aiutarmi ?
Dato l’alfabeto Σ = {0, 1} definire un DFA che accetta tutte e sole le stringhe w ∈ Σ∗ che hanno 1
come primo carattere, la cui lunghezza sia pari e il cui valore, interpretato come numero binario, sia
multiplo di 3.
Almeno la parte che ho evidenziato dovresti riuscire a farla.
Il resto lo disegni come una "scatola nera", poi ci guardiamo.
Visti i pochi dati in merito alle difficoltà non posso dirlo per certo, ma penso che il problema non sia tanto costruire un automa che accetti una stringa contenenti 1, quanto più la costruzione di un automa che tenga conto di tre proprietà diverse, nel complesso.
Penso questo perchè, per eseperienza, esercizi come questo lasciano parecchio spiazzati, la prima volta. Per il semplice fatto che l'approccio in generale è quello di iniziare a disegnare il diagramma di transizione del DFA non riuscendoci, neanche dopo diversi tentativi.
Quello che si fa per questo tipo di esercizi è sfruttare la proprietà di intersezione. Sostanzialmente usi diagrammi di transizione per definire i tre automi separatamente, e definisci l'automa dell'intersezione in maniera tabellare, considerando come stati finali le triple che condividono gli stati finali.
Per fare un esempio nell'automa dell'esercizio, il primo automa avrà due stati, $(q_0,q_1)$, il secondo avrà sempre due stati $(p_0,p_1)$, il terzo avrà tre stati $(r_0,r_1,r_2)$. In forma tabellare dovrai individuare per ogni input la destinazione (cioè per ogni terna $(q_0,p_0,r_0),(q_1,p_0,r_0),(q_0,p_1,r_0)$ ecc.. valuti in che stato si trovano i tre automi a seconda dell'input {0,1}). Se $q_1,p_1,r_0$ sono gli stati finali dei singoli automi, questa terna sarà lo stato finale risultante dall'intersezione dei tre.
Poichè diagrammi e tabelle sono forme equivalenti per definire un automa, puoi utilizzare uno o l'altro a seconda di quanto più semplice ti renda la vita. Fermo restante che una volta calcolata la tabella, se il tuo scopo(il testo dell'esercizio non specifica quindi credo vada bene anche un automa in forma tabellare) è disegnare il diagramma, il passo è totalmente meccanico.
In effetti la difficoltà potrebbe anche non esser questa, nel caso dovresti specificare qual'è il "grande problema" che ti attanaglia.
Penso questo perchè, per eseperienza, esercizi come questo lasciano parecchio spiazzati, la prima volta. Per il semplice fatto che l'approccio in generale è quello di iniziare a disegnare il diagramma di transizione del DFA non riuscendoci, neanche dopo diversi tentativi.
Quello che si fa per questo tipo di esercizi è sfruttare la proprietà di intersezione. Sostanzialmente usi diagrammi di transizione per definire i tre automi separatamente, e definisci l'automa dell'intersezione in maniera tabellare, considerando come stati finali le triple che condividono gli stati finali.
Per fare un esempio nell'automa dell'esercizio, il primo automa avrà due stati, $(q_0,q_1)$, il secondo avrà sempre due stati $(p_0,p_1)$, il terzo avrà tre stati $(r_0,r_1,r_2)$. In forma tabellare dovrai individuare per ogni input la destinazione (cioè per ogni terna $(q_0,p_0,r_0),(q_1,p_0,r_0),(q_0,p_1,r_0)$ ecc.. valuti in che stato si trovano i tre automi a seconda dell'input {0,1}). Se $q_1,p_1,r_0$ sono gli stati finali dei singoli automi, questa terna sarà lo stato finale risultante dall'intersezione dei tre.
Poichè diagrammi e tabelle sono forme equivalenti per definire un automa, puoi utilizzare uno o l'altro a seconda di quanto più semplice ti renda la vita. Fermo restante che una volta calcolata la tabella, se il tuo scopo(il testo dell'esercizio non specifica quindi credo vada bene anche un automa in forma tabellare) è disegnare il diagramma, il passo è totalmente meccanico.
In effetti la difficoltà potrebbe anche non esser questa, nel caso dovresti specificare qual'è il "grande problema" che ti attanaglia.
Un fatto non banale, almeno per me, è stato trovare un automa in grado di determinare se la stringa di ingresso intesa come numero binario fosse un multiplo di 3.
Assumo che la stringa sia un numero binario $\alpha$ in cui la prima cifra sia quella meno significativa e l'ultima la più significativa. Si ha quindi che
$\alpha = \sum_{k=0}^N a_k 2^k$
con $a_k \in {0,1}$ il $k$-esimo simbolo della sequenza di ingresso.
$\alpha$ è multiplo di 3 si esprime anche come $\alpha mod3 = 0$. Questo ci riporta allo studio di $2^k mod3$.
Per induzione si può dimostrare che $2^k mod 3 = {(1,\quad k \text{ pari}),(2,\quad k \text{ dispari}):}$
Quindi basta fare in modo che la somma dei valori di $2^k mod3$ quando $a_k = 1$ sia multiplo di 3, questo è facilmente realizzabile mantenendo uno stato della somma parziale in modulo 3, da cui le possibile operazioni possono essere $0 + 1$, $0 + 2$, $1 + 1$, $1 + 2$, $2 + 1$, $2 + 2$, da cui i possibili stati del contatore sono $0$, $1$, $2$. Infine bisogna fare in modo che lo stato ricordi anche il fatto che la posizione sia pari o dispari e quindi i possibili stati sono $p0, d0, p1,d1, p2,d2$.
L'automa si disegna facilmente a questo punto. La realizzazione delle altre tre richieste prevede piccole variazioni, circa gli stati finali e le transizioni uscenti dallo stato iniziale (che non è uno degli stati precedentemente citati).
Assumendo che il numero sia dal bit meno significativo a quello più significativo e con una sequenza di bit pari, che inizia con $1$, avrai dallo stato iniziale una transizione uscente marcata da $1$ che porta nello stato $p1$, dato che il primo elemento della sequenza corrisponde alla potenza $2^0$.
Se il numero dovesse essere interpretato al contrario, avendo una lunghezza della sequenza pari, l'automa non cambia poichè $2^{N -k} mod 3$ con $N$ pari equivale a $2^{k}mod3$, e quindi è come se si considerasse un numero in cui al primo simbolo corrisponde la potenza $2^N$. Questo non ci porta a considerare, dal punto di vista del multiplo di tre effettivamente il numero espresso nell'input $\beta$, bensì $2\beta$ (avendo lunghezza pari, la potenza più significativa è dispari poichè l'ultimo simbolo è associato alla potenza con esponente $0$, l'automa precedente dallo stato iniziale si porta nello stato $p1$ ovvero ad indicare il fatto che la potenza considerata dal primo simbolo è pari e quindi equivale a considerare la sequenza di bit shiftata a sinistra di una posizione cioè moltiplicata per $2$), ma il risultato è comunque corretto poichè $2\beta mod3 = \beta mod 3$.
Assumo che la stringa sia un numero binario $\alpha$ in cui la prima cifra sia quella meno significativa e l'ultima la più significativa. Si ha quindi che
$\alpha = \sum_{k=0}^N a_k 2^k$
con $a_k \in {0,1}$ il $k$-esimo simbolo della sequenza di ingresso.
$\alpha$ è multiplo di 3 si esprime anche come $\alpha mod3 = 0$. Questo ci riporta allo studio di $2^k mod3$.
Per induzione si può dimostrare che $2^k mod 3 = {(1,\quad k \text{ pari}),(2,\quad k \text{ dispari}):}$
Quindi basta fare in modo che la somma dei valori di $2^k mod3$ quando $a_k = 1$ sia multiplo di 3, questo è facilmente realizzabile mantenendo uno stato della somma parziale in modulo 3, da cui le possibile operazioni possono essere $0 + 1$, $0 + 2$, $1 + 1$, $1 + 2$, $2 + 1$, $2 + 2$, da cui i possibili stati del contatore sono $0$, $1$, $2$. Infine bisogna fare in modo che lo stato ricordi anche il fatto che la posizione sia pari o dispari e quindi i possibili stati sono $p0, d0, p1,d1, p2,d2$.
L'automa si disegna facilmente a questo punto. La realizzazione delle altre tre richieste prevede piccole variazioni, circa gli stati finali e le transizioni uscenti dallo stato iniziale (che non è uno degli stati precedentemente citati).
Assumendo che il numero sia dal bit meno significativo a quello più significativo e con una sequenza di bit pari, che inizia con $1$, avrai dallo stato iniziale una transizione uscente marcata da $1$ che porta nello stato $p1$, dato che il primo elemento della sequenza corrisponde alla potenza $2^0$.
Se il numero dovesse essere interpretato al contrario, avendo una lunghezza della sequenza pari, l'automa non cambia poichè $2^{N -k} mod 3$ con $N$ pari equivale a $2^{k}mod3$, e quindi è come se si considerasse un numero in cui al primo simbolo corrisponde la potenza $2^N$. Questo non ci porta a considerare, dal punto di vista del multiplo di tre effettivamente il numero espresso nell'input $\beta$, bensì $2\beta$ (avendo lunghezza pari, la potenza più significativa è dispari poichè l'ultimo simbolo è associato alla potenza con esponente $0$, l'automa precedente dallo stato iniziale si porta nello stato $p1$ ovvero ad indicare il fatto che la potenza considerata dal primo simbolo è pari e quindi equivale a considerare la sequenza di bit shiftata a sinistra di una posizione cioè moltiplicata per $2$), ma il risultato è comunque corretto poichè $2\beta mod3 = \beta mod 3$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo