2
$\begingroup$

In what circumstances should we prefer Glushkov's algorithm or Thompson's construction for the building of regular expression NFAs?

I understand the difference between them, and can follow the argument for each approach.

I understand that the result is an NFA in each case, but with a lack of $\epsilon$-transitions in Glushkov's approach, and that this presumably results in a minor[?] match-time implementation-complexity benefit and a reduction in the total number of states for a given expression?

Are these the primary criteria to recommend Glushkov?

It appears that the Glushkov construction process may be more complex than Thompson. Is this the case? Does this argue for Thompson for projects where that is a factor?

Are there other important factors affecting the implementation choice which I am unaware of?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.