Course summary

Page 1

FLC Cheatsheet rbino, Lapo, ray Disclaimer Gli autori non si assumono nessuna responsabilità per quanto riguarda la cor- rettezza di tutto ciò che segue, questo documento è stato creato nei pomeriggi di studio matto e disperatissimo e non ambiva ad essere diffuso al mondo inte- ro. Se avete correzioni, aggiunte, consigli aprite una issue o mandate una pull request sul repo Git1. Licenza Il presente documento è licenziato sotto Beer-Ware License (revisione 42). Una copia della licenza è disponibile nel repo Git. 1 Regular Expressions and Finite Automata 1.1 Berry-Sethi 1. Numerare i caratteri della grammatica e aggiungere il terminatore (⊣) 2. Calcolare il setIni (a) Tutti i simboli con cui la stringa può iniziare 3. Calcolare la look-up table per ogni carattere (a) Per ogni simbolo, ricavare i followers, ovvero tutti i caratteri che lo possono seguire 4. Disegno l’automa (a) Il primo stato ha come nome il setIni (b) Per ogni carattere nel nome dello stato, si guardano i followers e per ogni carattere (escludendo il pedice) si fa un arco in uscita che accetta quel carattere e finisce in uno stato con il nome dei followers di quel carattere 1https://github.com/rbino/flccheatsheet 1 i. Se ci sono due caratteri uguali ma con pedice diverso (i.e.a1 e a2) lo stato di arrivo è l’unione dei followers ii. Se ci si accorge che il nome dello stato risultante è uguale ad uno stato già esistente si riutilizza quello stato iii. Se tra i follower c’è anche il terminatore (⊣), lo stato viene segnato come terminale 1.2 Minimizzazione 1. Fare una matrice con righe e colonne con i nomi degli stati, rinominati con nomi umani (il triangolo superiore è inutile dato che è simmetrica) 2. Al primo step, segnare gli stati sicuramente distinguibili tra loro, ovvero le coppie finale-non finale 3. Per…