Построение по НКА эквивалентного ДКА, алгоритм Томпсона

Алгоритм Томпсона

Данный алгоритм используется для преобразования НКА в ДКА. Для построения используются обход в ширину графа переходов. Псевдокод: <Цикл по всем состояниям>

• <Для всех переходов по одинаковым символам>
  • <Объединить все состояния, куда они ведут в одно>
  • <Если такого состояния нет в новом автомате>
    • <Добавить>
  • <Иначе>
    • <Направить все переходы на него>

Так же для реализации можно использовать AVL-деревья