Name

Data::NFA - Non deterministic finite state machine from regular expression.

Synopsis

Create a non deterministic finite state machine from a regular expression which can then be converted into a deterministic finite state machine by Data::DFA and used to parse sequences of symbols.

For example, the regular expression:

((a|b)*)**4

produces the following machine:

use Data::NFA qw(:all);
use Data::Table::Text qw(:all);
use Test::More qw(no_plan);

my $N = 4;

my $s = q(zeroOrMore(choice(element("a"), element("b"))));

my $nfa = eval qq(fromExpr(($s)x$N));

ok $nfa->printNws("((a|b)*)**$N: ") eq nws <<END;
((a|b)*)**4:
Location  F  Transitions  Jumps
     0  1  { a => 1 }   [2, 4, 6, 8, 10, 12, 14, 16]
     1  1  undef        [0, 2, 3, 4, 6, 8, 10, 12, 14, 16]
     2  0  { b => 3 }   undef
     3  1  undef        [0, 2, 4, 6, 8, 10, 12, 14, 16]
     4  1  { a => 5 }   [6, 8, 10, 12, 14, 16]
     5  1  undef        [4, 6, 7, 8, 10, 12, 14, 16]
     6  0  { b => 7 }   undef
     7  1  undef        [4, 6, 8, 10, 12, 14, 16]
     8  1  { a => 9 }   [10, 12, 14, 16]
     9  1  undef        [8, 10, 11, 12, 14, 16]
    10  0  { b => 11 }  undef
    11  1  undef        [8, 10, 12, 14, 16]
    12  1  { a => 13 }  [14, 16]
    13  1  undef        [12, 14, 15, 16]
    14  0  { b => 15 }  undef
    15  1  undef        [12, 14, 16]
    16  1  undef        undef
END

Description

The following sections describe the methods in each functional area of this module. For an alphabetic listing of all methods by name see Index.

Construct regular expression

Construct a regular expression that defines the language to be parsed using the following combining operations which can all be imported:

element($)

One element. An element can also be represented by a string or number

   Parameter  Description        
1  $label     Transition symbol

Example:

my $nfa = fromExpr(element("a"));

ok $nfa->printNws("Element: a") eq nws <<END;
Element: a
Location  F  Transitions
       0  0  { a => 1 }
       1  1  undef

END

my $nfa = fromExpr(q(b));

ok $nfa->printNws("Element: b") eq nws <<END;
Element: b
Location  F  Transitions
       0  0  { b => 1 }
       1  1  undef

END

my $nfa = fromExpr(2);

ok $nfa->printNws("Element: 2") eq nws <<END;
Element: 2
Location  F  Transitions
       0  0  { 2 => 1 }
       1  1  undef

END

This is a static method and so should be invoked as:

Data::NFA::element

This method can be imported via:

use Data::NFA qw(element)

sequence(@)

Sequence of elements and/or symbols.

   Parameter  Description  
1  @elements  Elements

Example:

my $nfa = fromExpr(sequence(element("a"), element("b")));

ok $nfa->printNws("Sequence: ab") eq nws <<END;
Sequence: ab
Location  F  Transitions
       0  0  { a => 1 }
       1  0  { b => 2 }
       2  1  undef
END

This is a static method and so should be invoked as:

Data::NFA::sequence

This method can be imported via:

use Data::NFA qw(sequence)

optional(@)

An optional sequence of elements and/or symbols.

   Parameter  Description  
1  @element   Elements

Example:

my $nfa = fromExpr(element("a"), optional(element("b")), element("c"));

ok $nfa->printNws("Optional: ab?c") eq nws <<END;
Optional: ab?c
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [2]
       2  0  { c => 3 }   undef
       3  1  undef        undef
END

my $nfa = fromExpr

(element("a"),

oneOrMore(choice(qw(b c))),

optional(element("d")),

element("e")

);

ok $nfa->printNws("a(b|c)+d?e :") eq nws <<END;
a(b|c)+d?e :
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3 .. 6]
       3  0  { c => 4 }   undef
       4  0  undef        [1, 3, 5, 6]
       5  0  { d => 6 }   [6]
       6  0  { e => 7 }   undef
       7  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::optional

This method can be imported via:

use Data::NFA qw(optional)

zeroOrMore(@)

Zero or more repetitions of a sequence of elements and/or symbols.

   Parameter  Description  
1  @element   Elements

Example:

my $nfa = fromExpr(element("a"), zeroOrMore(element("b")), element("c"));

ok $nfa->printNws("Zero Or More: ab*c") eq nws <<END;
Zero Or More: ab*c
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3]
       3  0  { c => 4 }   undef
       4  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::zeroOrMore

This method can be imported via:

use Data::NFA qw(zeroOrMore)

oneOrMore(@)

One or more repetitions of a sequence of elements and/or symbols.

   Parameter  Description  
