Изменения
→Описание
Алгоритм Томпсона строит по [[Недетерминированные конечные автоматы|НКА]] эквивалентный [[Детерминированные конечные автоматы|ДКА]] следующим образом:
* Начало.
* '''Шаг 1.''' Помещаем в очередь <tex>Q</tex> множество, состоящее только из стартовой вершины.* '''Шаг 2.''' Затем, пока очередь не пуста выполняем следующие действия:
** Достаем из очереди множество, назовем его <tex>q</tex>
** Для каждого <tex>c \in \Sigma</tex> построим множество, содержащее состояния, в которые ведет символ <tex>c</tex> из каждого состояния из <tex>q</tex>. Затем положим построенное множество в очередь <tex>Q</tex> только если оно не лежало там раньше. Каждое такое множество в итоговом ДКА будет отдельной вершиной, в которую будут вести переходы по соответствующим символам.
** Если в множестве <tex>q</tex> хотя бы одна из вершин была терминальной в НКА, то соответствующая данному множеству вершина в ДКА также будет терминальной.
* Конец.
== Построение эквивалентного ДКА по НКА ==
