20091209, 06:38  #1 
Aug 2006
1761_{16} 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 notentirelyunrelated note: Suppose I had a MyhillNerode 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. 
20091209, 11:59  #2  
Nov 2003
7460_{10} Posts 
Quote:
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...... 

20091209, 19:56  #4  
Aug 2006
3^{2}×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:
Quote:
Last fiddled with by CRGreathouse on 20091209 at 19:57 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
How to concatenate values of expressions  enzocreti  FactorDB  2  20180301 21:51 
meaning of regular flashes of hot lead  wildrabbitt  Hardware  8  20150622 10:29 
Regular polygon: ruler & compass possible only if  Raman  Puzzles  21  20091209 20:25 
Using regular Prime 95 on 64 bit windows?  Speedbump  Information & Answers  1  20090725 00:51 
regular expression help  ixfd64  Programming  2  20090301 06:19 