perl-flat-cvs-notify Mailing List for The Perl Formal Language Toolkit (Page 3)

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

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";

2006	Jan	Feb (32)	Mar (25)	Apr (13)	May (3)	Jun	Jul	Aug (1)	Sep (5)	Oct (2)	Nov	Dec (1)
2007	Jan	Feb (28)	Mar (6)	Apr	May (3)	Jun	Jul	Aug	Sep	Oct	Nov	Dec

perl-flat-cvs-notify Mailing List for The Perl Formal Language Toolkit (Page 3)

perl-flat-cvs-notify — notifies subscribers of cvs commits