Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Calculate the difference and intersection of any two regexes

phylactery.org

Post reply on HN
Print view View original

121–127 of 127 posts

Re: Calculate the difference and intersection of any two regexes

#121

Post by daveFNbuck »

ufo wrote: post #99
jepler wrote: post #96

This is neat! I was surprised then not surprised that the union & intersection REs it comes up with are not particularly concise. For example the two expressions "y.+" and ".+z" have a very simple intersection: "y.*z" (equality verified by the page, assuming I haven't typo'd anything). But the tool gives yz([^z][^z]*z|z)*|y[^z](zz*[^z]|[^z])*zz* instead. I think there are reasons it gives the answer it does, and givi…

I think one of the reasons is the ".+z" gets bigger and uglier after you convert it to a deterministic automaton.

They show the DFA for it on the site, it's 3 states. There's a starting state for the first . and then two states that transition back and forth between whether z was the last character or not.

I think what's actually happening here is that they're doing the intersection on the DFAs and then producing a regex from the resulting DFA. The construction of a regex from a DFA is where things get ugly and weird.

Re: Calculate the difference and intersection of any two regexes

#122

Post by less_less »

DannyBee wrote: post #119
DannyBee wrote: post #86

Earlier quoted context omitted.

It depends on your operators. For these, no. Equivalence of DFA or NFA is PSPACE complete by savitch's theorem, regardless of time bound. As such, most types of regex equivalence is pspace-complete. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.... Has a detailed breakdown of operators vs complexity. In particular, the paper cited in the expspace page is talking about allowing a squaring operator. It is…

Since this may be confusing at first (why does squaring buy you anything here) - the reason squaring makes it expspace complete is, basically, squaring allows you to express an exponentially large regex in less than exponential input size. This in turn means polynomial space in the size of the input is no longer enough to deal with the regex. If you only allow repetition, than an exponentially large regex requires ex…

But the site does allow squaring, and in fact also general exponentiation? Like you can write "fo{2}" to match "foo", where the {2} is squaring.

Re: Calculate the difference and intersection of any two regexes

#123

Post by telotortium »

less_less wrote: post #122
DannyBee wrote: post #119

Earlier quoted context omitted.

Since this may be confusing at first (why does squaring buy you anything here) - the reason squaring makes it expspace complete is, basically, squaring allows you to express an exponentially large regex in less than exponential input size. This in turn means polynomial space in the size of the input is no longer enough to deal with the regex. If you only allow repetition, than an exponentially large regex requires ex…

But the site does allow squaring, and in fact also general exponentiation? Like you can write "fo{2}" to match "foo", where the {2} is squaring.

I don't think that's squaring, since "o" is a literal. Squaring is more like /f../ where the first and second /./ must match equal strings. Squaring is actually supported by the Perl regex /f(.)\g1/, where /\g1/ is a backreference[1] to the first match group (here just /(.)/, but could be arbitrarily large). It's easy to see how this feature requires backtracking, and therefore how it can lead to an exponential running time.

/f(.)\g1/ is equivalent to the non-backtracking regex /f(?:\x00\x00|…|aa|bb|cc|…|\U10FFFF\U10FFFF)/ - you've already made a regex over 2 million Unicode codepoints long from an input 6 bytes long. /f(..)\g1/ would create a regex 2 billion codepoints long. If you restrict the regex to Latin-1 or another 1-byte encoding, the exponent base is smaller, but the growth is still exponential.

Supporting features like backreferences is convenient, so that's why Perl has them. You can at least use backtracking to reduce the space blowup (only need linear memory to do a DFS), but it's easy to make the regex match take exponential time with a suitable match text. That's why backtracking regexes are not safe against hostile clients unless you sandbox their time and memory usage carefully.

[1] https://perldoc.perl.org/perlretut#Backreferences

Re: Calculate the difference and intersection of any two regexes

#124

Post by less_less »

telotortium wrote: post #123
less_less wrote: post #122

Earlier quoted context omitted.

