Спасибо за лекцию, пересмотрел 15 раз :) Алгоритмом Томпсона обычно называется алгоритм построения эпсилон-НКА по регулярному выражению (en.wikipedia.org/wiki/Thompson's_construction). Собственно, он и используется в док-ве теоремы Клини. Впрочем, судя по статье Томпсона 1968 года, складывается ощущение, что он эту конструкцию не представлял таким красивым образом, и это уже Хопкрофт и Ульман докрутили в своей книге 1979 (рекомендую всем первое издание!). В свою очередь алгоритм построения ДКА по НКА называется просто "конструкция подмножеств Рабина-Скотта" (en.wikipedia.org/wiki/Powerset_construction). По-моему, в их статье 1959 года не прослеживается "ленивая" версия этого алгоритма. Так что вероятно, что именно ленивый алгоритм предложил кто-то другой, это затерялось во времени, и теперь подход называется просто "powerset construction".
Добрый день, у меня один вопрос: почему в функции Accept для НКА мы в конце для получения результата итерируемся по всему массиву состояний, а не проверяем лишь те состояния, которые являются терминальными?
