Ron Savage > Set-FA > Set::FA

Download:
Set-FA-1.08.tgz

Dependencies

Annotate this POD

View/Report Bugs
Module Version: 1.08   Source  

NAME ^

Set::FA - A Set of Discrete Finite Automata

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

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() 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.

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.

clone()

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

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.

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.

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), other DFA modules I looked at were:

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 DMA::FSM

Uses a very old-fashioned style of writing Perl.

o FLAT::DSA. See FLAT

A toolkit for manipulating DFAs.

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.

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.

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