StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Yes, it turns out this does exist; what is required is what is known academically as a <strong>DFA Learning algorithm</strong>, examples of which include:</p> <ul> <li>Angluin's L*</li> <li>L* (adding counter-examples to columns)</li> <li>Kearns / Vazirani</li> <li>Rivest / Schapire</li> <li>NL*</li> <li>Regular positive negative inference (RPNI)</li> <li>DeLeTe2</li> <li>Biermann & Feldman's algorithm</li> <li>Biermann & Feldman's algorithm (using SAT-solving)</li> </ul> <p>Source for the above is <a href="http://libalf.informatik.rwth-aachen.de/" rel="nofollow noreferrer">libalf</a>, an open-source automata learning algorithm framework in C++; descriptions of at least some of these algorithms can be found in <a href="http://rads.stackoverflow.com/amzn/click/0521763169" rel="nofollow noreferrer">this textbook</a>, among others. There are also implementations of grammatical inference algorithms (including DFA learning) in <a href="https://code.google.com/p/gitoolbox/" rel="nofollow noreferrer">gitoolbox</a> for MATLAB.</p> <p>Since <a href="https://stackoverflow.com/questions/5958483/grammar-inference-library">this question has come up before</a> and has not been satisfactorily answered in the past, I am in the process of evaluating these algorithms and will update will more information about how useful they are, unless someone with more expertise in the area does first (which is preferable). </p> <p><sub><strong>NOTE:</strong> I am accepting my own answer for now but will gladly accept a better one if someone can provide one.</sub></p> <p><sub><strong>FURTHER NOTE:</strong> I've decided to go with the route of using custom code, since using a generic algorithm turns out to be a bit overkill for the data I'm working with. I'm leaving this answer here in case someone else needs it, and will update if I ever do evaluate these.</sub></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload