Algorithm for converting a finite state machine into a regular expression

http://qntm.org/algo

by pavel_lishin • 16 years ago

67 22 16 years ago

qntm.org

Kafka• 16 years ago

Any mirror?

Groxx• 16 years ago

Try googling for:

  cache: url you want cached

(I only found this trick out a couple days ago)

profquail2• 16 years ago

The site wasn't loading for me, but it did load (albeit slowly) from a Coral Cache link:

http://qntm.org.nyud.net:8080/algo

seancron2• 16 years ago

It loads for me, it just loads slowly.

Cached version: http://cache.historious.net/cached/569458/

Edit: P.S. If you used the cached version, can you let me know how it worked for you? I stumbled across historious and I'm testing to see how well it works.

profquail2• 16 years ago

The Historious cache link works just fine for me too.

StavrosK2• 16 years ago

Heh, I went to historify that site and post the cache to help out, but wasn't sure if it would be seen as shameless promotion. I'm proud this feature sees usage, and glad you like it!

EDIT: I'm glad to report that server load is at 0.01 right now, so hammer away, Varnish is pretty much indestructible.

qntm3• 16 years ago

I apologise for the site loading slowly, my entirely unrelated page http://qntm.org/uk "The Great British Venn Diagram" is currently being hammered by Redditors.

bhiggins• 16 years ago

If you find this interesting, you may be interested in this as well: http://en.wikipedia.org/wiki/Star_height_problem

Darmani2• 16 years ago

There are several completely different algorithms for converting DFAs into regular expressions. See http://www.cs.cmu.edu/~cdm/pdf/KleeneAlg.pdf for three. One of my favorites involves eliminating states by replacing all pairs of transitions through them with regexes -- it winds up looking almost exactly like the Floyd-Warshall algorithm.

nopassrecover• 16 years ago

Hmm my relevant theory is a little sketchy, but there are FSMs that aren't modellable by regex right? (e.g. Nested tags).

batterseapower• 16 years ago

Actually they are exactly equivalent.

See for example http://en.wikipedia.org/wiki/Regular_expression ("Regular expressions in this sense can express the regular languages, exactly the class of languages accepted by deterministic finite automata.")

xtacy• 16 years ago

Most of the regex engines in languages (like Perl) allow keeping track of state by using back references. If you're talking about this, then theoretically, they aren't "finite state" machines.

jemfinch• 16 years ago

Nested tags can't be matched by fsms.

andrewf• 16 years ago

FSMs can't handle nested tags. Pushdown Automata can.

qntm3• 16 years ago

Most "regular" expression engines in modern programming languages can handle back-references (e.g. "(.)\1"), which are actually so complex that you need a full-blown Turing machine to handle them.

Darmani2• 16 years ago

Just had a second look at your algorithm.

You're essentially running a well-known DFA-minimization algorithm (see http://en.wikipedia.org/wiki/DFA_minimization or http://www.cs.cmu.edu/~cdm/pdf/minimization.pdf ), and then running Brzozowski. This isn't new at all, though I'm pretty impressed you reinvented the minimization algorithm.

qntm3• 16 years ago

Well, there you go then. I did make an effort to find what I'd done online, but since there is no explicit "minimization" step in the way I've phrased my algorithm I probably didn't stand a chance. Apparently that DFA minimization thing is on any Computer Science degree course, which of course I've never taken (I only discovered state machines as a concept about six months ago).

Thanks for reading, everybody.

Twisol• 16 years ago

At least you know for sure that what you came up with was worth coming up with. ;) I do that all the time, and it's a mixed bag of pride and annoyance.

jacquesm• 16 years ago

At this rate you'll be coming up with original stuff before long. 6 months from discovering state machines to here is pretty impressive. Definitely don't let it stop you that this was already done before, keep at it!

alttab• 16 years ago

This is basically a course study in formal languages. What is more fascinating is that you arrived at the same abstraction independently.

Algorithm for converting a finite state machine into a regular expression

Related Stories