6

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

ackerleytng
  • 416
  • 6
  • 17

1 Answers1

6

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.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
  • 1
    This is the right answer. It's a construction practicality constraint, not a minimized form. –  Jan 19 '19 at 03:44