/ 
DFA-Simple-0.34
River stage zero No dependents
/ DFA::Simple

NAME

DFA::Simple - A Perl module to implement simple Discrete Finite Automata

SYNOPSIS

my $Obj = new DFA::Simple

or

my $Obj = new DFA::Simple $Transitions;

or

my $Obj = new DFA::Simple $Actions, $StateRules;

$Obj->Actions = [...];
my $Trans = $LP->Actions;

$Obj->StateRules = [...];
my $StateRules = $LP->StateRules;

DESCRIPTION

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:

1. There might be something you want done whenever you enter a given state (Transition Table)
2. There might be something you want done whenever you leave a given state (Transition Table)
3. You can go to some states from the current state (Action table)
4. There are tests to decide whether you should go to that new state (Action table)
5. There are conditional tasks you can do while sitting in that new state (Action table)

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").

The State Definitions, Tests, and Transitions

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):

State

The object has a particular state it is in; a specific state from a set of possible states

Actions

The object when entering or leaving a state may perform some action.

Rules

The object has rules for determining what its next state should be, and how to get there.

Example

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

State is a method that can get the current state or initiate a transition to a new 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

Actions is a method that can set or get the objects list of actions to perform when entering or leaving a particular state.

   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).

StateRules

   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.

Running the machine

To operate the state machine, first prime it:

$Obj->State(0);

Then tell it run a state transition:

$Obj->Check_For_NextState();

AUGMENTED TRANSITION NETWORKS

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).

State Stack

You can push a stack onto the stack, or pop one off. The register frame is saved and restored as well.

Registers

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.

The State Stack

$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.

Hold will save the current state of the automaton, including the registers.
Retrieve will restore the automaton's previously saved state and registers. This is called by a state machine action when it realizes that it is in the wrong state.
Commit will indicate that the previous restore is no longer needed, no more backtracks will be performed. It is called by a state machine action that is confident that it is in the proper state.

Register

$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 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.

DESIGNING RECURSIVE AND AUGMENTED TRANSITION NETWORKS

There are several issues involved with designing ATNs: * Input and Output

Input

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.

Output

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.

All output should be an ATN decides to commit to a branch

Following all paths: special issues

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.

INSTALLATION

Install this module using CPAN, cf. How to install CPAN modules

AUTHOR

Randall Maas

Maintenance by Alexander Becker (asb@cpan.org)