1  @element   Elements

Example:

my $nfa = fromExpr(element("a"), oneOrMore(element("b")), element("c"));

ok $nfa->printNws("One or More: ab+c") eq nws <<END;
One or More: ab+c
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   undef
       2  0  undef        [1, 3]
       3  0  { c => 4 }   undef
       4  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::oneOrMore

This method can be imported via:

use Data::NFA qw(oneOrMore)

choice(@)

Choice from amongst one or more elements and/or symbols.

   Parameter  Description                 
1  @elements  Elements to be chosen from

Example:

my $nfa = fromExpr(element("a"),

choice(element("b"), element("c")),

element("d"));

ok $nfa->printNws("Choice: (a(b|c)d") eq nws <<END;
Choice: (a(b|c)d
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [4]
       3  0  { c => 4 }   undef
       4  0  { d => 5 }   undef
       5  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::choice

This method can be imported via:

use Data::NFA qw(choice)

except(@)

Choice from amongst all symbols except the ones mentioned

   Parameter  Description                     
1  @elements  Elements not to be chosen from

Example:

my $nfa = fromExpr(choice(qw(a b c)), except(qw(c x)), choice(qw(a b c)));

ok $nfa->printNws("(a|b|c)(c!x)(a|b|c): ") eq nws <<END;
(a|b|c)(c!x)(a|b|c):
Location  F  Transitions  Jumps
   0      0  { a => 1 }   [2, 4]
   1      0  undef        [5, 7]
   2      0  { b => 3 }   undef
   3      0  undef        [5, 7]
   4      0  { c => 5 }   undef
   5      0  { a => 6 }   [7]
   6      0  undef        [8, 10, 12]
   7      0  { b => 8 }   undef
   8      0  { a => 9 }   [10, 12]
   9      1  undef        [13]
  10      0  { b => 11 }  undef
  11      1  undef        [13]
  12      0  { c => 13 }  undef
  13      1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::except

This method can be imported via:

use Data::NFA qw(except)

Non Deterministic finite state machine

fromExpr(@)

Create an NFA from a regular expression.

   Parameter  Description  
1  @expr      Expressions

Example:

my $nfa = fromExpr

(element("a"),

oneOrMore(choice(qw(b c))),

optional(element("d")),

element("e")

);

ok $nfa->printNws("a(b|c)+d?e :") eq nws <<END;
a(b|c)+d?e :
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3 .. 6]
       3  0  { c => 4 }   undef
       4  0  undef        [1, 3, 5, 6]
       5  0  { d => 6 }   [6]
       6  0  { e => 7 }   undef
       7  1  undef        undef
END

This is a static method and so should be invoked as:

Data::NFA::fromExpr

print($$$)

Print the current state of the finite automaton. If it is non deterministic, the non deterministic jumps will be shown as well as the transitions table. If deterministic, only the transitions table will be shown.

   Parameter  Description                             
1  $states    States                                  
2  $title     Title                                   
3  $print     Print to STDERR if 2 or to STDOUT if 1

Example:

my $nfa = fromExpr

(element("a"),

oneOrMore(choice(qw(b c))),

optional(element("d")),

element("e")

);

ok $nfa->printNws("a(b|c)+d?e :") eq nws <<END;
a(b|c)+d?e :
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3 .. 6]
       3  0  { c => 4 }   undef
       4  0  undef        [1, 3, 5, 6]
       5  0  { d => 6 }   [6]
       6  0  { e => 7 }   undef
       7  1  undef        undef
END

printNws($$$)

   Parameter  Description                             
1  $states    States                                  
2  $title     Title                                   
3  $print     Print to STDERR if 2 or to STDOUT if 1

symbols($)

Return an array of all the transition symbols.

   Parameter  Description  
1  $states    States

Example:

my $nfa = fromExpr

(element("a"),

oneOrMore(choice(qw(b c))),

optional(element("d")),

element("e")

);

ok $nfa->printNws("a(b|c)+d?e :") eq nws <<END;
a(b|c)+d?e :
Location  F  Transitions  Jumps
       0  0  { a => 1 }   undef
       1  0  { b => 2 }   [3]
       2  0  undef        [1, 3 .. 6]
       3  0  { c => 4 }   undef
       4  0  undef        [1, 3, 5, 6]
       5  0  { d => 6 }   [6]
       6  0  { e => 7 }   undef
       7  1  undef        undef
END

is_deeply ['a'..'e'], [$nfa->symbols];

isFinal($$)

Whether this is a final state or not

   Parameter   Description    
1  $states     States         
2  $stateName  Name of state

Example:

ok $nfa->printNws("Element: a") eq nws <<END;
Element: a
Location  F  Transitions
       0  0  { a => 1 }
       1  1  undef

END

ok  $nfa->isFinal(1);

