0
$\begingroup$

I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$

I am wondering if I should deconstruct the RegEx as -

  1. Concatenation of $a+$, $(b|c?)$ together with $c$ OR
  2. Union of $a$ and $(b|c?)$ concatenated with $c$

In either case, I would the need the atomic NFA construction for the $c?$. I am unable to figure it out.

Please help.

$\endgroup$

1 Answer 1

0
$\begingroup$

I would assume that $+$ and $|$ do not both mean union, so the regex is actually (assuming POSIX syntax) $$a^+ (b + c + \varepsilon) c \equiv aa^\ast (b + c + \varepsilon) c.$$ You should be able to figure out the NFA if you know the Thompson construction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.