Aha! This python library does the job: https://qntm.org/greenery
from greenery.lego import parse print(parse("abc...") & parse("...def")) abcdef print(parse("\d{4}-\d{2}-\d{2}") & parse("19.*")) 19\d\d-\d\d-\d\d print(parse("\W*") & parse("[a-g0-8$%\^]+") & parse("[^d]{2,8}")) [$%\^]{2,8} print(parse("[bc]*[ab]*") & parse("[ab]*[bc]*")) ([ab]*a|[bc]*c)?b* print(parse("a*") & parse("b*")) # returns empty string, the one string they both match
print(parse("a") & parse("b")) # returns empty character class []
As Victor pointed out, it can be very expensive to compute the intersection. I learned it's because at one point you're converting an NFA to a DFA, which can be exponentially large. On Thu, Nov 30, 2017 at 1:42 PM, Cris Moore <moore@santafe.edu> wrote:
Not too hard, since the intersection of two regular languages means the set of strings accepted by two finite-state automata, and this pair can be simulated by a single larger finite-state automaton. However, the number of states of this automaton is the product of the number of states the two automata have.
- Cris
On Nov 30, 2017, at 1:32 PM, Mike Stay <metaweta@gmail.com> wrote:
Given two regular expressions, how hard is it to tell whether they unify, i.e. whether the intersection of the languages they denote is empty?
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com