File Coverage

blib/lib/Set/FA.pm

Criterion	Covered	Total	%
statement	40	43	93.0
branch	8	8	100.0
condition			n/a
subroutine	10	11	90.9
pod	8	8	100.0
total	66	70	94.2

package Set::FA;

use parent 'Set::Object';
use strict;
use warnings;

our $VERSION = '1.08';

# -----------------------------------------------

sub accept
{
	my($self, $input) = @_;
	my($set)          = (ref $self) -> new;

	for my $automaton ($self -> members)
	{
		$set -> insert($automaton) if ($automaton -> accept($input) );
	}

	return $set;

} # End of accept.

# -----------------------------------------------

sub advance
{
	my($self, $input) = @_;

	for my $automaton ($self -> members)
	{
		$automaton -> advance($input);
	}

} # End of advance.

# -----------------------------------------------

sub clone
{
	my($self) = @_;
	my($set)  = (ref $self) -> new;

	for my $automaton ($self -> members)
	{
		$set -> insert($automaton -> clone);
	}

	return $set;

} # End of clone

# -----------------------------------------------

sub final
{
	my($self) = @_;
	my($set)  = (ref $self) -> new;

	for my $automaton ($self -> members)
	{
		$set -> insert($automaton) if ($automaton -> final);
	}

	return $set;

} # End of final.

# -----------------------------------------------

sub id
{
	my($self, $id) = @_;
	my($set)       = (ref $self) -> new;

	for my $automaton ($self -> members)
	{
		$set -> insert($automaton) if ($automaton -> id eq $id);
	}

	return $set;

} # End of id.

# -----------------------------------------------

sub in_state
{
	my($self, $state) = @_;
	my($set)          = (ref $self) -> new;

	for my $automaton ($self -> members)
	{
		$set -> insert($automaton) if ($automaton -> state eq $state);
	}

	return $set;

} # End of in_state.

# -----------------------------------------------

sub reset
{
	my($self) = @_;

	for my $automaton ($self -> members)
	{
		$automaton -> reset;
	}

} # End of reset.

# -----------------------------------------------

sub step
{
	my($self, $input) = @_;

	for my $automaton ($self -> members)
	{
		$automaton -> step($input);
	}

} # End of step.

# -----------------------------------------------

1;

=pod

=head1 NAME

L<Set::FA> - A Set of Discrete Finite Automata

=head1 Synopsis

	#!/usr/bin/perl

	use strict;
	use warnings;

	use Set::FA;
	use Set::FA::Element;

	# --------------------------

	my(@a) = map
	{
		Set::FA::Element -> new
		(
		 accepting   => ['ping'],
		 id          => "a.$_",
		 start       => 'ping',
		 transitions =>
		 [
		  ['ping', 'a', 'pong'],
		  ['ping', '.', 'ping'],
		  ['pong', 'b', 'ping'],
		  ['pong', '.', 'pong'],
		 ],
		)
	} (0 .. 2);

	my(@b) = map
	{
		Set::FA::Element -> new
		(
		 accepting   => ['pong'],
		 id          => "b.$_",
		 start       => 'ping',
		 transitions =>
		 [
		  ['ping', 'a', 'pong'],
		  ['ping', '.', 'ping'],
		  ['pong', 'b', 'ping'],
		  ['pong', '.', 'pong'],
		 ],
		)
	} (0 .. 4);

	my($set)   = Set::FA -> new(@a, @b);
	my($sub_a) = $set -> accept('aaabbaaabdogbbbbbababa');
	my($sub_b) = $set -> final;

	print 'Size of $sub_a: ', $sub_a -> size, ' (expect 3). ',
	'Size of @a: ', scalar @a, ' (expect 3). ',
	'Size of $sub_b: ', $sub_b -> size, ' (expect 5). ',
	'Size of @b: ', scalar @b, ' (expect 5). ', "\n",

=head1 Description

L<Set::FA> provides a mechanism to define and run a set of DFAs.

=head1 Installation

Install L<Set::FA> as you would for any C<Perl> module:

Run:

	cpanm Set::FA

or run:

	sudo cpan Set::FA

or unpack the distro, and then either:

	perl Build.PL
	./Build
	./Build test
	sudo ./Build install

or:

	perl Makefile.PL
	make (or dmake or nmake)
	make test
	make install

=head1 Constructor and Initialization

=head2 Parentage

This class extends L<Set::Object>, meaning L<Set::FA> is a subclass of L<Set::Object>.

