Most sources, such as http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html, suggest that the Kleene closure be constructed with 4 nodes.
Why can't it be constructed with just 2, as follows?
Most sources, such as http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html, suggest that the Kleene closure be constructed with 4 nodes.
Why can't it be constructed with just 2, as follows?
In order to get correct results when you concatenate two NFAs, you need to ensure that for both components, either:
There are no transitions out of the end state; or
There are no transitions into the start state.
The normal Thompson's construction ensures both.
Without such restrictions, composition doesn't work. With your construction, for example, the NFA for
a*b*
also acceptsababab
, which is wrong.