Why can't the Kleene closure construction for an NFA be simplified?

Question

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?

Vitiate

Answer 1

In order to get correct results when you concatenate two NFAs, you need to ensure that for both components, either:

1. There are no transitions out of the end state; or

2. 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 accepts ababab, which is wrong.

Oxheart

This is the right answer. It's a construction practicality constraint, not a minimized form. – Faerie