[Solved]: Converting Regular expression to DFA by building syntax tree

Problem Detail: 

There is a way to convert regular expression to DFA (deterministic finite automata) which is to build a syntax tree and then compute first pos, last pos, follow pos, and then use a Transition technique to build DFA for that particular regular expression. But this case only works when operators in the regular expression are only . (Dot), * (star), | (or). I just want to know if the operators in the regular expression are like ?, [], - and etc. Then can i convert regular expression to DFA just like above way?

Thanks in advance.

Asked By : user3127212

Answered By : J.-E. Pin

No, using complementation yields an exponential blow-up in the size of the DFA.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44174