1,680 views
0 votes
0 votes
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.

Please log in or register to answer this question.

Related questions