DFA::Simple - A Perl module to implement simple Discrete Finite Automata
my $Obj = new DFA::Simple
or
my $Obj = new DFA::Simple $Transitions;
my $Obj = new DFA::Simple $Actions, $StateRules; $Obj->Actions = [...]; my $Trans = $LP->Actions; $Obj->StateRules = [...]; my $StateRules = $LP->StateRules;
my $Obj = new DFA::Simple $Actions,[States];
This creates a simple automaton with a finite number of individual states. The short version is that state numbers are just indices into the array.
The state basically binds the rest of the machine together:
This structure may remind you of the SysV run-level concepts. It is very similar.
At run time you don't typically feed any state numbers to the finite machine; you ignore them. Rather your program may read inputs or such. The tests for the state transition would examine this input, or some other variables to decide which new state to go to. Whenever your code has gotten enough input, it would call the Check_For_NextState() method. This method runs through the tests, and carries out the state transitions ("firing the rules").
Check_For_NextState()
As for where the state definitions, tests, and transitions come from: you have to define them yourself, or write a program to do that. There are techniques for converting Phase Structure grammars into state machines (usually thru converting it to Chomsky Normal form, and such), or by drawing bubble diagrams. In the case of the bubble diagram, I usually just number each bubble sequentially from left to right. The arc (and its condition) will tell me most of how to build the Action Table. What the bubble is supposed to do will tell me how to build the Transition Table and the last column of the Action Table.
To support these, the object is composed of the following three things (with methods to match):
The object has a particular state it is in; a specific state from a set of possible states
The object when entering or leaving a state may perform some action.
The object has rules for determining what its next state should be, and how to get there.
Before we get into the deep details, I'll present a quick example. First, here is the output:
[randym@a Out]$ perl tmp.pl Intro I will force us to silently go to state 1, then 2, then 3: Greetings Am Here (in state 1) Bye Am Here (in state 3) Resetting: Intro I will force us to fail to go to a new state: Unusual circumstances? at tmp.pl line 54
And here is the example code:
use DFA::Simple; #A table of what to do when entering or leaving a state. my $Transitions =[ #Say "Intro" when entering state; do nothing when leaving [sub {print "Intro\n";}, undef], #Say "Greetings" when entering state, do nothing when leaving [sub {print "Greetings\n";}, undef], #When entering, do nothing, when leaving do nothing [undef,undef], #When entering say "Bye", when leaving do nothing [sub {print "Bye\n";}, undef], ]; # A global variable my $BogusTest=0; # Our state table. my $States =[ #State #0 [ #Next State, Test that must be true or return true if we are to go #into that state, what we do while /in/ that state [1, sub{$BogusTest}, sub{print "Am Here (in state 1)\n"}], #We can't go to any other state ], #State 1 [ # We can go to state #2 from state #1 if the test succeeds, but we # don't really do anything there [2, sub{$BogusTest}, ], ], #State 2 [ #We can go to state #1 again, but we do nothing [1, sub{$BogusTest}, ], # If the above test(s) fail, the undef below will force us to go # into state #3 [3, undef, sub {print "Am Here (in state 3)\n";}], ], ]; my $F=new DFA::Simple $Transitions, $States; $F->State(0); print "\nI will force us to silently go to state 1, then 2, then 3:\n"; $BogusTest=1; #Drive the state machine thru one transition $F->Check_For_NextState(); #Drive the state machine thru one transition $F->Check_For_NextState(); #Force us to go to state 3 $BogusTest=0; #Drive the state machine thru one transition $F->Check_For_NextState(); print "\nReseting:\n"; $F->State(0); print "I will force us to fail to go to a new state:\n"; $BogusTest=0; $F->Check_For_NextState();
State is a method that can get the current state or initiate a transition to a new state.
State
my $S = $Obj->State; $Obj->State($NewState);
The last one leaves the current state and goes to the specified NewState. If the current state is defined, its StateExitCodeRef will be called (see below). Then the new states StateEnterCodeRef will be called (if defined) (see below). Caveat, no check is made to see if the new state is the same as the old state; this can be used to `reset' the state.
Actions is a method that can set or get the objects list of actions to perform when entering or leaving a particular state.
Actions
my $Actions = $Obj->Actions; $Obj->Actions([ [StateEnterCodeRef, StateExitCodeRef], ]);
Actions is an array reference describing what to do when entering and leaving various states. When a state is entered, its StateEnterCodeRef will be called (if defined). When a state is left (as in going to a new state) its StateExitCodeRef will be called (if defined).
my $StateRules = [ #Rules for state 0 [ [NextState, Test, Thing to do after getting there ], #Rules for state 1 [ ... ], ];
The StateRules is a set of tables used to select the next state. For the current state, each item in the table is sequentially examined. Each rule has a test to see if we should perform that action. The test is considered to have `passed' if it is undefined, or the coderef returns a true. The first rule with a test that passes is used -- the state is changed, and the action is carried out.
The next section describes a different method of determining which rule to employ.
To operate the state machine, first prime it:
$Obj->State(0);
Then tell it run a state transition:
$Obj->Check_For_NextState();
The state machine has a second mode of operation -- every rule with a test that passes is considered. Since this is nondeterministic (we can't tell which rule is the correct one), this machine also employs special rollback mechanisms to undo choosing the wrong rule. This type of state machine is called an 'Augmented Transition Network.'
For the most part, augmented transition networks are just like the state machines described earlier, but they also have two more tables (and four more registers).
You can push a stack onto the stack, or pop one off. The register frame is saved and restored as well.
The object has the method for storing and retrieving information about its processing. Everything that you may want to have undone should be stored here. When the state machine decides it won't undo anything, then it can pass the information to the rest of the system.
$Obj->Hold; $Obj->Retrieve; $Obj->Commit;
The nondeterminancy is handled in a guess and back up fashion. If more than one transition rule is possible, the current state (including the registers) is saved. Each of the possible transition rules is run; if it executes Retrieve, the current state will be retrieved, and the next eligible transition will be attempted.
Retrieve
Hold
Commit
$Obj->Register->{'name'}='fred';
Register is a method that can set or get the objects register reference. This is a information that the actions, conditions, or transitions can employ in their processing. The reference can be anything.
Register
Register is important, since it is the automatons mechanism for undoing actions. The data is saved before a questionable action is carried out, and tossed out when a Retrieve is called. It is otherwise not used by the object implementation.
There are several issues involved with designing ATNs: * Input and Output
All input should be carefully thought out in an ATN -- this is for two reasons:
ATNs can back-up and retry different states, and
In multithreaded environments, several branches of the ATN may be simultaneously operating.
Some things to watch out for: reading from files, popping stuff off of global lists, things like that. The current file position may change unexpectedly.
All IO should be carefully thought out in an ATN -- this is because ATNs can back-up and retry different states, possibly invaliding any of the ATNs results.
print or other file writes any commands that affect the system (link, unlink, rename, etc.) enqueue or otherwise changing any Perl variable.
enqueue
All output should be an ATN decides to commit to a branch
If you choose the option of having all the possible paths taken, there are some special issues. First: what will the new state and registers be? In this case, the registers are must all be.
Be careful in single commit ATNs, with several nested branches. These can lead to very inefficient scenarios, due to the difficulty stop all of the branches of investigation.
Install this module using CPAN, cf. How to install CPAN modules
Randall Maas
Maintenance by Alexander Becker (asb@cpan.org)
To install DFA::Simple, copy and paste the appropriate command in to your terminal.
cpanm
cpanm DFA::Simple
CPAN shell
perl -MCPAN -e shell install DFA::Simple
For more information on module installation, please visit the detailed CPAN module installation guide.