Calculate the difference and intersection of any two regexes

Though going from NFA to explicit DFA isn't always a good idea.

Btw, you might also like looking into the Brzozowski derivative https://en.wikipedia.org/wiki/Brzozowski_derivative which can be used as an alternative way to match regular expressions.

In languages with tagged union types you do this a lot! Some Haskell pseudocode for ya

    module Email (Address, fromText, toText) where -- note we do not export the constructor of Address, just the type

    data Address = Address Text

    fromString :: Text -> Maybe Address
    fromString =
        -- you'd do your validation in here and return Nothing if it's a bad address.
        -- Signal validity out of band, not in band with the data.

    toText :: Address -> Text
    toText (Address addr) = addr -- for when you need to output it somewhere

>An e-mail address could be passed into a function that requires a non-empty string as input. When the type-system knows that an e-mail string is a subclass of non-empty string, it knows that an email address is valid.

Don't use regex for email address validation

https://news.ycombinator.com/item?id=31092912

Nothing like a dive into the wondrous world of what is and isn't allowed in an email address left of the @ on a warm late-summer morning. It's one of the mysteries of the modern world. The simple heuristic that proposes that every regex trying to express "valid email address" is wrong is a sufficiently safe bet, but it ruins all the fun.

> Their value space...

wossis mean? TIA

Edit: instread of downvoting try answering. I'd like to know. TIA{2}

It always amazes me how given the appropriate field, so much math can be transformed into linear algebra. Even Möbius transformations on the complex plane w=(az+b)/(cz+d) can be turned into linear algebra.

That usually means the representation is getting close to the truth. Good interfaces have intrinsic value, which many result-focused people do not appreciate.

iirc connections with linear algebra come up in Conway's https://store.doverpublications.com/0486485838.html (which I only skimmed).

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 web page hangs on the regular expressions that produce a DFA with a lot of states. For example, these ones:

(ab+c+)+

(abc){100}

a.*quick brown fox jumps over the lazy dog

The page says it doesn't support anchors anyway.

expressions like (...){1,256} are very heavyweight and the scala JS code ends up timing out or crashing the browser.

if you replace that with (...)+ then it seems to work (at least for me). smaller expressions like (...){1,6} should be fine.

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

Wouldn't a simpler solution work here? Instead of trying to validate the filter regex, show some sample IP addresses or let the user insert a set of addresses, and then show which ones the filter matches and which ones it doesn't. Also helps address the problem of incorrect filters.

The graphics look identical to those in Hopcroft & Ullman's "Introduction to Automata Theory, Languages, and Computation" (like the convention that they use a double-circle to denote accepting states). I imagine they're GraphViz-based: it's very easy [0] to draw these in GraphViz. I don't know what Hopcroft & Ullman used though, because that one was published in 1979, and GraphViz didn't exist before 1991. Suddenly I'm curious what the state of the art for vector diagrams was in 1979...?

[0] e.g. https://graphviz.org/Gallery/directed/fsm.html

It has the look of graphviz about it, which is an excellent tool. Often helpful in debugging anything related to graphs.

https://graphviz.org/

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?

the page actually does give these. for α := [a-z]{2,4} the page gives |α| = 475228.

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.

Here's a simple Haskell program to do it:

(EDIT: this code is completely wrongheaded and does not work; it assumes that when sequencing regexes, you can take the product of their sizes to find the overall size. This is just not true. See reply, below, for an example.)

    -- https://gist.github.com/rntz/03604e36888a8c6f08bb5e8c665ba9d0

    import qualified Data.List as List

    data Regex = Class [Char]   -- character class
               | Seq [Regex]    -- sequence, ABC
               | Choice [Regex] -- choice, A|B|C
               | Star Regex     -- zero or more, A*
                 deriving (Show)

    data Size = Finite Int | Infinite deriving (Show, Eq)

    instance Num Size where
      abs = undefined; signum = undefined; negate = undefined -- unnecessary
      fromInteger = Finite . fromInteger
      Finite x + Finite y = Finite (x + y)
      _ + _ = Infinite
      Finite x * Finite y = Finite (x * y)
      x * y = if x == 0 || y == 0 then 0 else Infinite

    -- computes size & language (list of matching strings, if regex is finite)
    eval :: Regex -> (Size, [String])
    eval (Class chars) = (Finite (length cset), [[c] | c <- cset])
      where cset = List.nub chars
    eval (Seq regexes) = (product sizes, concat <$> sequence langs)
      where (sizes, langs) = unzip $ map eval regexes
    eval (Choice regexes) = (size, lang)
      where (sizes, langs) = unzip $ map eval regexes
            lang = concat langs
            size = if elem Infinite sizes then Infinite
                   -- finite, so just count 'em. inefficient but works.
                   else Finite (length (List.nub lang))
    eval (Star r) = (size, lang)
      where (rsize, rlang) = eval r
            size | rsize == 0 = 1
                 | rsize == 1 && List.nub rlang == [""] = 1
                 | otherwise = Infinite
            lang = [""] ++ ((++) <$> [x | x <- rlang, x /= ""] <*> lang)

    size :: Regex -> Size
    size = fst . eval

Another interesting question is: how many possible successful matches are there for a given input string. For example:

How many ways can (a?){m}(a*){m} match the string a{m}

i.e. input m repetitions of the letter 'a'.

https://github.com/mike-french/myrex#ambiguous-example

The answer is a dot product of two vectors sliced from Pascal's Triangle.

For m=9, there are 864,146 successful matches.

might be something like this https://jvns.ca/blog/2016/04/24/how-regular-expressions-go-f... which refs https://en.wikipedia.org/wiki/Brzozowski_derivative

https://regex-generate.github.io/regenerate/ (I'm one of the authors) enumerates all the matching (and non-matching) strings, which incidentally answers the question, but doesn't terminate in the infinite case.

I feel like it might be possible with dataflow analysis. Stepping through the regex maintaining a liveness set or something like that. Sort of like computing exemplar inputs, but with repetition as permitted exemplars. Honestly probably end up re-encoding the regex in some other format, perhaps with 'optimizations applied.'

The answer is usually an infinite number, except for very, very simple cases. Anything involving * for example means infinity is your answer.

What’s your use case?

  negation (~α): strings not matched by α
  difference (α - β): strings matched by α but not β
  intersection (α & β): strings matched by α and β
  exclusive-or (α ^ β): strings matched by α or β but not both
  inclusion (α > β): does α matches all strings β matches?
  equality (α = β): do α and β match exactly the same strings?

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 EXPSPACE complete if you allow squaring, but not if you use repetition.

IE it is expspace complete if you allow e^2, but not if you only allow ee.

The states are numbered, $\alpha_0, ..., \alpha_N$ and $\beta_0, ...$. You might be missing the font for the digits.

I wouldn't use an LLM for anything that can be done 100% precisely, like this.