Изменения
Нет описания правки
== Описание ==
Алгоритм Томпсона строит по [[Недетерминированные конечные автоматы|НКА]] эквивалентный [[Детерминированные конечные автоматы|ДКА]] следующим образом:
* Помещаем в очередь <tex>Q</tex> множество, состоящее только из стартовой вершины.
* Затем, пока очередь не пуста выполняем следующие действия:
** Достаем из очереди множество, назовем его <tex>q</tex>
** Для каждого <tex>c \in \Sigma</tex> построим множество, содержащее состояния, в которые ведет <tex>c</tex> по каждому состоянию из <tex>q</tex>. Затем положим построенное множество в очередь <tex>Q</tex> только если оно не лежало там раньше. Каждое такое множество в итоговом ДКА будет отдельной вершиной, в которую будут вести переходы по соответствующим символам.
* Если в множестве <tex>q</tex> хотя бы одна из вершин была терминальной в НКА, то соответствующая данному множеству вершина в ДКА также будет терминальной.
== Построение эквивалентного ДКА по НКА ==
Пусть нам дан произвольный [[Недетерминированные конечные автоматы|НКА]]: <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to 2^Q \rangle</tex>.
Построим по нему следующий [[Детерминированные конечные автоматы|ДКА]]: <tex>\langle \Sigma , Q_d, s_d \in Q_d, T_d \subset Q_d, \delta_d : Q_d \times \Sigma \to Q_d \rangle</tex>, где:
# <tex>Q_d = \{q_d \mid q_d \subset 2^Q \}</tex>,
# <tex>s_d = \{s\}</tex>,
