[Perl-flat-cvs-notify] blokhead/lib/FLAT NFA.pm,1.5,1.6

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

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

Modified Files:
	NFA.pm 
Log Message:
added NFA->contains, NFA->trace methods. now we can actually *use* these
  regular languages..



Index: NFA.pm
===================================================================
RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/NFA.pm,v
retrieving revision 1.5
retrieving revision 1.6
diff -C2 -d -r1.5 -r1.6
*** NFA.pm	23 Feb 2006 19:46:12 -0000	1.5
--- NFA.pm	24 Feb 2006 01:04:52 -0000	1.6
***************
*** 38,55 ****
      
      my $result = $nfas[0]->clone;
-     my @newstate = ([ $result->get_states ]);
      
!     for (1 .. $#nfas) {
!         push @newstate, [ $result->_swallow( $nfas[$_] ) ];
!     }
  
!     my $newstart = $result->add_states(1);
!     $result->unset_starting($result->get_states);
!     $result->set_starting($newstart);
      
!     for my $nfa_id (0 .. $#nfas) {
!         $result->set_transition( $newstart, $newstate[$nfa_id][$_], "" )
!             for $nfas[$nfa_id]->get_starting;
!     }
  
      $result;
--- 38,57 ----
      
      my $result = $nfas[0]->clone;
      
!     $result->_swallow($_) for @nfas[1 .. $#nfas];
  
! #    my @newstate = ([ $result->get_states ]);
! #    for (1 .. $#nfas) {
! #        push @newstate, [ $result->_swallow( $nfas[$_] ) ];
! #    }
! 
! #    my $newstart = $result->add_states(1);
! #    $result->unset_starting($result->get_states);
! #    $result->set_starting($newstart);
      
! #    for my $nfa_id (0 .. $#nfas) {
! #        $result->set_transition( $newstart, $newstate[$nfa_id][$_], "" )
! #            for $nfas[$nfa_id]->get_starting;
! #    }
  
      $result;
***************
*** 179,182 ****
--- 181,207 ----
  
  
+ sub contains {
+     my ($self, $string) = @_;
+ 
+     my @active = $self->epsilon_closure( $self->get_starting );    
+     for my $char (split //, $string) {
+         return 0 if ! @active;
+         @active = $self->epsilon_closure( $self->successors(\@active, $char) );
+     }
+     return !! grep { $self->is_accepting($_) } @active;
+ }
+ 
+ sub trace {
+     my ($self, $string) = @_;
+ 
+     my @trace = ([ $self->epsilon_closure( $self->get_starting ) ]);
+     
+     for my $char (split //, $string) {
+         push @trace,
+             [ $self->epsilon_closure( $self->successors($trace[-1], $char) ) ];
+     }
+     return @trace;
+ }
+ 
  ############