Does exist an algorithm to find all equivalence classes of given regular expression without kleene star?
If yes then what is it?
Note that alphabet of the given regular expression is binary, i.e. it contains only 2 symbols exactly.
This is important, because I can easily construct NFA from the given regular expression and then construct the DFA from that NFA, but the result DFA is not minimal and the result DFA's number of states is exponential.
Of course I can run Hopcroft's algorithm to minimize the DFA, but if DFA's number of states is Θ(2n) then Hopcroft's algorithm runs in Θ(2nlog(2n)) = Θ(2nn) = Θ(n2n) and this might take too much time to get the minimal DFA for the given regular expression.
Also my computer has only 4GB of RAM.
If the given regular expression is long and the result NFA is big, then in the middle time conversion from NFA to DFA, there might be out of memory exception thrown and my application won't make it to call Hopcroft's algorithm at all.
For the given regular expression, running the algorithm to find all it's equivalence classes is considered to be much better than constructing NFA from the regular expression, constructing DFA from the NFA and run Hopcroft's algorithm to minimize it, but if and only if the algorithm to find all the equivalence classes won't use too much resources and won't take too much time to finish, then I can use the equivalence classes to efficiently construct the minimal DFA quickly for the given regular expression.
I tried to google the answer for this question, but I didn't find it yet.
Thinking about this algorithm myself is very difficult and hard.
I am very curious to find out what is this algorithm already.
