Notes on String Generation

From The Perl Formal Language Toolkit

The current string dump is available via fash, and simply creates strings that result from all acyclic paths from the start state of a DFA to each of the accepting states. For the dirty details of the DFA string generation techniques I've utilized thus far, please see the DFA string generation techniques page. A related write on the recursively generated iterators is available at PerlMonks.

Example usage:

#!/usr/bin/env perl
use strict;
use warnings;

use FLAT::DFA;
use FLAT::NFA;
use FLAT::PFA;
use FLAT::Regex::WithExtraOps;

my $PRE = "abc&(def)*";
my $dfa = FLAT::Regex::WithExtraOps->new($PRE)->as_pfa->as_nfa->as_dfa->as_min_dfa->trim_sinks;

my $next = $dfa->new_acyclic_string_generator;

print "PRE: $PRE\n";
print "Acyclic:\n";
while (my $string = $next->()) {
  print "  $string\n";
}

$next = $dfa->new_deepdft_string_generator();
print "Deep DFT (default):\n";
for (1..10) {
 while (my $string = $next->()) {
   print "  $string\n";
   last;
  }
}

$next = $dfa->new_deepdft_string_generator(5);
print "Deep DFT (5):\n";
for (1..10) {
  while (my $string = $next->()) {
    print "  $string\n";
    last;
  }
}

Output:

PRE: abc&(def)*
Acyclic:
  deabfc
  deabcf
  dabcef
  dabefc
  dabecf
  daebfc
  daebcf
  abc
  adbcef
  adbefc
  adbecf
  adebfc
  adebcf
Deep DFT (default):
  deabfdcef
  deabfc
  deabcf
  deafbdcef
  deafbdecf
  deafbc
  deafdbcef
  deafdbefc
  deafdbecf
  dabcef
Deep DFT (5):
  defdefdefdefdeabfdcef
  defdefdefdefdeabfdcefdef
  defdefdefdefdeabfdcefdefdef
  defdefdefdefdeabfdcefdefdefdef
  defdefdefdefdeabfdcefdefdefdefdef
  defdefdefdefdeabfdefdcef
  defdefdefdefdeabfdefdcefdef
  defdefdefdefdeabfdefdcefdefdef
  defdefdefdefdeabfdefdcefdefdefdef
  defdefdefdefdeabfdefdcefdefdefdefdef

Future goals for this include implementing this such that:

• cycles in the DFA (ala closures) may be explored utilizing a modify depth first search algorithm; this will allow for much greater amount of control when creating strings
• implementing an iterative version of these algorithms that allows one to grab the next string on an as-needed basis

The uses are not immediately obviously, but once there is a tool that will generate some set of strings based on a regular expression, the problems that this tool solves will begin to appear.