Изменения
Нет описания правки
[[Категория: Теория формальных языков]]
== Алгоритм систем подмножеств ==
Смысл алгоритма состоит в замене множества из <tex>n</tex> состояний НКА, множеством из <tex>2^n</tex> подмножеств его состояний.
=== Алгоритм ===
Генерируем все подмножества множества состояний НКА {{---}} это состояния ДКА.
Далее для всевозможных <tex>(q_1, q_2)</tex> {{---}} пар состояний ДКА и символов <tex>c</tex>, добавляем переход из <tex>q_1</tex> в <tex>q_2</tex> по <tex>c</tex>, если для каждого состояния НКА из <tex>q_1</tex> есть переход по <tex>c</tex> в состояние из <tex>q_2</tex> и, наоборот, в каждое состояние НКА из <tex>q_2</tex> есть переход из состояния из <tex>q_1</tex> по <tex>c</tex>
== Алгоритм Томпсона ==
Данный алгоритм используется для преобразования НКА в ДКА.
Смысл этого алгоритма , как и предыдущего, состоит в замене множества из <tex>n</tex> состояний НКА, множеством из <tex>2^n</tex> подмножеств его состояний. Но не все из <tex>2^n</tex> состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширину.
===Алгоритм===
Вначале в очередь помещается множество состоящее только из стартового состояния НКА <tex>{q_0}</tex>.
