11–20 of 127 posts
Kinda related but I'm looking for something that could give me the number of possible matching strings for a simple regex. Does such a tool exist ?
I feel like it shouldn't be too hard to calculate from the finite automaton that encodes the regular expression, but surely in most cases it will simply be infinite?
Kinda related but I'm looking for something that could give me the number of possible matching strings for a simple regex. Does such a tool exist ?
The answer is usually an infinite number, except for very, very simple cases. Anything involving * for example means infinity is your answer.
Earlier quoted context omitted.
I feel like it shouldn't be too hard to calculate from the finite automaton that encodes the regular expression, but surely in most cases it will simply be infinite?
Maybe the number of possible matchings for a given length (or range of lengths) might be interesting?
Automata are really a lost art in modern natural language processing. We used to do things like store a large vocabulary in an deterministic acyclic minimized automaton (nice and compact, so-called dictionary automaton). And then to find, say all words within Levenshtein distance 2 of hacker, create a Levenshtein automaton for hacker and then compute (on the fly) the intersection between the Levenshtein automaton and the dictionary automaton. The language of the automaton is then all words within the intersection automaton.
I wrote a Java package a decade ago that implements some of this stuff:
Regular expressions are a great example of bundling up some really neat and complex mathematical theory into a valuable interface. Linear algebra feels similar to me.
Earlier quoted context omitted.
The answer is usually an infinite number, except for very, very simple cases. Anything involving * for example means infinity is your answer.
I wonder if it makes sense to compute an "order type" for a regexp. For example, a* is omega, a*b* is 2 omega. https://en.m.wikipedia.org/wiki/Order_type https://en.wikipedia.org/wiki/Ordinal_number
Earlier quoted context omitted.
I feel like it shouldn't be too hard to calculate from the finite automaton that encodes the regular expression, but surely in most cases it will simply be infinite?
Maybe the number of possible matchings for a given length (or range of lengths) might be interesting?
Earlier quoted context omitted.
Maybe the number of possible matchings for a given length (or range of lengths) might be interesting?
Say you want to compute all strings of length 5 that the automaton can generate. Conceptually the nicest way is to create an automaton that matches any five characters and then compute the intersection between that automaton and the regex automaton. Then you can generate all the strings in the intersection automaton. Of course, IRL, you wouldn't actually generate the intersection automaton (you can easily do this on…
That's basically a Trie right? To be fair I have only heard of them and know they can be used to do neat tricks, I've rarely used one myself.
Regular expressions are a great example of bundling up some really neat and complex mathematical theory into a valuable interface. Linear algebra feels similar to me.
iirc connections with linear algebra come up in Conway's https://store.doverpublications.com/0486485838.html (which I only skimmed).
Regular expressions are a great example of bundling up some really neat and complex mathematical theory into a valuable interface. Linear algebra feels similar to me.
iirc connections with linear algebra come up in Conway's https://store.doverpublications.com/0486485838.html (which I only skimmed).