Automa stati finito
Ciao ho provato centinaia di volte ma non riesco a capire come si fa questo automa, cè qualcuno che sa farlo?
ecco la traccia:
Costruire un automa finito che riconosca il linguaggio:
L = { (01)n1m | n, m ≥ 0 & n+m pari}
N.B. la somma di due numeri è pari se gli addendi sono entrambi pari o entrambi dispari.
ecco la traccia:
Costruire un automa finito che riconosca il linguaggio:
L = { (01)n1m | n, m ≥ 0 & n+m pari}
N.B. la somma di due numeri è pari se gli addendi sono entrambi pari o entrambi dispari.
Risposte
Intendi $L={(01)^n 1^m : n,m>=0, n+m\ \pari}$ ?
Ovviamente assumo $Sigma={0,1}$ come alfabeto.
Ovviamente assumo $Sigma={0,1}$ come alfabeto.
si intendo proprio questo
Con la notazione usata $(01)^n$ intendi una stringa di '0' e '1' di lunghezza $n$ caratteri, oppure una stringa di $n$ sequenze '01'?
[ C'è molta arbitrarietà di notazione in giro... ]
[ C'è molta arbitrarietà di notazione in giro... ]
"Rggb":
Con la notazione usata $(01)^n$ intendi una stringa di '0' e '1' di lunghezza $n$ caratteri, oppure una stringa di $n$ sequenze '01'?
[ C'è molta arbitrarietà di notazione in giro... ]
a parte l'arbitrarietà, due volte su tre $(01)$ indica la concatenazione, cioè una sequenza di $01$
ragazzi allora non sapete aiutarmi? la traccia e come ha trascritto rggb, è la scittura ufficiale.
oddio... indicativamente definirei per iniziale 4 stati (A,B,C,D) + 2(per ora), (E,F),
A) che resta in A per ingresso 0 e va in B per 1
B) va in C per 0 e in E per 1
C) torna in A per 0 e va in D per 1
D) torna in A per 0 e va in F per 1
questi 4 stati contano 01
una volta ricevuta 01 n volte con n dispari l'automa sarà in B, con n pari sarà in D
poi se è in B e viene fuori 1 allora va in E cioè lo stato da cui comincia il conteggio di $1^m$
complementare per lo stato F
se quindi è in E m=1 (poichè ci è arrivato) e l'uscita dev'essere 1 solo se m è dispari (n+m pari).
quindi B andrà in E con uscita 1.
E andrà poi in A per ingresso 0 e in F per ingresso 1 (con uscita 0 poichè m sarebbe pari)
F quindi tornerà in E con ingr. 1 e uscita 1 (il ritorno => m dispari)
se invece la sequinza di 01 è pari allora il sistema è in D. D andrà in F con ingr 1 e uscita 0 (m dev'essere pari perchè n+m sia pari) e F andrà in A con ingr 0 e in E con uscita 1 e ingr 1 (come detto prima)
guarda se va bene
A) che resta in A per ingresso 0 e va in B per 1
B) va in C per 0 e in E per 1
C) torna in A per 0 e va in D per 1
D) torna in A per 0 e va in F per 1
questi 4 stati contano 01
una volta ricevuta 01 n volte con n dispari l'automa sarà in B, con n pari sarà in D
poi se è in B e viene fuori 1 allora va in E cioè lo stato da cui comincia il conteggio di $1^m$
complementare per lo stato F
se quindi è in E m=1 (poichè ci è arrivato) e l'uscita dev'essere 1 solo se m è dispari (n+m pari).
quindi B andrà in E con uscita 1.
E andrà poi in A per ingresso 0 e in F per ingresso 1 (con uscita 0 poichè m sarebbe pari)
F quindi tornerà in E con ingr. 1 e uscita 1 (il ritorno => m dispari)
se invece la sequinza di 01 è pari allora il sistema è in D. D andrà in F con ingr 1 e uscita 0 (m dev'essere pari perchè n+m sia pari) e F andrà in A con ingr 0 e in E con uscita 1 e ingr 1 (come detto prima)
guarda se va bene
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo