My teacher asked me to convert the regular expression $(a | b)^*$ to an NFA using Thompson's algorithm – well, I'm well aware of how this algorithm works, but since I'm not good at memorising details, I produced a slightly different NFA, and the teacher said it was wrong. Yeah, I know that it's not what the algorithm produces, but I guess it's not wrong either – what do you guys think?
This is the NFA that I produced:
Thompson's algorithm produces an empty transition from state 7 to 2 instead of that from 8 to 1. Is there anything wrong with my construction? If so, could you please show me?
N.B.: The accepting state (8) is not marked because of a difficulty with the drawing tool.
Asked By : H_DANILO
Answered By : Rick Decker
Your construction is correct, in that your FA accepts $(a\mid b)^*$. In fact, the construction is exactly the one that is used in a popular (and very good) text by Peter Linz. However, your instructor might have objected to the fact that it wasn't the one used in the Thompson paper, which of course it wasn't, as you noted. The upshot is that there are different, equivalent, ways of going from a regular expression to an NFA. As the sage said, "There are many roads to the top of the mountain, grasshopper".
(For instance, one might also propose the 1-state FA for this language, which also would be correct.)
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/42568
0 comments:
Post a Comment
Let us know your responses and feedback