All geek questions in one place

Why can't you simplify the Kleene closure design for the NFA?

In most sources, such as http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html , suppose the Klein closure will be built with 4 nodes.

Why can't it be built with just 2, as follows?

enter image description here

+4
source share
1 answer

To get the right results when combining the two NFAs, you need to make sure that for both components:

  • There are no transitions from the final state; or

  • There are no transitions to the initial state.

Thompson's normal design provides both.

. , NFA a*b* ababab, .

+4

Source: https://habr.com/ru/post/1665460/

More articles:


All Articles