1. Conversione diretta ed inversa tra automi a stati non definiti (NFA) ed espressioni regolari FACOLT DI INGEGNERIA Tesi di Laurea in INGEGNERIA INFORMATICARelatore: Prof. Eric Medvet Correlatore: Dott. Andrea De Lorenzo Candidato: Paolo Oltramonti

2. Oggetto della tesi Sviluppare un algoritmo che effettua la conversione diretta ed inversa tra automi a stati finiti non deterministici (NFA) ed espressioni regolariNFAESPRESSIONE REGOLAREESPRESSIONE REGOLARENFA 3. Scenario 4. Scenario Il progetto si colloca nellambito di una ricerca di alto livello su: Generazione automatica di pattern a partire da esempib[A-Z0-9._%+-]+ 5. Scenario Si sono esplorate due strade1. Le NFA2. Le espressioni regolarib[A-Z0-9._%+-]+che si sono rivelate entrambe interessanti 6. Cos una NFA Una NFA un automa a stati finitiUn automa un modello che permette di descrivere con precisione e in maniera formale il comportamento di un sistema 7. Cos una NFA Distinguiamo due importanti tipi di automi a stati finitiautomi a stati finiti non deterministici (NFA)automi a stati finiti deterministici (DFA) 8. Cos un espressione regolare Unespressione regolare un formalismo che permette di descrivere un insieme di stringhe Unespressione regolare un linguaggio regolareUnespressione regolare definisce una funzione che prende in ingresso una stringa, e restituisce in uscita un valore booleano, a seconda che la stringa aderisca o meno al pattern 9. Coshanno in comune NFA e Regex Sono dei pattern Riconoscono un linguaggio regolare Un linguaggio regolare pu essere rappresentato con entrambe le rappresentazioni 10. Quali sono le differenze Le espressioni regolari hanno il vantaggio di essere utilizzate negli editor di testoQuindi hanno una maggiore utilit rispetto alle NFA 11. Quali sono le differenze I tempi di esecuzione: NFA dipendono linearmente dalla lunghezza dellinput Espressioni regolari dipendono anche dalla complessit 12. Problema 13. Perch convertire Per beneficiare dei vantaggi di entrambi gli approcci necessario sviluppare una metodologia per convertire da espressioni regolari ad NFA e viceversaab*b|aa*a 14. Soluzione 15. Approccio al problema Per effettuare le conversioni si sono identificati ed implementati degli algoritmi noti Algoritmo di creazione dei sottoinsiemi per la conversione da NFA ad espressione regolare Algoritmo di Thompson per la conversione da espressione regolare ad NFA 16. Vincoli di progetto e tecnologie 1. Linguaggio di programmazione Javascript 2. Codifica NFA preesistente in oggetti JSON:Lalgoritmo si deve integrare con un software preesistente 17. Realizzazione: NFA => Regex Algoritmo di creazione dei sottoinsiemiNFA => DFADFA => GNFAGNFA => Regex 18. NFA => Regex Esempio di conversione da NFA ad espressione regolare NFAGNFADFARegexab|cd 19. Realizzazione: Regex => NFA Algoritmo di ThompsonRegex => sottoespressioniSottoespressioni => blocchi NFABlocchi NFA => NFA 20. Regex => NFA Esempio di conversione da espressione regolare a NFARegexSottoexpr1=ab ab|cdr2=cdr3=r1|r2Blocchi NFANFA 21. Test Limplementazione stato testata su: 50 espressioni regolari 50 NFATutte le conversioni dirette ed inverse sono state testate con successo 22. Conclusioni 23. Conclusioni Algoritmi implementati Algoritmo di creazione dei sottoinsiemi Algoritmo di ThompsonEsito implementazione Limplementazione stata testata con successo 24. Grazie