Построение по НКА эквивалентного ДКА, алгоритм Томпсона — различия между версиями
(Новая страница: «{{В разработке}} == Алгоритм Томпсона ==») |
|||
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
== Алгоритм Томпсона == | == Алгоритм Томпсона == | ||
| + | Данный алгоритм используется для преобразования НКА в ДКА. | ||
| + | Для построения используются обход в ширину графа переходов. | ||
| + | Псевдокод: | ||
| + | <Цикл по всем состояниям> | ||
| + | * <Для всех переходов по одинаковым символам> | ||
| + | ** <Объединить все состояния, куда они ведут в одно> | ||
| + | ** <Если такого состояния нет в новом автомате> | ||
| + | *** <Добавить> | ||
| + | ** <Иначе> | ||
| + | *** <Направить все переходы на него> | ||
| + | |||
| + | Так же для реализации можно использовать AVL-деревья | ||
Версия 06:03, 29 сентября 2010
Эта статья находится в разработке!
Алгоритм Томпсона
Данный алгоритм используется для преобразования НКА в ДКА. Для построения используются обход в ширину графа переходов. Псевдокод: <Цикл по всем состояниям>
- <Для всех переходов по одинаковым символам>
- <Объединить все состояния, куда они ведут в одно>
- <Если такого состояния нет в новом автомате>
- <Добавить>
- <Иначе>
- <Направить все переходы на него>
Так же для реализации можно использовать AVL-деревья