For the (long) list of methods available and provided by L<Set::Object>, see that object's
documentation.

=head2 Using new()

C<new()> is called as C<< my($set) = Set::FA -> new(@list_of_dfas) >>.

It returns a new object of type C<Set::FA>.

You may supply a list of L<Set::FA::Element> objects to new.

If the list is empty, you will need to call $set -> insert(@list_of_dfas) to do anything meaningful
with $set.

The new object is a set whose members are all L<Set::FA::Element> objects.

This class allows you to operate on all members of the set simultaneously, as in the
synopsis.

=head1 Methods

=head2 accept($input)

Calls L<Set::FA::Element/accept($input)> on all members of the set. This in turn calls
L<Set::FA::Element/advance($input)> on each member.

Note: This does I<not> mean it calls advance() on the set object.

Returns a L<Set::FA> object containing just the members of the original set which have ended up
in their respective accepting states.

=head2 advance($input)

Calls L<Set::FA::Element/advance($input)> on all members of the set.

Returns nothing.

=head2 clone()

Returns a clone of the set. All references (except for code references) in the
new set point to newly created objects.

=head2 final()

Calls L<Set::FA::Element/final()> on all members of the set.

Returns a L<Set::FA> object containing just the members of the original set which are
in their respective accepting states.

=head2 id($id)

Returns a L<Set::FA> object containing just the members of the original set whose ids
match the $id parameter.

=head2 in_state($state)

Returns a L<Set::FA> object containing just the members of the original set who current
state matches the $state parameter.

=head2 reset()

Calls L<Set::FA::Element/reset()> on all members of the set.

Returns nothing.

=head2 step($input)

Calls L<Set::FA::Element/step($input)> on all members of the set.

Returns nothing.

=head1 Machine-Readable Change Log

The file CHANGES was converted into Changelog.ini by L<Module::Metadata::Changes>.

=head1 Version Numbers

Version numbers < 1.00 represent development versions. From 1.00 up, they are production versions.

=head1 Credit

The code was rewritten to perform exactly as did earlier versions (pre-1.00) of L<Set::FA> and
L<Set::FA::Element>, and hence is essentially the same, line for line.

I've reformatted it, and changed the OO nature and the logging, obviously, but Mark Rogaski, the author of
L<Set::FA> gets the credit for the code.

I've rewritten the documentation from scratch.

=head1 See Also

Before adopting L<Set::FA> (for L<Graph::Easy::Marpa>'s lexer), other DFA modules I looked at were:

=over 4

=item o L<DFA::Kleene>

The author definitely knows what he's doing, but this module addresses a different issue than I
face. It outputs regexps corresponding to the transitions you specify.

=item o L<DFA::Statemap>

This is a wrapper around the State Machine Compiler, to output a SM in Perl. SMC requires Java,
and can output in a range of languages. See L<http://smc.sourceforge.net/>.

SMC looks sophisticated, but it's a rather indirect way of doing things when Perl modules such
as L<Set::FA::Element> are already available.

=item o L<DMA::FSM>

Uses a very old-fashioned style of writing Perl.

=item o FLAT::DSA. See L<FLAT>

A toolkit for manipulating DFAs.

=item o L<IDS::Algorithm::DFA>

Uses an old-fashioned style of writing Perl.

=item o L<MooseX::FSM>

Looks like an unfinished thought-bubble.

=item o L<Parse::FSM>

Outputs a Perl module implementing the FSM you define.

=item o L<The Ragel State Machine Compiler|http://www.complang.org/ragel/>

A non-Perl solution.

That page has lots of interesting links.

=item o L<Shishi>

Doesn't use a transition table, but does allow you to modify the SM while it's running.
You build up a transition network diagram, labouriously, with 1 line of code at a time.

=back

See also L<this Wikipedia article|http://en.wikipedia.org/wiki/Deterministic_finite-state_machine>.

=head1 Support

Email the author, or log a bug on RT:

L<https://rt.cpan.org/Public/Dist/Display.html?Name=Set::FA>.

=head1 Author

L<Set::FA> was written by Mark Rogaski and Ron Savage I<E<lt>[e-mail]<gt>> in 2011.

Home page: L<http://savage.net.au/index.html>.

=head1 Copyright

Australian copyright (c) 2011, Ron Savage.

	All Programs of mine are 'OSI Certified Open Source Software';
	you can redistribute them and/or modify them under the terms of
	The Artistic License, a copy of which is available at:
	http://www.opensource.org/licenses/index.html

=cut