Today I am going to talk about my finite state automaton project that I did for my data structures class. I am pretty proud of this one since I started this class with no C++ experience and ended it by being the first person in my study group to get it finished. In case this is a recruiter reading this who doesn't know what an FSA does, http://en.wikipedia.org/wiki/Finite-state_machine
I started off by experimenting with how I wanted to handle the edges and nodes as constructs. Then I set about planning how I wanted the FSA to get constructed by writing up simple ones on a whiteboard and experimenting with connecting them. From that I decided I was going to work my way from a single accept node back to a single start node by creating simple FSAs and pointing the end nodes to the previously constructed FSA and the start node of the last FSA becomes the start node of the entire thing.
In order to actually run the FSA, I went with an input loop that first has a loop to fully explore all epsilon connections from a list of starting nodes, adding nodes with non-epsilon connections to a second list and then having a second loop to test each node in the second list for edges that match the next character.
I use breadth first search for both printing out a text representation of the FSA and for deleting it since in both situations depth first will lead to infinite loops. Deletion is done by first putting pointers to every node in a separate list and then traversing the list and deleting everything.
Graphical representation was done via third party program Graphviz.
Edit: Thanks to Gavin, Chris, Carlos, Julian, and everyone in the Burrow that helped me learn C++ despite having homework to do themselves.
