/ 
Set-FA-2.01
River stage one • 1 direct dependent • 1 total dependent
/ Set::FA

NAME

Set::FA - A Set of Discrete Finite Automata

Synopsis

This is scripts/synopsis.1.pl:

#!/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",

Description

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

Installation

Install Set::FA as you would for any 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

Constructor and Initialization

Parentage

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

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

Using new()

"new([@list_of_dfas])" is called as my($set) = Set::FA -> new(@list_of_dfas).

It returns a new object of type Set::FA.

You may supply a list of Set::FA::Element objects to "new([@list_of_dfas])".

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 Set::FA::Element objects.

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

Methods

accept($input)

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

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

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

advance($input)

Calls "advance($input)" in Set::FA::Element on all members of the set.

Returns nothing.

final()

Calls "final()" in Set::FA::Element on all members of the set.

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

id($id)

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

in_state($state)

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

new([@list_of_dfas])

Here, the [] indicate an optional parameter.

The constructor. See "Constructor and Initialization".

reset()

Calls "reset()" in Set::FA::Element on all members of the set.

Returns nothing.

step($input)

Calls "step($input)" in Set::FA::Element on all members of the set.

Returns nothing.

FAQ

See "FAQ" in Set::FA::Element.

Machine-Readable Change Log

The file Changes was converted into Changelog.ini by Module::Metadata::Changes.

Version Numbers

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

Credit

The code was rewritten to perform exactly as did earlier versions (pre-1.00) of Set::FA and 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 Set::FA gets the credit for the code.

I've rewritten the documentation from scratch.

See Also

Before adopting Set::FA (for Graph::Easy::Marpa's lexer), here are some other DFA modules I found on https://metacpan.org:

o 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.

o 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 http://smc.sourceforge.net/.

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

o Dict::FSA

This module is a perl wrapper around fsa, a set of tools based on finite state automata.

See http://www.eti.pg.gda.pl/~jandac/fsa.html.

o DMA::FSM

Uses a very old-fashioned style of writing Perl.

o FLAT::DFA. See FLAT

A toolkit for manipulating DFAs.

o FSA::Engine

A Moose Role to convert an object into a Finite State Machine.

o FSA::Rules

Build simple rules-based state machines in Perl.

o IDS::Algorithm::DFA

Uses an old-fashioned style of writing Perl.

o MooseX::FSM

Looks like an unfinished thought-bubble.

o Parse::FSM

Outputs a Perl module implementing the FSM you define.

o The Ragel State Machine Compiler

A non-Perl solution.

That page has lots of interesting links.

o 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.

See also this Wikipedia article.

Repository

https://github.com/ronsavage/Set-FA

Support

Email the author, or log a bug on RT:

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

Author

Set::FA was written by Mark Rogaski and Ron Savage <ron@savage.net.au> in 2011.

My homepage: http://savage.net.au/index.html

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 Perl License, a copy of which is available at:
http://www.opensource.org/licenses/index.html