Почему нельзя создать конструкцию замыкания Клини для NFA?

Question

Большинство источников, таких как http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html, предполагают, что замыкание Клини должно быть построено с 4 узлами.

Почему это не может быть построено только с 2, как показано ниже?

Answer 1

Чтобы получить правильные результаты при объединении двух NFA, необходимо убедиться, что для обоих компонентов:

1. Нет переходов из конечного состояния; или же

2. Нет переходов в начальное состояние.

Нормальная конструкция Томпсона обеспечивает оба.

Без таких ограничений композиция не работает. С вашей конструкцией, например, NFA для a*b* также принимает ababab, что не так.