[Perl-flat-cvs-notify] perl-flat/lib/FLAT PFA.pm,1.9,1.10

[<per...@li...>]

Update of /cvsroot/perl-flat/perl-flat/lib/FLAT
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv10957/lib/FLAT

Modified Files:
	PFA.pm 
Log Message:
...

Index: PFA.pm
===================================================================
RCS file: /cvsroot/perl-flat/perl-flat/lib/FLAT/PFA.pm,v
retrieving revision 1.9
retrieving revision 1.10
diff -C2 -d -r1.9 -r1.10
*** PFA.pm	18 Apr 2006 21:50:17 -0000	1.9
--- PFA.pm	19 Apr 2006 15:27:43 -0000	1.10
***************
*** 5,9 ****
  
  use FLAT::Transition;
!   
  sub new {
      my $pkg = shift;
--- 5,21 ----
  
  use FLAT::Transition;
! 
! #
! # Note: in a PFA, states are made up of active nodes.  In this implementation, we have
! # decided to retain the functionality of the state functions in FA.pm, although the entities
! # being manipulated are technically nodes, not states.  States are only explicitly tracked
! # once the PFA is serialized into an NFA.  Therefore, the TRANS member of the PFA object is
! # the nodal transition function, gamma.  The state transition function, delta, is not used
! # in anyway, but is derived out of the PFA->NFA conversion process.
! #
! 
! # The new way of doing things eliminated from PFA.pm of FLAT::Legacy is the 
! # need to explicitly track: start nodes, final nodes, symbols, and lambda & epsilon symbols,  
! 
  sub new {
      my $pkg = shift;
***************
*** 11,21 ****
--- 23,139 ----
      $self->{TIED} = [];              # tracks tied nodes
      $self->{ACTIVE_NODES} = [];      # tracks active nodes - could be label like start and final
+     $self->{LAMBDA} = '#lambda';     # special lambda symbol - used internally
      return $self;
  }
  
+ # Singleton is no different than the NFA singleton
+ sub singleton {
+     my ($class, $char) = @_;
+     my $pfa = $class->new;
+     
+     if (not defined $char) {
+         $pfa->add_states(1);
+         $pfa->set_starting(0);
+     } elsif ($char eq "") {
+         $pfa->add_states(1);
+         $pfa->set_starting(0);
+         $pfa->set_accepting(0);
+     } else {
+         $pfa->add_states(2);
+         $pfa->set_starting(0);
+         $pfa->set_accepting(1);
+         $pfa->set_transition(0, 1, $char);
+     }
+     return $pfa;
+ }
+ 
+ # attack of the clones
+ sub as_pfa { $_[0]->clone() }
+ 
+ 
+ # set lambda symbol - temp fix for larger problem of special symbols
+ # like epsilon and lambda
+ sub set_lambda {
+   my $self = shift;
+   $self->{LAMBDA} = $_[0];
+ }
+ 
+ # get lamnda symbol
+ sub get_lambda {
+   my $self = shift;
+   return $self->{LAMBDA};
+ }
+ 
+ # will implement the joining of two PFAs with lambda transitions
  sub shuffle {
    croak "PFA::shuffle is not yet supported";
+   # can't use _swallow, but might be able to use a modifed version of it...
+   # look at FLAT::Legacy
+ }
+ 
+ <<<<<<< PFA.pm
+ # joins two PFAs in a union (or)
+ sub union {
+     my @pfas = map { $_->as_pfa } @_;
+     my $result = $pfas[0]->clone;
+     $result->_swallow($_) for @pfas[1 .. $#pfas];
+     $result;
+ }
+ 
+ # joins two PFAs via concatenation
+ sub concat {
+     my @pfas = map { $_->as_pfa } @_;
+     
+     my $result = $pfas[0]->clone;
+     my @newstate = ([ $result->get_states ]);
+     my @start = $result->get_starting;
+ 
+     for (1 .. $#pfas) {
+         push @newstate, [ $result->_swallow( $pfas[$_] ) ];
+     }
+ 
+     $result->unset_accepting($result->get_states);
+     $result->unset_starting($result->get_states);
+     $result->set_starting(@start);
+     
+     for my $pfa_id (1 .. $#pfas) {
+         for my $s1 ($pfas[$pfa_id-1]->get_accepting) {
+         for my $s2 ($pfas[$pfa_id]->get_starting) {
+             $result->set_transition(
+                 $newstate[$pfa_id-1][$s1],
+                 $newstate[$pfa_id][$s2], "" );
+         }}
+     }
+ 
+     $result->set_accepting(
+         @{$newstate[-1]}[ $pfas[-1]->get_accepting ] );
+ 
+     $result;
+ }
+ 
+ # forms closure around a the given PFA
+ sub kleene {
+     my $result = $_[0]->clone;
+     
+     my ($newstart, $newfinal) = $result->add_states(2);
+     
+     $result->set_transition($newstart, $_, "")
+         for $result->get_starting;
+     $result->unset_starting( $result->get_starting );
+     $result->set_starting($newstart);
+ 
+     $result->set_transition($_, $newfinal, "")
+         for $result->get_accepting;
+     $result->unset_accepting( $result->get_accepting );
+     $result->set_accepting($newfinal);
+ 
+     $result->set_transition($newstart, $newfinal, "");    
+     $result->set_transition($newfinal, $newstart, "");
+     
+     $result;
  }
  
+ # reversal should be like the transpose of the nodal transitoin
+ # matrix, but I still have to make sure 
  sub reverse {
     croak "PFA::reverse is not yet supported";