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