Automi a stati finiti deterministici.

[Roberto81]

ciao a tutti volevo chiarirmi qualche dubbio sugli automi deterministici....

un classico esercizio è questo:
definire un automa a stati finiti deterministico sull'alfabeto ${0,1}$ di tutte le stringhe che contengono un numero pari di $0$ e $1$

questo automa ha quattro stati. per identificare le seguenti situazioni:
$q_0=$ stato iniziale e accettante l'automa ha letto un numero pari di 0 e 1
$q_1=$ il numero dei 0 letti è pari e gli 1 sono dispari
$q_2=$ il numero dei 0 è dispari e il numero di 1 è pari
$q_3=$ il numero di 0 e 1 sono dispari

Le mie domande sono queste:
1)ogni volta che si deve costruire un automa gli stati vengono decisi tramite una "semplice logica" oppure esiste un modo per determinare il numero di stati necessari.
2)creato un automa come posso provare che questo riconosca univocamente solo le stringhe del linguaggio?

[onlyReferee]

Ciao Roberto,
vedo di rispondere ai tuoi quesiti.
1) In generale il numero degli stati dipende appunto dalla logica/strategia adottata ossia da come si è pensato risolvere il proprio problema. In alcuni casi esiste una sola soluzione, in altri ve ne sono molteplici. Chiaramente si tende a preferire la soluzione più semplice;
2) Nel caso il linguaggio abbia un numero molto esiguo (e finito) di stringhe si può provare a generarle tutte ed enumerarle a partire dall'automa appena creato. In caso contrario si ricorre a delle apposite tecniche tipiche della calcolabilità e dei linguaggi formali di cui però non so nulla di preciso (almeno non ancora).
Spero di averti dato una delucidazione, seppure parziale.

[Roberto81]

Beh certamente é tutto piu chiaro. Grazie mille.