Automa a stati finiti
Dato l'alfabeto E:atcg trovare tutte le occorrenze della stringa: aatccgcaatc sul testo T. Definire un automa a stati finiti deterministrico che permetta di svolgere in maniera efficiente questa ricerca
Come si può risolvere questo esercizio? Devo prima creare il diagramma degli stati o la tabella degli stati? Da dove iniziare?
Non ho trovato esempi concreti che mi possano aiutare. Grazie
Come si può risolvere questo esercizio? Devo prima creare il diagramma degli stati o la tabella degli stati? Da dove iniziare?
Non ho trovato esempi concreti che mi possano aiutare. Grazie
Risposte
Una cosa è da chiarire: un DFA non può determinare dove sono le occorrenze né tantomeno quante sono (a meno non sia nota la lunghezza dell'input $T$, assumo non lo sia); come dobbiamo quindi interpretare "trovare tutte le occorrenze"? Hai qualche riferimento più preciso?
Io comunque comincierei dall'automa che verifica se la stringa è presente in una generica stringa di input $T$:
- parte da uno stato iniziale q0, se trova "a" cambia stato in q1, per le altre stringhe rimane in q0;
- dallo stato q1 se trova "a" cambia stato in q2, per le altre stringe torna in q0;
- dallo stato q2 se trova "t" cambia stato in q3, per le altre stringhe torna in q0;
eccetera.
Prova a continuare, fino a raggiungere uno stato finale.
Io comunque comincierei dall'automa che verifica se la stringa è presente in una generica stringa di input $T$:
- parte da uno stato iniziale q0, se trova "a" cambia stato in q1, per le altre stringhe rimane in q0;
- dallo stato q1 se trova "a" cambia stato in q2, per le altre stringe torna in q0;
- dallo stato q2 se trova "t" cambia stato in q3, per le altre stringhe torna in q0;
eccetera.
Prova a continuare, fino a raggiungere uno stato finale.
Rggb ma te costruisci l'automa da T?
Io conosco uno string matching con automi, che costruisce l'automa di E (del pattern) e poi itera su T.
O è lo stesso?
Io conosco uno string matching con automi, che costruisce l'automa di E (del pattern) e poi itera su T.
O è lo stesso?
E' lo stesso, se ci fai caso il mio esempio è (l'inizio di) un DFA pattern-match. Non "costruisco l'automa da T" considerato che $T$ è l'input... 
Però se la lunghezza di $T$ è nota posso costruire un automa che "sappia" dove sono le occorrenze e quante sono, e avrà un numero di stati proporzionale a $|T|$.
Normalmente non è questo l'uso dei DFA: è un po' come ammazzare elefanti a colpi di fichi molli.
Però se la lunghezza di $T$ è nota posso costruire un automa che "sappia" dove sono le occorrenze e quante sono, e avrà un numero di stati proporzionale a $|T|$.Normalmente non è questo l'uso dei DFA: è un po' come ammazzare elefanti a colpi di fichi molli.
Allora.
L'argomento rigurada proprio string matching. E l'esercizio è proprio scritto così per come è. Nelle varie esercitazioni sono tutte un pò simili.
Pertanto seguendo le indicazioni di Rggb potrei costruire una tabella degli stati e da li costruire il diagramma dell'automa.
Altri riferimenti non ne ho in particolare. L'unico che può aiutare e che sono problemi di string matching
Creare una tabella:
a t g c
0 1 0 0 0 a
1 2 0 0 0 a
2 2 3 0 0 t
3 0 0 0 4 c
4 0 0 0 5 c
5 0 0 6 0 g
............
Dove 0,1,2,3....sono gli stati
atgc è l'alfabeto e aatccg... è il pattern
E poi il grafico? che ne pensate?
L'argomento rigurada proprio string matching. E l'esercizio è proprio scritto così per come è. Nelle varie esercitazioni sono tutte un pò simili.
Pertanto seguendo le indicazioni di Rggb potrei costruire una tabella degli stati e da li costruire il diagramma dell'automa.
Altri riferimenti non ne ho in particolare. L'unico che può aiutare e che sono problemi di string matching
Creare una tabella:
a t g c
0 1 0 0 0 a
1 2 0 0 0 a
2 2 3 0 0 t
3 0 0 0 4 c
4 0 0 0 5 c
5 0 0 6 0 g
............
Dove 0,1,2,3....sono gli stati
atgc è l'alfabeto e aatccg... è il pattern
E poi il grafico? che ne pensate?
Ho guardato meglio l'algoritmo che conoscevo, sì è simile alla spiegazione di Rggb, l'unica differenza sono i i fichi
Ho letto male, $E$ pensavo fosse il pattern, di solito leggo $Sigma$ per l'alfabeto.
@ciccionet: la tua descrizione, a me sembra corretta, per il passo di preelaborazione del Pattern con Automi. (non ho guardato la tabella, ma il procedimento da fare è quello)
Non sono molto d'accordo (o forse ho capito male o forse ancora diciamo la stessa cosa), spiego.
L'algoritmo di "Finite-Automata-Matcher" (che non sapevo si chiamasse DFA), ha il passo di preelaborazione sul Pattern che costruisce l'automa di matching (Compute-Transition), complessità $O(m^3|Sigma|)$ complessità proporzionale, rispettivamente alla lunghezza del Pattern $m$, e la cardinalità dell'alfabeto.
L'algortimo di matching vero e proprio è lineare alla lunghezza del testo $T$ cioè $Theta(n)$.
Anche non avendo il testo, il passo di preelaborazione lo fai sul pattern, mica sul testo.
Non capisco, anche, perchè non possiamo conoscere la lunghezza del test T. Non è inerente all'algoritmo di Matching, ma è una funzione "lenght" con complessità $Theta(n)$, che se messa assieme all'algoritmo di ricerca delle occorrenze sarà sempre $O(n)$.
SP (Solo Per): Un algoritmo più efficente è KMP con complessità $O(m|Sigma|)$, ma non utilizza Automi.
Ho letto male, $E$ pensavo fosse il pattern, di solito leggo $Sigma$ per l'alfabeto.
@ciccionet: la tua descrizione, a me sembra corretta, per il passo di preelaborazione del Pattern con Automi. (non ho guardato la tabella, ma il procedimento da fare è quello)
Però se la lunghezza di T è nota posso costruire un automa che "sappia" dove sono le occorrenze e quante sono, e avrà un numero di stati proporzionale a |T|.
Non sono molto d'accordo (o forse ho capito male o forse ancora diciamo la stessa cosa), spiego.
L'algoritmo di "Finite-Automata-Matcher" (che non sapevo si chiamasse DFA), ha il passo di preelaborazione sul Pattern che costruisce l'automa di matching (Compute-Transition), complessità $O(m^3|Sigma|)$ complessità proporzionale, rispettivamente alla lunghezza del Pattern $m$, e la cardinalità dell'alfabeto.
L'algortimo di matching vero e proprio è lineare alla lunghezza del testo $T$ cioè $Theta(n)$.
Anche non avendo il testo, il passo di preelaborazione lo fai sul pattern, mica sul testo.
Non capisco, anche, perchè non possiamo conoscere la lunghezza del test T. Non è inerente all'algoritmo di Matching, ma è una funzione "lenght" con complessità $Theta(n)$, che se messa assieme all'algoritmo di ricerca delle occorrenze sarà sempre $O(n)$.
SP (Solo Per): Un algoritmo più efficente è KMP con complessità $O(m|Sigma|)$, ma non utilizza Automi.
"ham_burst":
@ciccionet: la tua descrizione, a me sembra corretta, per il passo di preelaborazione del Pattern con Automi. (non ho guardato la tabella, ma il procedimento da fare è quello)
Confermo.
"ham_burst":Però se la lunghezza di T è nota posso costruire un automa che "sappia" dove sono le occorrenze e quante sono, e avrà un numero di stati proporzionale a |T|.
Non sono molto d'accordo (o forse ho capito male o forse ancora diciamo la stessa cosa), spiego.
L'algoritmo di "Finite-Automata-Matcher" (che non sapevo si chiamasse DFA), ha il passo di preelaborazione sul Pattern che costruisce l'automa di matching (Compute-Transition), complessità $O(m^3|Sigma|)$ complessità proporzionale, rispettivamente alla lunghezza del Pattern $m$, e la cardinalità dell'alfabeto.
Tutto giusto ma sto dicendo un'altra cosa (a margine, DFA sta per Deterministic Finite Automata).
In caso sia nota la lunghezza massima del testo da analizzare $n=|T|$ è possibile creare un DFA con al più $k*n$ stati con $k$ costante calcolabile, e l'automa può "sapere" dove e quante sono le occorrenze della stringa in base allo stato finale; però - appunto - normalmente non è questo che riguarda il pattern-match aka string-match et al, e i corrispondenti automi (da qui i fichi molli
), la mia era solo una considerazione sulla base del testo del problema come presentato dall'autore del thread.
Grazie! La tebella da me postata e però visualizzata male, nel senso che la prima prima colonna rappresentano gli stati poi la seconda le corrispondenze con la prima riga e l'ultima collonna in pattern.
Ho cercato di costruirla seguendo il ragionamento che appensa non trova corrispodenza torna indietro
Per il discorso della lunghezza di T non so cosa rispondere, visto che l'esercizio era scritto così
Grazie per il supporto
Ho cercato di costruirla seguendo il ragionamento che appensa non trova corrispodenza torna indietro
Per il discorso della lunghezza di T non so cosa rispondere, visto che l'esercizio era scritto così
Grazie per il supporto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo