|
Sat Sep 8 01:40:18 EDT 2007
Perl-FLAT Update
--
Most of my current activities have been related to getting the
fash utility into a useful state. Currently, it is a shell
script that simply provides a simplified interface to the obtuse,
"perl -MFLAT -e xx", idiom that I've forced upon myself.
As a result, I also moved all the command line interface stuff
out of the base FLAT.pm file. The file currently implementing
all command line functions is FLAT/CMD.pm, but I may further sub-
divide based on functionality.
I've been trying to work out how how to reduce a DFA into a regu-
lar expression using state elimination, and I feel like I am
pretty close. HMU outlines a method, but I am too dense to real-
ly understand what they are doing - but I have a feeling that
what I've come up with is pretty close.
In addition to inplementing a function that will get an equiva-
lent regular expression out of a DFA, I am also looking at imple-
menting a feature that will allow the pumping of valid strings in
DFAs that include closures. Currently, all strings are created
by tracing all acyclic paths from the start state to any of the
accepting states. This approach gets all strings from a DFA with
no cycles, but totally misses the mark for more interesting DFAs
- like the ones that result from the shuffle of closed strings.
The algorithm is one I designed, and is based on the traditional
depth first search of a directed graph. It is sure not to be
new, but some of the things I've come up with are pretty darn in-
teresting to me.
In any case, I hope to have both the DFA->RE feature and the ad-
vanced string pump completed by the end of this semester. In-
cluded will be full descriptions of the algorthms that I end up
implementing.
Lastly, I am taking a theory class this semester - which I be-
lieve will motivate me to increase the set of features. Stay
tuned!
--
Powered by vee
Copyright © 2006-2008
|
|