To address the zeroth point, if it were possible to have such a machine then optimal would be fastest. The idea is that I can write an easy to understand regex that isn't fast, and likewise I can write a short regex that isn't fast, but I want a regex that is fast whether or not it sacrifices length or understandability.

For the first comment, I can see both sides equally. If the two suboptimal regexes are equivalent, then it should find two optimal regexes for each, since I figure this is a machine where I put one input in and get one output out. But if these two inputs are equivalent, then there should be a single "most optimal" regex and if there is a difference in the results from putting r1 and r2, then either one isn't fully optimized since there is a single "most optimal", or my argument has a flaw since I assume that there exists a "most optimal" state.

Admittedly, some time has passed since I was knee deep in language theory, so I may have missed some very critical points that cause a regex optimizer to fail. So, here's a question: If heuristics are employed in the development of this machine (and mind you at this point, the REO is going to remain purely theoretical), does it doom the optimization from the point at which a heuristic is employed? Does this machine require that it can only operate on the input regex with algorithmic manipulations?

And finally, for the second point, that just rules out the ability to do the problem within a certain context. ALL HAIL BRAK!!!

In reply to RE: RE: Regular Expression Optimizer by PsychoSpunk
in thread Regular Expression Optimizer by PsychoSpunk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.