0
$\begingroup$

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.

enter image description here

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.