Automa a stati finiti
Ciao a tutti, ho un problema di pattern matching.
Più precisamente si deve trovare l' automa a stati finiti, relativo al riconoscimento di un qualunque pattern P, di prefisso "GGG" e suffisso "GAT" ricordando che il pattern può essere di qualunque lunghezza maggiore strettametne a 4.
Il problema è che non so proprio come dovrei considerare le eventuali lettere che si trovano tra il prefisso ed il suffisso.
L' alfabeto utiizzato è {C,G,T,A}
Ora, quello che non riesco proprio a determinare, è il numero di combinazioni che ci possono essere lì in mezzo. Cioè. ci possono essere infiniti caratteri..
Mi sta evedentemente sfuggendo qualcosa..
Ogni consiglio è ben accetto, grazie a tutti!
Più precisamente si deve trovare l' automa a stati finiti, relativo al riconoscimento di un qualunque pattern P, di prefisso "GGG" e suffisso "GAT" ricordando che il pattern può essere di qualunque lunghezza maggiore strettametne a 4.
Il problema è che non so proprio come dovrei considerare le eventuali lettere che si trovano tra il prefisso ed il suffisso.
L' alfabeto utiizzato è {C,G,T,A}
Ora, quello che non riesco proprio a determinare, è il numero di combinazioni che ci possono essere lì in mezzo. Cioè. ci possono essere infiniti caratteri..
Mi sta evedentemente sfuggendo qualcosa..
Ogni consiglio è ben accetto, grazie a tutti!
Risposte
Mi è venuta in mente una possibile soluzione subito dopo aver scritto il topic..XD
Dato il valore dell' automa cerca il più lungo prefisso di P che sia suffisso di P. Se come prefisso ho "GGG" vuol dire che: a meno che in mezzo non ci siano solo "G", non è possiible trovare un prefisso che sia, ad esempio, suffisso di "GGGTA" oppure "GGGCCA". quindi per tutte le lettere diverse da "G", lo stato sarà zero, giusto ?
Dato il valore dell' automa cerca il più lungo prefisso di P che sia suffisso di P. Se come prefisso ho "GGG" vuol dire che: a meno che in mezzo non ci siano solo "G", non è possiible trovare un prefisso che sia, ad esempio, suffisso di "GGGTA" oppure "GGGCCA". quindi per tutte le lettere diverse da "G", lo stato sarà zero, giusto ?
Dato il valore dell' automa cerca il più lungo prefisso di P che sia suffisso di P. Se come prefis]so ho "GGG" vuol dire che: a meno che in mezzo non ci siano solo "G", non è possiible trovare un prefisso che sia, ad esempio, suffisso di "GGGTA" oppure "GGGCCA". quindi per tutte le lettere diverse da "G", lo stato sarà zero, giusto ?
Forse sei sulla strada buona... anche se il ragionamento mi sembra un po' incatricchiato
Ma scusa sei abituato a costruire gli automi con quale metodo? Cerchi la regex e poi lo crei, oppure fai a rovescio? Costruisci DFA o NFA?
Costruisci DFA o NFA?
Ehm, mi cogli decisamente impreparato..
A noi è stato spiegato un solo metodo, senza dargli assolutamente un nome. Provo a farti un esempio, magari ci capiamo..
Se tipo il mio pattern è: "ABABACA" mi è stato insegnato che se al primo confronto con il Testo, trovo una "A", allora passo allo stato 1, poi se al secondo confronto trovo una "B", allora passo al secondo stato. Se invece trovo una "A" al secondo confronto, dovrò vedere qual è il più lungo prefisso di P che sia suffisso di "AA", che è chiaramente "A", quindi resterò allo stato 1. Nel caso io trovassi una lettera divresa, tipo "C" o "T", tornerei allo stato zero, per chè non c'è nessun prefisso di P che sia suffisso di "AT" o di "AC". E avanti così..
Tra l' altro anche su internet ho sempre e solo visto questo metodo, che è quello presentato dal libro..
Scusami, credevo fossi più addentrato nella materia. Sono le usuali sigle di identificazione degli automi, dall'inglese DFA=Deterministic Finite Automata (automa deterministico) e NFA=Non-deterministic Finite Automata (automa non deterministico).
Dalla tua spiegazione direi che sei abituato a fare direttamente il primo, che è un automa nel quale ogni stato ha tutte le possibili transizioni, ovvero in una rappresentazione grafica con "cerchietti" per gli stati e "freccette" per le transizioni, da ogni cerchietto escono tante frecce quanti sono i simboli possibili dell'alfabeto, ho detto bene?
Ora, il tuo automa deve cercare l'espressione che comincia per "GGG" e finisce per "GAT"; il fatto debba essere strettamente più lunga di 4 simboli è implicito in questo: la sequenza più corta è GGGAT che è di 5, quindi l'espressione è
"GGGAT oppure GGG poi qualche altro carattere poi GAT" che in sintassi delle espressioni regolari si può scrivere "GGGAT|GGG(A|C|G|T)*GAT"
Quindi ti consiglio di provare a costruire l'automa per l'espressione GGGAT e vedrai che il resto vien da sé.
Dalla tua spiegazione direi che sei abituato a fare direttamente il primo, che è un automa nel quale ogni stato ha tutte le possibili transizioni, ovvero in una rappresentazione grafica con "cerchietti" per gli stati e "freccette" per le transizioni, da ogni cerchietto escono tante frecce quanti sono i simboli possibili dell'alfabeto, ho detto bene?
Ora, il tuo automa deve cercare l'espressione che comincia per "GGG" e finisce per "GAT"; il fatto debba essere strettamente più lunga di 4 simboli è implicito in questo: la sequenza più corta è GGGAT che è di 5, quindi l'espressione è
"GGGAT oppure GGG poi qualche altro carattere poi GAT" che in sintassi delle espressioni regolari si può scrivere "GGGAT|GGG(A|C|G|T)*GAT"
Quindi ti consiglio di provare a costruire l'automa per l'espressione GGGAT e vedrai che il resto vien da sé.
"Rggb":
Scusami, credevo fossi più addentrato nella materia. Sono le usuali sigle di identificazione degli automi, dall'inglese DFA=Deterministic Finite Automata (automa deterministico) e NFA=Non-deterministic Finite Automata (automa non deterministico).
Dalla tua spiegazione direi che sei abituato a fare direttamente il primo, che è un automa nel quale ogni stato ha tutte le possibili transizioni, ovvero in una rappresentazione grafica con "cerchietti" per gli stati e "freccette" per le transizioni, da ogni cerchietto escono tante frecce quanti sono i simboli possibili dell'alfabeto, ho detto bene?
Ora, il tuo automa deve cercare l'espressione che comincia per "GGG" e finisce per "GAT"; il fatto debba essere strettamente più lunga di 4 simboli è implicito in questo: la sequenza più corta è GGGAT che è di 5, quindi l'espressione è
"GGGAT oppure GGG poi qualche altro carattere poi GAT" che in sintassi delle espressioni regolari si può scrivere "GGGAT|GGG(A|C|G|T)*GAT"
Quindi ti consiglio di provare a costruire l'automa per l'espressione GGGAT e vedrai che il resto vien da sé.
Si hai capito correttamente quello che faccio, e non siamo neanche addentrati nella materia. Comunque l' automa te lo scrivo come matrice; nella riga in alto ho l' alfabeto, a sinistra ci dovrebbero essere gli stati, da zero a 5, ma se metto anche questa colonna non mi viene fuori la matrice. Tutti i numeri all' interno della matrice rappresentano lo stato in cui si andrà, trovando una determinata lettera.
$((G,C,T,A),(0,1,0,0),(0,2,0,0),(0,3,0,0),(0,3,0,4),(0,1,5,0),(0,1,0,0))$
Quindi vedo che: in una ipotetica sequenza di lettere all' interno del Patter, l' unico caso, in cui non si debba per forza tornare a zero, è quando il pattern è ridonandante, cioè ripete sè stesso.
Tipo se il mio pattern è: P= "GGGCTAGGGCTGAT" Allora, quando con l' automa sono arrivato a "GGGCTAGGGCT", se trovo una "G" vado avanti, con "T" e "C" torno a zero, mentre con "A" torno allo stato 6.
Quindi in particolare il pattern dovrebbe essere ridondante apparte l' ultima lettera (per evitare di tornare sempre a zero con una lettera diversa da "G").
Se dai in ingresso GGGAT o GGGGAT al tuo automa, rimane in stato 0, mi sa che non è quello che vuoi
Provo a fare l'automa "alla voleé", senza completarlo; parto da stato iniziale 0:
0) se trovo G passo a 1, altri simboli rimango in 0
1) se trovo G passo a 2, altri simboli torno a 0
2) se trovo G passo a 3, altri simboli torno a 0
[lo stato (3) mi indica "trovate tre G di fila"; inoltre, so che l'ultimo carattere è G, che può essere l'inizio del suffisso]
3) se trovo A passo a 4, altri simboli: completa tu
4) se trovo T passo a 5, altri: idem
5) [stato finale] se trovo qualche simbolo, passo a: completa, dai!
PS. Dal tuo ragionamento di sopra sembra tu ti ponga il problema di DISTINGUERE le stringhe che hanno più prefissi o suffissi corretti, ovvero cerchi di scrivere un automa che, dato ad esempio "AAGGGAAGGGAAGATCCGATCCGAT" vada in stati DIFFERENTI dopo aver trovato il primo prefisso "GGG", dopo il secondo "GGG", dopo il primo suffisso "GAT" e così via. Ma questo non è necessario, anzi di più: non si può fare con gli automi DFA, hai bisogno di qualcosa computazionalmente più potente.
PPS. Scaricati JFLAP che ti aiuta a capire e a fare le verifiche.
http://www.cs.duke.edu/csed/jflap/
Provo a fare l'automa "alla voleé", senza completarlo; parto da stato iniziale 0:
0) se trovo G passo a 1, altri simboli rimango in 0
1) se trovo G passo a 2, altri simboli torno a 0
2) se trovo G passo a 3, altri simboli torno a 0
[lo stato (3) mi indica "trovate tre G di fila"; inoltre, so che l'ultimo carattere è G, che può essere l'inizio del suffisso]
3) se trovo A passo a 4, altri simboli: completa tu
4) se trovo T passo a 5, altri: idem
5) [stato finale] se trovo qualche simbolo, passo a: completa, dai!
PS. Dal tuo ragionamento di sopra sembra tu ti ponga il problema di DISTINGUERE le stringhe che hanno più prefissi o suffissi corretti, ovvero cerchi di scrivere un automa che, dato ad esempio "AAGGGAAGGGAAGATCCGATCCGAT" vada in stati DIFFERENTI dopo aver trovato il primo prefisso "GGG", dopo il secondo "GGG", dopo il primo suffisso "GAT" e così via. Ma questo non è necessario, anzi di più: non si può fare con gli automi DFA, hai bisogno di qualcosa computazionalmente più potente.
PPS. Scaricati JFLAP che ti aiuta a capire e a fare le verifiche.
http://www.cs.duke.edu/csed/jflap/
Oddio cosa ho scritto, ho proprio sbagliato a ricopiare le colonne nella matrice.
Comunque:
3)se trovo A passo a 4, se trovo G resto allo stato 3, se trovo T o C torno a zero.
4)se trovo T passo a 5, se trovo A o C torno a zero, se trovo G torno ad 1.
5)stato finale: a questo punto l' unica possibilità per non tornare a zero è trovare una G.
Per quanto riguarda quello che hai scritto dopo, se non è troppo diffiicle spiegarmelo, potresti dirmi come mai non è possibile fare quello che pensavo ?
Insomma, alla fine si tratta pur sempre di trovare un prefisso che sia anche suffisso, non basta un veloce controllo ?
E comunque nel testo dell' esercizio non c'è appunto alcuna specifica su questo fatto, quindi è plausibile che si possa cadere nel caso di Pattern che si ripete, e di conseguenza, dovrò trovare un apposito automa che controlli bene se il testo si ripete..
Comunque:
3)se trovo A passo a 4, se trovo G resto allo stato 3, se trovo T o C torno a zero.
4)se trovo T passo a 5, se trovo A o C torno a zero, se trovo G torno ad 1.
5)stato finale: a questo punto l' unica possibilità per non tornare a zero è trovare una G.
Per quanto riguarda quello che hai scritto dopo, se non è troppo diffiicle spiegarmelo, potresti dirmi come mai non è possibile fare quello che pensavo ?
Insomma, alla fine si tratta pur sempre di trovare un prefisso che sia anche suffisso, non basta un veloce controllo ?
E comunque nel testo dell' esercizio non c'è appunto alcuna specifica su questo fatto, quindi è plausibile che si possa cadere nel caso di Pattern che si ripete, e di conseguenza, dovrò trovare un apposito automa che controlli bene se il testo si ripete..
"stefano_89":
3)se trovo A passo a 4, se trovo G resto allo stato 3, se trovo T o C torno a zero.
4)se trovo T passo a 5, se trovo A o C torno a zero, se trovo G torno ad 1.
5)stato finale: a questo punto l' unica possibilità per non tornare a zero è trovare una G.
Non funziona, direi. Fra l'altro l'automa che ho scritto di getto non potrebbe riconoscere la sequenza più corta "GGGAT", ho bisogno di un nuovo stato che ho chiamato X; riscrivo tutto in forma tabellare e cerco di spiegartelo:
s - G A T C
0 - 1 0 0 0
1 - 2 0 0 0
2 - 3 0 0 0
3 - 3 4 X X
X - 3 X X X
4 - 3 X 5 X
5 - 5 5 5 5
La prima colonna è degli stati, le altre dei simboli. Lo stato iniziale è 0 e lo stato finale è 5.
L'automa parte da 0, quando trova tre simboli G di fila (il prefisso) passa a stato 3, in tutte le altre condizioni ritorna in 0. Lo stato 3 mi rappresenta "trovate tre G di fila e l'ultimo simbolo scandito è G".
Dallo stato 3, se trova un simbolo G (il primo simbolo del suffisso) rimane in stato 3, se trovo A (il secondo simbolo del suffisso) passo a stato 4, altrimenti passa in uno stato X, sul quale l'automa rimane finché non trova il prossimo simbolo G che lo riporta in stato 3.
Dallo stato 4, trovando G ritorna in 3 ("trovate tre G di fila, ultimo simbolo G") e trovando T (terzo simbolo del suffisso) passa in stato finale 5.
Come puoi notare, quando raggiunge lo stato finale 5 l'automa "rimane bloccato" per così dire.
Per quanto riguarda quello che hai scritto dopo, se non è troppo diffiicle spiegarmelo, potresti dirmi come mai non è possibile fare quello che pensavo ?
Insomma, alla fine si tratta pur sempre di trovare un prefisso che sia anche suffisso, non basta un veloce controllo ?
Non so se ho capito correttamente quello che pensavi
Io intendevo dire "non si può costruire un automa a stati finiti che riconosca infinite volte una certa espressione regolare" in quanto questo dovrebbe avere infiniti stati.
Comunque, sia che l'automa descritto ti sembra possa andare bene, sia tu cercassi qualcosa di differente, fammi sapere.
Non capisco assolutamente il discorso del nuovo stato, non ne abbiamo mai parlato a lezione, e non penso che fosse quello che il professore chiedesse.
Sinceramente non riesco a capire questo punto:
Cioè, se siamo allo stato 4, saremmo arrivati a "GGGA", se trovo una "G", dovrò trovare un prefisso per la sequenza "GGGAG", quindi mi sembra logico tornare ad 1.
E poi perchè l' automa non può ricominciare?
Noi abbiamo sempre fatto ripartire l' automa..
Per quanto riguarda l' ultima parte, ho capito cosa intendi..
Sinceramente non riesco a capire questo punto:
Dallo stato 4, trovando G ritorna in 3 ("trovate tre G di fila, ultimo simbolo G")
Cioè, se siamo allo stato 4, saremmo arrivati a "GGGA", se trovo una "G", dovrò trovare un prefisso per la sequenza "GGGAG", quindi mi sembra logico tornare ad 1.
E poi perchè l' automa non può ricominciare?
Noi abbiamo sempre fatto ripartire l' automa..
Per quanto riguarda l' ultima parte, ho capito cosa intendi..
"stefano_89":
Non capisco assolutamente il discorso del nuovo stato, non ne abbiamo mai parlato a lezione, e non penso che fosse quello che il professore chiedesse.
E' solo che nella prima risposta avevo messo un automa a sei stati (0..5), mentre mi sono accorto ne servono sette (o almeno, di sette stati è l'automa che ho trovato). Per non cambiare i numeri ho chiamato il nuovo stato X, se preferisci puoi rifarlo numerando gli stati da 0 a 6.
Sinceramente non riesco a capire questo punto:
[quote]Dallo stato 4, trovando G ritorna in 3 ("trovate tre G di fila, ultimo simbolo G")
Cioè, se siamo allo stato 4, saremmo arrivati a "GGGA", se trovo una "G", dovrò trovare un prefisso per la sequenza "GGGAG", quindi mi sembra logico tornare ad 1.[/quote]
E perché mai? La sequenza "GGGAG" finisce in stato 3, che come ho detto rappresenta "trovati tre G di fila (ovvero il prefisso), e l'ultimo simbolo scandito è G". Se a questo punto segue il suffisso, la sequenza deve essere riconosciuta.
Controesempio: "GGGAGAT" è una sequenza che deve essere riconosciuta (quello che hai indicato come pattern). Giusto?
E poi perchè l' automa non può ricominciare?
Noi abbiamo sempre fatto ripartire l' automa..
Certo che può ricominciare, però... a questo punto, visti i tuoi numerosi dubbi, mi chiedo se stiamo cercando di fare la stessa cosa; dunque, l'automa che ho descritto verifica, data una qualunque sequenza di simboli G, A, C, T, se questa CONTIENE - all'inizio, alla fine, all'interno - una sequenza ("pattern") che ha prefisso GGG e suffisso GAT.
Quindi, per come sei abituato a procedere o per quello che ti chiede l'esercizio, con la sequenza "AGGGCATGATT" (che contiene un prefisso GGG seguito da un suffisso GAT) secondo te l'automa deve terminare in uno stato finale oppure no?
eh no..
ti sei dimenticato che c'è una A di mezzo.. Se l' automa finisse allo stato 3 vorrebbe dire che GGG è uguale GAG.
E perché mai? La sequenza "GGGAG" finisce in stato 3, che come ho detto rappresenta "trovati tre G di fila (ovvero il prefisso), e l'ultimo simbolo scandito è G".
ti sei dimenticato che c'è una A di mezzo.. Se l' automa finisse allo stato 3 vorrebbe dire che GGG è uguale GAG.
"stefano_89":
ti sei dimenticato che c'è una A di mezzo.. Se l' automa finisse allo stato 3 vorrebbe dire che GGG è uguale GAG.
Come sospettavo... o io mi sono spiegato male, oppure stiamo cercando di fare cose differenti. Quoto:
Più precisamente si deve trovare l' automa a stati finiti, relativo al riconoscimento di un qualunque pattern P, di prefisso "GGG" e suffisso "GAT" ricordando che il pattern può essere di qualunque lunghezza maggiore strettametne a 4.
Allora chiedo: secondo te la stringa "GGGAG" ha prefisso "GGG"? Secondo me la risposta è "sì", comincia per "GGG".
Se la tua risposta invece è "no", stiamo decisamente cercando due cose diverse, non ti pare?
Allora chiedo: secondo te la stringa "GGGAG" ha prefisso "GGG"? Secondo me la risposta è "sì", comincia per "GGG".
Certo, non metto in dubbio che GGG sia PREfisso di GGGGAG, ma mi manderebbe allo stato 3 solo se, GGG fosse SUffisso di GGGGAG.
Cioè, questo è il metodo che ho sempre usato, e non credo ce ne siamo altri..
Cerco di chiudere l'argomento; credo ci siano problemi di comprensione della soluzione e del metodo ("cosa" e "come"), infatti per me il tuo ultimo post non ha molto senso. Però proprio questo mi incuriosisce.
Puoi per favore darmi riferimenti, tipo il libro di testo usato, il corso, qualche link sul web? Oppure puoi postare un esercizio e/o problema che hai già fatto e risolto correttamente.
Puoi per favore darmi riferimenti, tipo il libro di testo usato, il corso, qualche link sul web? Oppure puoi postare un esercizio e/o problema che hai già fatto e risolto correttamente.
Ciao!
Stavo riprendendo questo argomento studiato all'università, e mi sono imbattuto in questo thread, dopo aver fatto una ricerca.
L'ASF che ho pensato io in merito al problema posto da stefano_89, è il seguente:
Mi pare che "funzioni", il problema che ho sempre avuto è nella verifica che effettivamente sia corretto. Di questo non riesco mai ad avere la certezza.
Per quel che riguarda le espressioni regolari invece: la tecnica sarebbe quella di crearsi un ASF e da esso ricavare la regex, oppure ci sono altri metodi, per chi è profano in materia?
A proposito, molto interessante il programma JFLAP. Devo approfondirlo.
Ma quindi questo tool mi aiuterebbe a creare le espressioni regolari?
Stavo riprendendo questo argomento studiato all'università, e mi sono imbattuto in questo thread, dopo aver fatto una ricerca.
L'ASF che ho pensato io in merito al problema posto da stefano_89, è il seguente:
Mi pare che "funzioni", il problema che ho sempre avuto è nella verifica che effettivamente sia corretto. Di questo non riesco mai ad avere la certezza.
Per quel che riguarda le espressioni regolari invece: la tecnica sarebbe quella di crearsi un ASF e da esso ricavare la regex, oppure ci sono altri metodi, per chi è profano in materia?
A proposito, molto interessante il programma JFLAP. Devo approfondirlo.
Ma quindi questo tool mi aiuterebbe a creare le espressioni regolari?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo