[Perl-flat-cvs-notify] blokhead/lib/FLAT PFA.pm,NONE,1.1 NFA.pm,1.7,1.8

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

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

Modified Files:
	NFA.pm 
Added Files:
	PFA.pm 
Log Message:
added PFA.pm place holder, generating more cvs spam :)

Index: NFA.pm
===================================================================
RCS file: /cvsroot/perl-flat/blokhead/lib/FLAT/NFA.pm,v
retrieving revision 1.7
retrieving revision 1.8
diff -C2 -d -r1.7 -r1.8
*** NFA.pm	24 Feb 2006 06:20:25 -0000	1.7
--- NFA.pm	24 Feb 2006 06:49:42 -0000	1.8
***************
*** 282,286 ****
  
  A FLAT::NFA object is a finite automata whose transitions are labeled
! either wtih characters or the empty string (epsilon).
  
  =head1 USAGE
--- 282,286 ----
  
  A FLAT::NFA object is a finite automata whose transitions are labeled
! either with characters or the empty string (epsilon).
  
  =head1 USAGE

--- NEW FILE: PFA.pm ---
package FLAT::PFA;
use strict;
use base 'FLAT::FA';

use FLAT::Transition;

sub new {
    my $pkg = shift;
    my $self = $pkg->SUPER::new(@_);
    $self->{TRANS_CLASS} = "FLAT::Transition";
    return $self;
}

sub singleton {
    my ($class, $char) = @_;
    my $nfa = $class->new;

    if (not defined $char) {
        $nfa->add_states(1);
        $nfa->set_starting(0);
    } elsif ($char eq "") {
        $nfa->add_states(1);
        $nfa->set_starting(0);
        $nfa->set_accepting(0);
    } else {
        $nfa->add_states(2);
        $nfa->set_starting(0);
        $nfa->set_accepting(1);
        $nfa->set_transition(0, 1, $char);
    }
    return $nfa;
}

sub as_pfa {

}

sub as_nfa {

}

sub union {

}

sub concat {

}

sub kleene {

}

sub shuffle {

}

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>, 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