But the site does allow squaring, and in fact also general exponentiation? Like you can write "fo{2}" to match "foo", where the {2} is squaring.

I don't think that's squaring, since "o" is a literal. Squaring is more like /f../ where the first and second /./ must match equal strings. Squaring is actually supported by the Perl regex /f(.)\g1/, where /\g1/ is a backreference[1] to the first match group (here just /(.)/, but could be arbitrarily large). It's easy to see how this feature requires backtracking, and therefore how it can lead to an exponential runni…

Squaring isn't backreferences, though you can square more than a literal. An example squaring is /(foo|bar*){2}/ which is equivalent to /(foo|bar*)(foo|bar*)/, not /(foo|bar*)\g1/.

Backreferences aren't technically regular, and as you say they can take exponential time to match. But the theorem that regular expression equivalence is EXPSPACE-complete applies to real regular expressions, not just perl "regexes".

IIRC the proof is something like, given a Turing machine that runs in space S, to consider traces of the the computation, which are concatenations of S-long strings (plus a head indicator holding the machine's internal state etc). You can make a regex that matches invalid executions of the machine, which are basically of the form

/.* (foo1.{S}bar1 | foo2.{S}bar2 | ...) .*/

where foo1->bar1, foo2->bar2 etc are all the types of invalid transitions (basically, either something on the tape not next to the head changed, or the head changed in a way not indicated in the state table).

You also set rules to enforce the initial state. Then you ask whether:

/wrong initial state | invalid execution | execution that doesn't end in "accept"/

is the same regex as

/.*/

If it's the same, then there are no strings which don't match the first regex; such a string must have the right initial state, a valid execution, and end in "accept". So if the two are the same, then all valid executions end in "reject". Since you aren't constrained to allow only a single state transition rule, this actually shows NEXPSPACE hardness, but that's equal to EXPSPACE by Savitch's theorem. Anyway I could be misremembering this, it's been a while, but it doesn't require backreferences.

The squaring is required to make the {S} part without exponential blowup. Otherwise, I think the problem is only PSPACE-hard (PSPACE-complete? I don't remember).

Re: Calculate the difference and intersection of any two regexes

#125

Post by simlevesque »

pimlottc wrote: post #56
simlevesque wrote: post #7

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 ?

What’s your use case?

Calculate how long it takes to bruteforce something matching a regexp.

Re: Calculate the difference and intersection of any two regexes

#126

Post by o11c »

o11c wrote: post #39
vintermann wrote: post #4

Earlier quoted context omitted.

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?

A lack of `^` is equivalent to prepending `(.*)`, then trimming the match span to the end of that capture. And similarly for a lack of `$` (but suddenly I remember how nasty Python was before `.fullmatch` was added ...). More interesting is word boundaries: `\b` is just `\ ` though that should be bubbled up and usually only one side will actually produce a matchable regex. `A\ `.

Correction, `A\<B` is `(A&(\W|^))(\w&B)`, which matters if the A regex can match the empty string.

Re: Calculate the difference and intersection of any two regexes

#127

Post by wnoise »

skulk wrote: post #87
d66 wrote: post #51

Earlier quoted context omitted.

interesting! what would [ab]* be? for computing an ordinal number the only real difficulty is how to handle kleene star: given ord(X) how do we calculate ord(X*)? but as you probably noticed i'm a bit out of my depth when dealing with ordinals.

I would say [ab]* has order type omega. That's because the set of strings it represents is: {epsilon, ab, abab, ababab, abababab, ...} which looks a lot like omega. (epsilon = empty string) What this exercise really is is finding a canonical way to order a regular language (the set of strings a regexp matches). For example, a*b* could be {epsilon, a, aa, aaa, aaa, aaaa, ..., b, bb, bbb, bbbb, bbbbb, bbbbbb, ..., ab,…

[ab] is a character class, not a parenthesized catenation. It's (a|b), not (ab). So [ab]* is {epsilon, a, b, aa, ab, ba, bb, ...}
Post reply on HN