9 ms·
Every Finite Automaton Has a Corresponding Regular Expression
- ridiculous_fish 7y agoI worked on a tool that infers a regex from sample strings, by building and then reducing an NDFA. The NDFA->regex construction worked by "collapsing" a node in the NDFA. Choose a victim node. Construct a Kleene star for all "self loops." Lastly, form all triples of (incoming, self-loop, outgoing) edges; these become the labels of new edges. Now you can discard the victim node. Repeat until you're down to a single start -> goal node, and you're done (the edges just become alternations). Surprisingly the length of a regex would vary dramatically by the choice of nodes to collapse. Finding the minimum regex was an unexpected challenge. Has anyone explored regexp minimization? Incidentally it's not the case that Thompson and subset construction "are the basis of every lexer and regexp engine there is." It's not even true of the regexp engine inside the browser you're using now!
- captn3m0 7y agoIf someone is looking, https://github.com/noprompt/frak https://github.com/noprompt/frak does the same.. >frak transforms collections of strings into regular expressions for matching those strings. The primary goal of this library is to generate regular expressions from a known set of inputs which avoid backtracking as much as possible. It is available as a command line utility and for the browser as a JavaScript library.
- deleted 7y ago[deleted]
- bane 7y agoVery cool, do you know of any tool that does something similar (provide examples, get regex)?
- pottertheotter 7y agoMicrosoft PROSE kind of does. I haven't looked at it for a while so can't quite remember, but might be of interest to you.
- jraph 7y agoI am not sure this is what you are looking for, but I have been working on Aude (AUtomata DEmystifier), an open source pedagogical application targeted at CS teachers and students that works in browsers without installation (but one can download and run it offline too). The aim is to visualise and manipulate automata, including conversions between them and regular expressions. Happy to take feedback! https://aude.imag.fr https://aude.imag.fr
- AlchemistCamp 7y agoThat's a neat project! What inspired you to start it?
- jraph 7y agoThanks for the kind words. Well, I was a student and needed to practice the related lesson, "Languages and Automata", before the final exam. So I implemented the algorithms of the lesson and used Graphviz to render the result. The thing worked in a browser but ran on the server (using D!). I figured my fellow students or the teacher may find it useful, so I sent the link to the teacher (in a post-scriptum of a very long mail in which I was asking for help, ah ah). "Your tool seems really interesting, what about you continue developing this during an internship this summer?" Hell, yes. And Aude started. Since then, I was lucky to mentor several interns to work on Aude with this teacher.
- AlchemistCamp 7y agoThat is very cool and I'll bet having a steady flow of later cohorts of students helped a ton!
- jraph 7y agoI would not say a steady flow, there were two to three students two months per summer these last three years, but they helped a lot anyway indeed :-) And it was fun to work with them. The first "cohort" of three students called themselves the Aude Team and they put that in their internship report.
- Gys 7y agoMaybe this: http://regex.inginf.units.it/ http://regex.inginf.units.it/
- blitmap 7y agoThis sounds exactly like what I was hoping to learn more about. I wanted to create an IRC client where I would add/remove modules at runtime. These modules might respond to things said in-chat. As an example, you might have a greeter module that responds to common things like "hi" and "hello". The module would register expressions for things it triggers on. In parallel, all these modules would have registered expressions. Instead of testing all these expressions in series, I wanted to feed these to some code that would decompose and reduce them into a simplified expression. It'd be like if you arranged the regexps in a nested series of if-conditions. Finding an appropriate middle ground for testing expensive regular expressions was the objective of all that, but I didn't get very far as I lost myself in Lua's LPeg project. What a beautiful goddamn project. So unique and amazing.
- jbapple 7y ago> Has anyone explored regexp minimization? There has been significant work on https://en.wikipedia.org/wiki/DFA_minimization https://en.wikipedia.org/wiki/DFA_minimization
- Syzygies 7y agoThe first chapter of Berstel and Reutenauer's "Noncommutative Rational Series with Applications" presents Schützenberger's theorem that every noncommuting rational power series is representable, and conversely. The idea is NOT painfully abstract, but makes twenty minutes work of a semester of undergraduate automata theory (an assertion I've tested multiple times in my math office hours). They work with coefficients in an arbitrary semiring, which can be like watching paint dry. However, boolean true/false, and probabilities, make two great examples. The idea that hidden Markov chains is exactly the same theory as CS automata theory is mind-blowing. Once one absorbs this, there's an interesting wrinkle worked out in the 1960's that is still poorly understood. If the outputs are probabilities, do the internal coefficients of the matrices need to be probabilities? Why yes, if we are so enamored with fulfilling our expectations that we can simply draw graphs and label them in understandable ways for people who aren't willing to work very hard or defy expectations. Why no, if one chases the actual math. There are examples that can require arbitrarily many matrix dimensions to model using probabilities, that can be modeled in few dimensions using real numbers outside the [0,1] range. This has a simple explanation. There's a pattern one sees twice, a linear combination with coefficients in [0,1] that sum to one: A probability distribution, and barycentric coordinates. One can have a point cloud of small dimension, whose convex hull requires arbitrarily many vertices. Restricting the coefficients to the [0,1] range means working with these vertices as separate matrix dimensions. Leaving the coefficients unrestricted means working with the raw dimension.
- Donald 7y agoThis perspective is excellent. Besides the book reference, any papers in this area that are relevant?
- minipci1321 7y agoNot direct answer to your question, but Berstel's publications: http://www-igm.univ-mlv.fr/~berstel/PubsJeanBerstel.html http://www-igm.univ-mlv.fr/~berstel/PubsJeanBerstel.html You can try to contact him, he might be able to help you.
- joppy 7y agoThat’s a very cool construction of regular expressions, just using matrices and semirings. I loved the explanation of why F and G were as they were as well. I had two comments: > Assume we have a regular language (R, 1, ., 0, +, * ) Shouldn’t this data (a semiring with * -operation or “closure”) not be one regular language, but _all_ regular languages? A single regular language should be an element of R. I also think that the power series A* = 1 + A + A^2 + ... looks more like 1/(1-A) rather than e^A, which makes sense given the defining equation A* = 1 + A(A*), but that’s not much of an issue since neither of these properly make sense in this semiring.
- 2sk21 7y agoThis is an example of an important piece of knowledge that typically only programmers with a formal education in computer science are taught. This theorem is taught in all formal language courses.
- saagarjha 7y agoI had friends who came into college already knowing this, so this isn't a given.
- coreyp_1 7y agoYou may know of a few individuals who already knew this, but that doesn't discount the gp's word "typically". Most people don't know about it, period. For those who do know about it, unless they have taken an Automata or Theory of Computing course, then they have probably still missed the point of this factoid, which is actually the main reason that this theorem is important. A Finite State Machine is capable of performing many computations, but is limited in processing capability in that it has no memory. A Regular Expression is capable of expressing the exact same computations as the FSM, and is subject to the same constraint as the FSM and therefore the same limitations. (Of course, it is also important to know that the RegEx that is talked about in an Automata class is different from the RegEx that most programmers and SysOps deal with in practice). The underlying (important) concept is that the process of validating the pattern of characters in any string is simply a proxy for understanding a computational problem. In fact, all computational problems can be represented in this paradigm (the validation of a string of input). Whether or not the machine in question can perform that validation is the purpose of the Automata or Theory of Computing class. It's not sufficient to say "I know a fact." And simply knowing the fact isn't the point of the class. The reason for the class is to understand why the fact is important to know.
- saagarjha 7y agoI am specifically asserting that there were people in my college freshman class who had a handle on what the statement meant, its implications, and a whole lot more on formal automata than you've talked about here. Mostly because they had an interest in it before arriving and were exposed to it in some way beforehand, be it through an actual textbook or practical experience. What I'm trying to say is that there is nothing that can only be learned in a class; it just often provides a decent framework for getting a well-rounded exposition to a topic.
- NHQ 7y agoWhat is the regex for a given state of Game of Life?