Francesco Guastella

Salve,

è un pò che non ci si vede…si avete ragione. Ho trascorso la scorsa estate scrivendo un pò di cose, ho contribuito nel portare Axiom su Windows Phone 7 e molto altro, insomma, come potete immaginare, preferisco usare linguaggi come c/c++, c# e altri…ma non linguaggi parlati 😉

Dopo questa scherzosa introduzione, cominciamo a parlare del sample che ho scritto e che sto condividendo con voi oggi…

Il sample, scritto in C#, mostra come sia possibile usare automi a stati finiti per obiettivi di indicizzazione. Cominciamo costruendo un NFA a partire da una stringa su un alfabeto di 0 e 1 (nel codice del sample è “0100101″). Questo NFA ha una particolare caratteristica: tutti i suoi stati sono sia iniziali che accettati. Pertanto, la rappresentatione dell’automa non deterministico sarà la seguente:

Il prossimo passo sarà creare un DFA a partire dall’NFA creato in precedenza, usando l’algoritmo del subset construction. Questo automa avrà anch’esso tutti gli stati accettati come l’NFA, ma ci sarà un solo stato iniziale (definizione di automa deterministico).

Questo DFA sarà infine utilizzato per la ricerca di sottostringhe nella stringa “0100101″, già indicizzata.

Scarica il codice sorgente Indexing with Automatons sample

Tags: automata, automaton, c#, dfa, index, indexing, nfa, sample, string, substring