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

1.1k views Asked by At

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?

enter image description here

1

There are 1 answers

1
Matt Timmermans On

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.