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?