Q. If machine M is recognizing L with n states. Then M' recognizing L* construed using Thompson's Construction will have ___ states.
a) n
b) n+1
c) n+2
d) n-1
I know that we use Thompson's construction while converting from e-NFA. I thought if some RE is accepted with n states, then (RE)* should also be acceptable by n states. But my book says the answer as b) n+1 states.
I am not even getting their explaination as "We need one extra state to eliminate the e-moves" . How can this be done? Can somebody plz explain.
Thanks.