mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-12-09, 06:38   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

176116 Posts
Default 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.
CRGreathouse is offline   Reply With Quote
Old 2009-12-09, 11:59   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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......
R.D. Silverman is offline   Reply With Quote
Old 2009-12-09, 12:32   #3
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

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
Raman is offline   Reply With Quote
Old 2009-12-09, 19:56   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

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 View Post
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:
Originally Posted by Raman View Post
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.
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
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to concatenate values of expressions enzocreti FactorDB 2 2018-03-01 21:51
meaning of regular flashes of hot lead wildrabbitt Hardware 8 2015-06-22 10:29
Regular polygon: ruler & compass possible only if Raman Puzzles 21 2009-12-09 20:25
Using regular Prime 95 on 64 bit windows? Speedbump Information & Answers 1 2009-07-25 00:51
regular expression help 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.