21–30 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 ?
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.
I love how it looks like a CS textbook.
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 ?
however, as others have pointed out any non-trivial use of the kleene star means the result will be ∞. in this case the page will list numbers that roughly correspond to "number of strings with N applications of kleene star" in addition to infinity.
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 ?
On mobile: are the rectangle glyphs as suffixes on the states on purpose or am I missing a font?
The amazing page computes binary relations between pairs of regular expressions and shows a graphical representation of the DFA. It’s a really incredible demonstration of some highly non-trivial operations on regular expressions.
It's very cool, but also no wonder that it doesn't support all those features of regexes which technically make them not regular expressions anymore. Though, I would have thought ^ and $ anchors shouldn't be a problem?
The standard theory of regular expressions focuses entirely on regex matching, rather than searching. For matching, ^ and $ don't really mean anything. In particular, regexp theory is defined in terms of the "language of" a regexp: the set of strings which match it. What's the set of strings that "^" matches? Well, it's the empty string, but only if it comes at the beginning of a line (or sometimes the beginning of the document). This beginning-of-line constraint doesn't fit nicely into the "a regexp is defined by its language/set of strings" theory, much the same way lookahead/lookbehind assertions don't quite fit the theory of regular expressions.
The standard workaround is to augment your alphabet with special beginning/end-of-line characters (or beginning/end-of-document), and say that "^" matches the beginning-of-line character.
Earlier quoted context omitted.
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
I think that's just the ordinal corresponding to lexicographic order on the words in the language, so yeah that should work. I wonder how easy it is to calculate...
i believe the cardinality of a set of words from a finite alphabet (with more than one member) is equivalent to the cardinality of the real numbers. this means that the cardinality of .* is c.
unfortunately, i don't think that cardinality gets us very far when trying to differentiate the "complexity" of expressions like [ab]* from ([ab]*c[de]*)*[x-z]*. probably some other metric should be used (maybe something like kolmogorov complexity).