Goals

From The Perl Formal Language Toolkit

Contents 1 Short Term 1.1 String Generation 2 Medium Term 2.1 Documentation 2.2 DFA->RE 2.3 Hyper-DFA Minimization 2.4 Simulated Execution of NFA 3 Long Term

Short Term

String Generation

• iterative string pump that returns random strings - this is as simple as changing the call stack management from a pop/push situation preserving the depth first nature of the recursiveness to randomly selecting subs in the stack to call at random; initialization could allow an addition variable to seed the randomness; this obviously wouldn't guarantee any sort of reproducability

• update test(5) to use random PRE w/string gen and validation

Medium Term

Documentation

• user docs
• update and clarify POD

DFA->RE

The XFA implementation will facilitate this by providing for a state elimination algorithm, whose successive application ultimately yields an equivalent regular expression.

Hyper-DFA Minimization

I'd like to implement the hyper-minimization algorithm presented at http://www.ianab.com/hyper/.

Simulated Execution of NFA

The simulation of executing a string over an NFA could be accomplished easily using a breadth-first descent over the NFA for each non-deterministic path taken. The question is, how much faster would string validation be versus a DFA when taking into account no longer needing to convert an NFA to a DFA? Also, what would the memory trade offs be?

Long Term

• implementing a PRE transformation routine that will reduce the concurrency expressed in PREs using some basic transformation rules. Think Math::Symbolic, but for regular expressions.
• ability to attach data objects to symbols; this includes anonymous subroutines (that handle defined events) and data structures;
• limited support for Perl regular expressions - though this is not really the intent of this package, it may be useful and attractive to others
• (very long term) features similar to Ragel, the state machine compiler;