Francesco Guastella

Hi there,

long time no see..yeah you’re right. I spent last summer writing lot of stuff, I contributed to get Axiom ported on Windows Phone 7, and many other things….in short, as you can imagine, I prefer using laguages like c/c++, c# and others…but not spoken languages

After this introduction (with tongue in my cheek), let start talking about the sample I wrote and I’m sharing today with you…

The sample, written in C#, shows how it is possible to use finite state automatons to accomplish indexing tasks. We start constructing an NFA from a string over an alphabet of 0 and 1 (in the sample source code is “0100101″). This NFA has a particular feature: all its states are both initial and accepted. So the representation of the non-deterministic automaton will be as follows:

The next step will be creating a DFA starting from the previous created NFA, using the subset construction algorithm. This automaton will have all states accepted as well as NFA, but there will be only one initial state (definition of deterministic automaton).

This DFA will be finally used for searching substring occurrences in the string “0100101″, already indexed.

Download the source code Indexing with Automatons sample

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