ok !$nfa->isFinal(0);

ok $nfa->printNws("Element: b") eq nws <<END;
Element: b
Location  F  Transitions
       0  0  { b => 1 }
       1  1  undef

END

ok $nfa->printNws("Element: 2") eq nws <<END;
Element: 2
Location  F  Transitions
       0  0  { 2 => 1 }
       1  1  undef

END

allTransitions($)

Return all transitions in the NFA as {stateName}{symbol} = [reachble states]

   Parameter  Description  
1  $states    States

Example:

ok $nfa->printNws("a*a* 1: ") eq nws <<END;
a*a* 1:
Location  F  Transitions  Jumps
       0  1  { a => 1 }   [2, 4]
       1  1  undef        [0, 2, 4]
       2  1  { a => 3 }   [4]
       3  1  undef        [2, 4]
       4  1  undef        undef
END

is_deeply $nfa->allTransitions, {

"0" => { a => [0 .. 4] },

"1" => { a => [0 .. 4] },

"2" => { a => [2, 3, 4] },

"3" => { a => [2, 3, 4] },

"4" => { a => [] },

};

Private Methods

fromExpr2($$$)

Create an NFA from a regular expression.

   Parameter  Description                                                                                                                                                              
1  $states    States                                                                                                                                                                   
2  $expr      Regular expression constructed from L<element|/element> L<sequence|/sequence> L<optional|/optional> L<zeroOrMore|/zeroOrMore> L<oneOrMore|/oneOrMore> L<choice|/choice>  
3  $symbols   Set of symbols used by the NFA.

propogateFinalState($)

Mark the states that can reach the final state with a jump as final

   Parameter  Description  
1  $states    States

statesReachableViaJumps($$)

Find the names of all the states that can be reached from a specified state via jumps alone

   Parameter   Description          
1  $states     States               
2  $StateName  Name of start state

printWithJumps($$$)

Print the current state of an NFA with jumps.

   Parameter  Description                             
1  $states    States                                  
2  $title     Title                                   
3  $print     Print to STDERR if 2 or to STDOUT if 1

printWithOutJumps($$$)

Print the current state of an NFA without jumps

   Parameter  Description                             
1  $states    States                                  
2  $title     Title                                   
3  $print     Print to STDERR if 2 or to STDOUT if 1

statesReachableViaSymbol($$$$)

Find the names of all the states that can be reached from a specified state via a specified symbol and all the jumps available.

   Parameter   Description                   
1  $states     States                        
2  $StateName  Name of start state           
3  $symbol     Symbol to reach on            
4  $cache      A hash to be used as a cache

Index

1 allTransitions

2 choice

3 element

4 except

7 isFinal

10 print

11 printNws

12 printWithJumps

13 printWithOutJumps

14 propogateFinalState

15 sequence

16 statesReachableViaJumps

17 statesReachableViaSymbol

18 symbols

19 zeroOrMore

Exports

All of the following methods can be imported via:

use Data::NFA qw(:all);

Or individually via:

use Data::NFA qw(<method>);

1 choice

2 element

3 except

Installation

This module is written in 100% Pure Perl and, thus, it is easy to read, use, modify and install.

Standard Module::Build process for building and installing modules:

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

Author

philiprbrenan@gmail.com

http://www.appaapps.com

Copyright

This module is free software. It may be used, redistributed and/or modified under the same terms as Perl itself.

To install Data::NFA, copy and paste the appropriate command in to your terminal.

cpanm

cpanm Data::NFA

CPAN shell

perl -MCPAN -e shell
install Data::NFA

For more information on module installation, please visit the detailed CPAN module installation guide.

	Global
`s`	Focus search bar
`?`	Bring up this help dialog

	GitHub
`g` `p`	Go to pull requests
`g` `i`	go to github issues (only if github is preferred repository)

	POD
`g` `a`	Go to author
`g` `c`	Go to changes
`g` `i`	Go to issues
`g` `d`	Go to dist
`g` `r`	Go to repository/SCM
`g` `s`	Go to source
`g` `b`	Go to file browse

	Search terms
module: (e.g. module:Plugin)
distribution: (e.g. distribution:Dancer auth)
author: (e.g. author:SONGMU Redis)
version: (e.g. version:1.00)

Name

Synopsis

Description

Construct regular expression

element($)

sequence(@)

optional(@)

zeroOrMore(@)

oneOrMore(@)

choice(@)

except(@)

Non Deterministic finite state machine

fromExpr(@)

print($$$)

printNws($$$)

symbols($)

isFinal($$)

allTransitions($)

Private Methods

fromExpr2($$$)

propogateFinalState($)

statesReachableViaJumps($$)

printWithJumps($$$)

printWithOutJumps($$$)

statesReachableViaSymbol($$$$)

Index

Exports

Installation

Author

Copyright

Module Install Instructions