Good day all!
Revision #17566 contains a somewhat usable implementation of the FiniteStateMachine (FSM) class. I say somewhat, because the current class interface and available features are not providing the level of abstractions needed to encapsulate the error-prone tasks of using an FSM.
Overview
Here is a quick overview of what can be done with the current implementation.
The following is a code sample that demonstrates the usage of the FSM to validate a Canadian postal code.
Revision #17566 contains a somewhat usable implementation of the FiniteStateMachine (FSM) class. I say somewhat, because the current class interface and available features are not providing the level of abstractions needed to encapsulate the error-prone tasks of using an FSM.
Overview
Here is a quick overview of what can be done with the current implementation.
- Programmatically add states and transitions to an FSM.
- Specify a predicate per transition, denoting which input symbols cause the transition.
- Construct an enumerator to walk the FSM, one input symbol at a time.
The following is a code sample that demonstrates the usage of the FSM to validate a Canadian postal code.
// Validates a Canadian postal code (xnx-nxn, where x is a letter and n is a digit; e.g. H0H-0H0).
bool ValidatePostalCode(string postalCode)
{
FiniteStateMachine<char> fsm = new FiniteStateMachine<char>;
fsm.AddState("start");
fsm.AddState("final");
fsm.AddState("letter_0");
fsm.AddState("letter_1");
fsm.AddState("letter_2");
fsm.AddState("hyphen");
fsm.AddState("digit_0");
fsm.AddState("digit_1");
fsm.AddTransition(new Transition<char>("start", "letter_0", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_0", "digit_0", Char.IsDigit));
fsm.AddTransition(new Transition<char>("digit_0", "letter_1", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_1", "hyphen", ch => ch == '-'));
fsm.AddTransition(new Transition<char>("hyphen", "digit_1", Char.IsDigit));
fsm.AddTransition(new Transition<char>("digit_1", "letter_2", Char.IsLetter));
fsm.AddTransition(new Transition<char>("letter_2", "final", Char.IsDigit));
IFsmEnumerator<char> enumerator = fsm.CreateStateEnumerator("start");
foreach(char symbol in postalCode)
{
if(!enumerator.NextState(symbol)) { return false; }
}
return enumerator.CurrentState == "final";
}
Overall, a bit laborious but it sets a good foundation to get the internals working.
QuickGraph and FSM Persistence
The FSM classes use QuickGraph as the underlying storage for the representation of the FSM. I chose to use this library over the tabular FSM representation because the graph data structure avoids a sparse FSM table, and that the graph library supports graph serialization, persistence, and visualization. A quick comparison of the two data structures shows that navigation speed of the graph from vertex to vertex is on the same order as a table lookup, however the memory overhead is slightly higher due to the management of hash tables versus a single two-dimensional array. In the future, I may consider abstracting the data storage of the FSM into a policy to support the tabular implementation.
I've also been concerned with the ability to serialize and persist a graph that contains dynamic data structures such as anonymous delegates. How does one represent a non-static method call in XML? I've verified that the binary serializer supports method and parameter serialization, but this doesn't bode well with users that want to manage and create an FSM in a human-readable file. So, I'm going to revisit this issue when addressing the serialization work item; the QuickGraph graph visualizers may have some native support to address this issue.
0 comments:
Post a Comment