How to deal with character set in regular expression?

Question

In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit or \w to represents word character. I wonder how they are converted to DFA, since you cannot really create expand edges in alphabet(Unicode).

Take example as: x(2|\d)*y. The dfa is generated as the following graph.

Apprently 2|\d is the same as \d, the edge '2' is not necessary since it is contained in '\d'. But DFA cannot realize it.

Is there any way to reduce such kind of redundancy?

It also seems regular expression compression becomes very difficult. If we don't expand \d to 0|1|2...|9 E.g. we can hardly say is \w+ equals a*\w+b* or not.

And does those regular expression implemention (e.g. re package in python) consider the redundancy?

Answer 1

Theoretically, NFA or RegEx minimization is PSPACE-complete [1]

Practically, you can throw as many optimizing features to your online regex visualizer websites as current websites do, as long as it does not consume all your server's resources.

[1] Minimizing nfa’s and regular expressions, Gregor Gramlich,, Georg Schnitger

Answer 2

Is there any way to reduce such kind of redundancy?

You expand any special notation to their full finite sets of characters.

It also seems regular expression compression becomes very difficult. If we don't expand \d to 0|1|2...|9 E.g. we can hardly say is \w+ equals a*\w+b* or not.

Compare after expansion. Note that after expansion you can always replace groups of edges with their compressed forms after comparison/minimization again.

And does those regular expression implemention (e.g. re package in python) consider the redundancy?

This is not a computer science question. Check their source code.