path: root/lib/FLAT/PFA.pm

package FLAT::PFA;
use strict;
use base 'FLAT::NFA';
use Carp;

use FLAT::Transition;

use constant LAMBDA => '#lambda';

# 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;
    my $self = $pkg->SUPER::new(@_); # <-- SUPER is FLAT::NFA
    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() }

sub set_starting {
    my ($self, @states) = @_;
    $self->_assert_states(@states);
    $self->{STATES}[$_]{starting} = 1 for @states;
}

# Creates a single start state with epsilon transitions from
# the former start states;
# Creates a single final state with epsilon transitions from
# the former accepting states
sub pinch {
 my $self = shift;
 my $symbol = shift;
 my @starting = $self->get_starting;
 if (@starting > 1) {
   my $newstart = $self->add_states(1);
   map {$self->add_transition($newstart,$_,$symbol)} @starting;
   $self->unset_starting(@starting);
   $self->set_starting($newstart);
 }
 #
 my @accepting = $self->get_accepting;
 if (@accepting > 1) {
   my $newfinal = $self->add_states(1);
   map {$self->add_transition($_,$newfinal,$symbol)} @accepting;
   $self->unset_accepting(@accepting);
   $self->set_accepting($newfinal);
 }
 return;
}

# Implement the joining of two PFAs with lambda transitions
# Note: using epsilon pinches for simplicity
sub shuffle {
    my @pfas = map { $_->as_pfa } @_;
    my $result = $pfas[0]->clone;
    $result->_swallow($_) for @pfas[1 .. $#pfas];
    $result->pinch(LAMBDA);
    $result;
}

##############

sub is_tied {
    my ($self, $state) = @_;
    $self->_assert_states($state);
    return $self->{STATES}[$state]{tied};
}

sub set_tied {
    my ($self, @states) = @_;
    $self->_assert_states(@states);
    $self->{STATES}[$_]{tied} = 1 for @states;
}

sub unset_tied {
    my ($self, @states) = @_;
    $self->_assert_states(@states);
    $self->{STATES}[$_]{tied} = 0 for @states;
}

sub get_tied {
    my $self = shift;
    return grep { $self->is_tied($_) } $self->get_states;
}

##############

# joins two PFAs in a union (or) - no change from NFA
sub union {
    my @pfas = map { $_->as_pfa } @_;    
    my $result = $pfas[0]->clone;    
    $result->_swallow($_) for @pfas[1 .. $#pfas];
    $result->pinch('');
    $result;
}

# joins two PFAs via concatenation  - no change from NFA
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  - no change from NFA
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;
}

sub as_nfa { 
    my $self = shift;
    my $result = FLAT::NFA->new();    
    # Dstates is initially populated with the start state, which 
    # is exactly the set of all nodes marked as a starting node
    my @Dstates = [sort($self->get_starting())]; # I suppose all start states are considered 'tied'
    my %DONE = ();                               # |- what about all accepting states? I think so...
    # the main while loop that ends when @Dstates becomes exhausted
    my %NEW = ();
    while (@Dstates) {
      my $current = pop(@Dstates);
      my $currentid = join(',',@{$current});
      $DONE{$currentid}++;    # mark done
      foreach my $symbol ($self->alphabet(),'') {  # Sigma UNION epsilon
        if (LAMBDA eq $symbol) {
          my @NEXT = ();  
	  my @tmp = $self->successors([@{$current}],$symbol);
	  if (@tmp) {
	    my @pred = $self->predecessors([@tmp],LAMBDA);
            if ($self->array_is_subset([@pred],[@{$current}])) {
              push(@NEXT,@tmp,$self->array_complement([@{$current}],[@pred]));
              @NEXT = sort($self->array_unique(@NEXT));
	      my $nextid = join(',',@NEXT);
	      push(@Dstates,[@NEXT]) if (!exists($DONE{$nextid})); 	            
              # make new states if none exist and track
              if (!exists($NEW{$currentid})) {$NEW{$currentid} = $result->add_states(1)};
              if (!exists($NEW{$nextid}))    {$NEW{$nextid} = $result->add_states(1)   };
	      $result->add_transition($NEW{$currentid},$NEW{$nextid},'');  
            }
	  }
        } else {
	  foreach my $node (@{$current}) {
	    my @tmp = $self->successors([$node],$symbol);	    
	    foreach my $new (@tmp) {
              my @NEXT = ();	      
              push(@NEXT,$new,$self->array_complement([@{$current}],[$node]));
              @NEXT = sort($self->array_unique(@NEXT));
	      my $nextid = join(',',@NEXT);
	      push(@Dstates,[@NEXT]) if (!exists($DONE{$nextid})); 	            
              # make new states if none exist and track
              if (!exists($NEW{$currentid})) {$NEW{$currentid} = $result->add_states(1)};
              if (!exists($NEW{$nextid}))    {$NEW{$nextid} = $result->add_states(1)   };
	      $result->add_transition($NEW{$currentid},$NEW{$nextid},$symbol);	  
	    }
	  }
	}
      }
    }
    $result->set_starting($NEW{join(",",sort $self->get_starting())});
    $result->set_accepting($NEW{join(",",sort $self->get_accepting())});
    return $result;
 }

1;

__END__

=head1 NAME

FLAT::PFA - Parallel finite automata

=head1 SYNOPSIS

A FLAT::PFA object is a finite automata whose transitions are labeled either 
with characters, the empty string (epsilon), or a concurrent line of execution 
(lambda).  It essentially models two FSA in a non-deterministic way such that 
a string is valid it puts the FSA of the shuffled languages both into a final, 
or accepting, state.  A PFA is an NFA, and as such exactly describes a regular 
language.

A PFA contains nodes and states.  A state is made up of whatever nodes happen 
to be active.  There are two transition functions, nodal transitions and state 
transitions.  When a PFA is converted into a NFA, there is no longer a need for 
nodes or nodal transitions, so they go are eliminated.  PFA model state spaces 
much more compactly than NFA, and an N state PFA may represent 2**N non-deterministic 
states. This also means that a PFA may represent up to 2^(2^N) deterministic states.

=head1 USAGE

(not implemented yet)

In addition to implementing the interface specified in L<FLAT> and L<FLAT::NFA>, 
FLAT::PFA objects provide the following PFA-specific methods:

=over

=item $pfa-E<gt>shuffle

Shuffle construct for building a PFA out of a PRE (i.e., a regular expression with
the shuffle operator)

=item $pfa-E<gt>as_nfa

Converts a PFA to an NFA by enumerating all states; similar to the Subset Construction
Algorithm, it does not implement e-closure.  Instead it treats epsilon transitions
normally, and joins any states resulting from a lambda (concurrent) transition
using an epsilon transition.

=back

=head1 AUTHORS & ACKNOWLEDGEMENTS

FLAT is written by Mike Rosulek E<lt>mike at mikero dot comE<gt> and 
Brett Estrade E<lt>estradb at gmail dot comE<gt>.

The initial version (FLAT::Legacy) by Brett Estrade was work towards an 
MS thesis at the University of Southern Mississippi.

Please visit the Wiki at http://www.0x743.com/flat

=head1 LICENSE

This module is free software; you can redistribute it and/or modify it under
the same terms as Perl itself.