SMC Manual: Section 6

The State Machine Compiler download contains both simple and complex examples using all SMC features - simple transitions, default states, default transitions, state entry and exit actions and pushing and popping. Each example is presented in C, C++, Java, [incr Tcl], VB.net, C#, Groovy, Lua, Python, Perl, PHP, Ruby and Scala. The first examples are the simplest and gradually become more complex.

These examples are in SMC's "example" directory. All examples contain README text files describing what the example does, how to build it and run it.

Example 1

Describes a system that determines whether a string is acceptable or not. The intent is to process a string of bits having a specific pattern: 0*1*

That is:

Anything other than a 0 or a 1 will trigger an Unknown transition, producing an Unacceptable result.
A transition from 1 to 0 is likewise unacceptable.

The State "Error" is defined specifically to collect unacceptable strings. Unknown transitions (regardless of state) and transitions from 1 to 0 both result in a final state of "Error"

We can walk through the string of bits 0000111 which is acceptable to gain some understanding of the functioning of this FSM:

Start in the "Start" state, and walk the bits from left to right.
The first is a 0 and so we enter the "Zero" state.
Subsequent 0's keep the FSM in the Zero state until we see a 1.
This first 1 triggers a One "Transition" which puts the FSM in the "One" state.
Additional ones don't cause any state changes (if we had gotten a zero at this point, we'd transition to the error state).
Finally the "EOS" transition takes place when we reach the end of the string which transitions the FSM to its final "OK" state.

This last transition's "Acceptable" action sets AppClass's acceptable boolean property to true. Conversely, the Error state's EOS transition sets that bit to false (unacceptable).

The OK state is a final state. Once entered, no transitions will get us out.

Example 2

Consider example 2 as a case in refactoring the .sm file.

Notice that the same "Unknown" transition applies for all states (except the OK state).

So, rather than define it tediously and repeatedly for every state, we can place it in the Default state which acts as a fallback mechanism. Now if an "Unknown" transition is encountered in any state, the Default state will handle it on behalf of the current state. It doesn't matter that we now have an unknown transition on OK because we've already reached the end of the string by then. Technically the OK transition now is no longer a "final" state.

The other refactoring is the ability to specify the next state for transitions that don't escape the current state in a relative manner using the 'nil' keyword. 'nil' implies remaining in the current state.

Example 3

This example is the textbook demonstration of a push-down finite state machine. This FSM checks for palindromes using a three character alphabet {0, 1, c}. Palindromes read the same way from left to right as they do from right to left:

Able was I ere I saw Elba

Each side is a mirror image of the other. The 'c' is used to demarcate the middle point (palindromes are odd).

This examples shows SMC push and pop transitions in action. It contains three Maps. The basic behavior of this FSM is to keep pushing the next bit encountered onto the stack until the middle point is reached. The stack acts as a sort of memory for the bits encountered. If you're in Map1 that means you've been encountering zeros. If you're in Map2, that means you've been encountering ones. When you get to the center ('c'), it's a signal to start popping or consuming the stack. When we were pushing, we were always in a map's PushIt state; now that we're popping we move to the map's PopIt state.

To see this in action is to turn on debugging by uncommenting the "setDebugFlag" line in AppClass.java. For strings that at least are in the alphabet (0, 1, c) and that at least have the same number of characters to each side of 'c', you should see that number of pushes follows by the same number of pops.

The point of the algorithm is to make sure the sequence we're about to encounter is a mirror of the sequence we built up to. In other words, that we pop the same digits we've been pushing. Each map knows what the correct digit should be. If you're in OnesMap that means you had originally pushed a one and now you'd better be popping a one...and vice versa for ZerosMap: you better be popping zeros.

So this dictates the transitions for both maps:

In ZerosMap if I pop a zero, we're OK, otherwise we're in error.
In OnesMap if I pop a one, we're OK, otherwise we're in error.

That's the gist of this exercise.

Notice a small nuance in the code: there's an action called emptyStack. Typically all action methods are defined in AppClass but you'll see no such method in AppClass. emptyStack is a reserved action method name defined in FSMContext. SMC looks for such reserved names and makes sure to generate source code that reroutes such calls to context (the FSMContext class) instead of ctxt (the AppClass).

Java, Ant, Python, Perl and Ruby example EX7 uses the push/pop transition in a more realistic way. %map PhoneNumber is used to collect the dialed telephone number. If the dialed number was acceptable, then the PhoneNumber map pops the transition:

pop(DialingDone, callType, areaCode, exchange, local)

where DialingDone is a transition name and callType, areaCode, exchange, local are transition parameters.

The push transition itself is different:

Dialing/push(PhoneNumber::DialTone)

This has the FSM first go to the Dialing state and then push PhoneNumber::DialTone. The popped DialingDone or InvalidDigit transition will be taken from the Dialing state.

PHP example web is an example for building stateless dynamic web pages with a state machine. It implements a simple RPN calculator which preserves its state and calculation stack across HTTP requests with a hidden input field.