mersenneforum.org > Math Regular expressions (or DFA?)
 Register FAQ Search Today's Posts Mark Forums Read

 2009-12-09, 06:38 #1 CRGreathouse     Aug 2006 176116 Posts Regular expressions (or DFA?) This is theoretical computer science rather than mathematics per se, unless you call TCS math -- I typically do. But I couldn't find a better forum. I'm looking for a practical algorithm -- or, much better, a program -- that simplifies an arbitrary regular expression. Of course a regular language can be defined by a DFA just as easily as a regular expression, and converting between the two shouldn't cause that much of a blowup, so I think an algorithm/program for simplifying a DFA would be almost as good. Anyone know of such a thing? I know that this is a theoretically hard task, but I'd like to do it anyway. On a not-entirely-unrelated note: Suppose I had a Myhill-Nerode proof (a finite set of equivalence classes) that a given language was regular. Is there a way to unwind this to get an actual regex or DFA? At the moment I can't even find one... making the above moot at the moment. I merely suspect that when I build it, the expression will be unnecessarily unwieldy and in need of simplification.
2009-12-09, 11:59   #2
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by CRGreathouse This is theoretical computer science rather than mathematics per se, unless you call TCS math -- I typically do. But I couldn't find a better forum. I'm looking for a practical algorithm -- or, much better, a program -- that simplifies an arbitrary regular expression. Of course a regular language can be defined by a DFA just as easily as a regular expression, and converting between the two shouldn't cause that much of a blowup, so I think an algorithm/program for simplifying a DFA would be almost as good. Anyone know of such a thing? I know that this is a theoretically hard task, but I'd like to do it anyway. On a not-entirely-unrelated note: Suppose I had a Myhill-Nerode proof (a finite set of equivalence classes) that a given language was regular. Is there a way to unwind this to get an actual regex or DFA? At the moment I can't even find one... making the above moot at the moment. I merely suspect that when I build it, the expression will be unnecessarily unwieldy and in need of simplification.
I checked my copy of Hopcroft & Ullman's book on Automata and Languages
and could find nothing. Perhaps Myhill's original paper on representations
of events might help? I think it dates back to the late 50's/early 60's.

I have not looked at this stuff in 35 years......

 2009-12-09, 12:32 #3 Raman Noodles     "Mr. Tuch" Dec 2007 Chennai, India 3×419 Posts Does the Java Formal Language & Automata Package from the website jflap.org help you out? I have already mentioned about this software within another thread, before itself. Last fiddled with by Raman on 2009-12-09 at 12:34
2009-12-09, 19:56   #4
CRGreathouse

Aug 2006

32×5×7×19 Posts

I realized last night that my second question is trivial -- it's easy enough to convert the proof to a DFA, which can be converted to a regular expression in turn. My main question about regex minimization still remains.

Quote:
 Originally Posted by R.D. Silverman I checked my copy of Hopcroft & Ullman's book on Automata and Languages and could find nothing. Perhaps Myhill's original paper on representations of events might help? I think it dates back to the late 50's/early 60's.
I can't immediately find the paper you refer to -- Dr. Myhill was rather prolific.

Quote:
I've played with JFLAP before. I just tried the applet version to see if it was able to help. You can convert a regular expression to a NFA, convert the NFA to a DFA, minimize the DFA, then convert the DFA to a regular expression. Unfortunately this roundtripping seems to increase rather than decrease the complexity and size...

Last fiddled with by CRGreathouse on 2009-12-09 at 19:57

 Similar Threads Thread Thread Starter Forum Replies Last Post enzocreti FactorDB 2 2018-03-01 21:51 wildrabbitt Hardware 8 2015-06-22 10:29 Raman Puzzles 21 2009-12-09 20:25 Speedbump Information & Answers 1 2009-07-25 00:51 ixfd64 Programming 2 2009-03-01 06:19

All times are UTC. The time now is 10:28.

Sat May 15 10:28:16 UTC 2021 up 37 days, 5:09, 0 users, load averages: 1.44, 1.59, 1.55