[Automi]Automi che contano

[angus89]

Allora...preametto che ho appena scoperto cos'è un automa e quindi anche se banale la mia domanda per me è difficile.

Allora...
Come faccio a definire un linguaggio attraverso un automa dove ogni parola ha lunghezza $n$?

Esempio pratico.
Il mio linguaggio è formato dall'alfabeto ${0,1}$ (ovvero formato solo da 0 e 1) e le parole che l'automa deve far accettare devono avere lunghezza 5.

Ok questa è una sciocchezza, mi è sufficiente un automa a 5 stati, ma cosa succede se solo provo a dire

Esempio
Il mio linguaggio è formato dall'alfabeto ${0,1}$ e le parole che l'automa deve far accettare devono avere lunhezza 5 ma devono esserci almeno 2 zeri.

Bè adesso il numero di stati aumenta esponenzialmente...
Come posso sistemarlo?

[marx1]

Devi prima costruirti l'automa che riconosce le parole che contengono almeno 2 zeri,poi costrisci quello che riconosce le parole che hanno lunghezza 5 e puoi ottenere l'automa che cerchi facendo l'intersezione dei 2 automi

[angus89]

"marx":Devi prima costruirti l'automa che riconosce le parole che contengono almeno 2 zeri,poi costrisci quello che riconosce le parole che hanno lunghezza 5 e puoi ottenere l'automa che cerchi facendo l'intersezione dei 2 automi

mmm...
intersezione fra automi...a livello intuitivo e' come interseare i due linguaggi e vedere le parole che son contenute sia nell'uno che nell'altro...l'idea c'e'...devo solo capire come farlo..
ti ringrazio

[angus89]

proprio non ci arrivo...come devo fare l'intersezione degli automi??

ps...
il testo che sto utilizzando non è il massimo della chiarezza, ci sono direttamente esercizi impossibili, infatti l'esercizio originale era:
creare un automa che accetta solo stringhe le cui sottostringhe di lunghezza 5 hanno almeno due zeri...

Comuqne se qualcuno ha qualche link o qualche dispensa che spieghi come approcciarci a questi esercizi posti pure

[marx1]

Dati due automi A1 e A2 la loro intersezione è:

A={Σ,Q1xQ2,(q01,q02),F1xF2,δ}

e dove

δ((q1,q2),a)=(δ1(q1,a),δ2(q2,a))

quindi lo stato iniziale sarà l'insieme formato dai due stati iniziali e da ognio stato si prendono tutte le possibilin transizioni per ogni singolo automa e si arriva per ogni possibile transizione ad un'insieme di stati, saranno di accettazione quegli stati che sono formati da soli stati di accettazione per gli automi di partenza.