[esercizi] automi stati finiti

[cleaner]

mm, allora dovrei capire bene la logica che sta sotto agli automi a stati finiti:


le due stringhe di prova sono queste: 'aaab' e 'abaabb'

ora stavo guarando la prima:

allo stato q0 'aaab'
allo stato q1 la soluzione al problema mi dice che ho 'aab' ma sinceramente non ho capito il perchè; io devo partire da q0 giusto?

a q1 dovrei avere a(prima freccia verso destra in alto) e b(freccia in basso lunga)

Anche sullo stato q3 cosa significa la freccia che torna su se stessa?

[king64]

Dovresti indicare il particolare tipo di automa che vuoi andare a realizzare, devi cioè postare le specifiche del tuo problema. Saluti

[Vincenzo1968]

Si tratta di un automa a stati finiti di tipo deterministico(DFA).
La prima stringa, aaab, non viene accettata dall'automa; la seconda, abaabb, si.
Vediamo perché.

Stringa 1: aaab
L'automa parte nello stato iniziale q0; il primo carattere in input è 'a' e l'automa, dunque, transita nello stato q1.
Il carattere successivo è un'altra 'a' e l'automa transita nello stato q2. Il terzo carattere è, ancora una volta, una 'a'.
La funzione di transizione porta l'automa allo stato q3. Il carattere successivo è una 'b'; nello stato q3, la funzione di transizione fa rimanere l'automa nello stesso stato(q3) sia con una 'a' che con una 'b'(questo è il significato della freccia che torna sullo stesso stato).
Poiché non c'è più alcun carattere in input, e l'automa si trova nello stato q3, che non è accettante, la stringa non viene accettata.

Stringa 2: abaabb
Si parte dallo stato iniziale, q0. Il primo carattere, una 'a', porta l'automa nello stato q1. Il secondo, una 'b', transita l'automa nello stato q0. In questo stato, il carattere successivo, una 'a' ci porta allo stato 'q1'; il carattere 'a' transita l'automa allo stato q2.
Il carattere successivo, una 'b', transita l'automa nello stato q1. La 'b' successiva porta l'automa allo stato q0.
Poiché non c'è più alcun carattere in input e q0 è uno stato accettante, la stringa viene accettata(gli stati accettanti si rappresentano con un circoletto doppio).

[cleaner]

ti ringrazio ottima risposta