1
$\begingroup$

Why this case exists in Thompson's construction algorithm? enter image description here

Isn't just a special case of:
enter image description here
where the symbol a is replaced by ϵ?

$\endgroup$
6
$\begingroup$

It's not a special case since $a$ is a symbol of the alphabet whereas $\epsilon$ is a symbol representing the empty word. However, you could lump the two cases together if you wish.

It all boils down to your recursive definition of regular expression. Most definitions will have three "axioms": $a$ for $a \in \Sigma$, $\epsilon$, and $\emptyset$. This necessitates three different base cases in the construction.

$\endgroup$
  • $\begingroup$ Does this difference have impact on implementing the algorithm? $\endgroup$ – Bite Bytes Aug 27 '17 at 13:08
  • 1
    $\begingroup$ That depends on the implementation. It really depends on how you represent (parsed) regular expressions and NFAs. Such details are off-topic here - you can figure them out on your own. $\endgroup$ – Yuval Filmus Aug 27 '17 at 13:19

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.