1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\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.