Изменения

== Описание ==Алгоритм Томпсона строит по [[Недетерминированные конечные автоматы|НКА]] эквивалентный [[Категория: Теория формальных языковДетерминированные конечные автоматы|ДКА]]следующим образом:== Алгоритм систем подмножеств ==* Начало.Смысл алгоритма состоит * '''Шаг 1.''' Помещаем в замене множества из очередь <tex>nQ</tex> состояний НКАмножество, множеством состоящее только из <tex>2^n</tex> подмножеств его состоянийстартовой вершины.=== Алгоритм ===Генерируем все подмножества множества состояний НКА {{---}} это состояния ДКА* '''Шаг 2.''' Затем, пока очередь не пуста выполняем следующие действия:Далее для всевозможных ** Достаем из очереди множество, назовем его <tex>(q_1, q_2)q</tex> {{---}} пар состояний ДКА и символов ** Для всех <tex>c\in \Sigma</tex>, добавляем посмотрим в какое состояние ведет переход из <tex>q_1</tex> в <tex>q_2</tex> по символу <tex>c</tex>, если для из каждого состояния НКА из в <tex>q_1q</tex> есть переход по . Полученное множество состояний положим в очередь <tex>cQ</tex> только если оно не лежало там раньше. Каждое такое множество в состояние из <tex>q_2</tex> и, наоборотитоговом ДКА будет отдельной вершиной, в каждое состояние НКА из <tex>q_2</tex> есть переход из состояния из <tex>q_1</tex> которую будут вести переходы по <tex>c</tex>== Алгоритм Томпсона ==Данный алгоритм используется для преобразования НКА в ДКАсоответствующим символам.Смысл этого алгоритма, как и предыдущего, состоит ** Если в замене множества из множестве <tex>nq</tex> состояний хотя бы одна из вершин была терминальной в НКА, множеством из <tex>2^n</tex> подмножеств его состояний. Но не все из <tex>2^n</tex> состояний будут присутствовать то соответствующая данному множеству вершина в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширинутакже будет терминальной.* Конец.  ===Алгоритм=Построение эквивалентного ДКА по НКА ==Вначале в очередь помещается множество, состоящее только из стартового состояния Пусть нам дан произвольный НКА : <tex>{q_0}\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to 2^Q \rangle</tex>.Затем из очереди изымается очередное множество <tex>P</tex> {{---}} новое состояние Построим по нему следующий ДКА. Если в <tex>P</tex> есть допускающие состояния, то оно допускающее. Функция перехода строится по следующему правилу: <tex>\delta_D(Plangle \Sigma , Q_d, c) = \bigcup_{q_i s_d \in P}Q_d, T_d \delta_N(q_isubset Q_d, c)\delta_d : Q_d \times \Sigma \to Q_d \rangle</tex>.<br>, где:В результате # <tex>Q_d = \{q_d \mid q_d \delta_D(P, c)</tex> задаст новое состояние <tex>subset 2^Q\}</tex> автомата. Если ,# <tex>Qs_d = \{s\}</tex> еще нет в ДКА, тогда мы помещаем <tex>Q</tex> в очередь.Так как # <tex>|Q_N|T_d = \{q \in Q_d \mid \exists p \in T : p \in q\}</tex> - конечна, а # <tex>|Q_D| \le 2^{|Q_N|}</tex>delta_d(q, то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма c) = \bigcup_{{---a \in q}} в худшем случае это <tex>O\delta(2^na, c)</tex>.

===КорректностьДоказательство эквивалентности==={{УтверждениеТеорема

Построенный автомат принимает тот же языкДКА эквивалентен данному НКА.

Применим индукцию по длине слова #Докажем, что любое слово, которое принимает НКА, будет принято построенным ДКА. Заметим, что <tex>\omegaforall q \in q_d, \forall c \in \Sigma, \forall p \in \delta(q, c): p \in \delta_d(q_d, c)</tex>.* Рассмотрим слово <tex>|w=w_1 \omega|=1dots w_m</tex>, которое принимает автомат НКА: По построению стартовое состояние <tex>\langle s, w_1w_2 \dots w_m \rangle \vdash \langle u_1, w_2 \dots w_m \rangle \vdash^* \langle u_m, \varepsilon \rangle, u_m \in T</tex>. Проверим, что построенный ДКА будет тоже принимает это слово. Заметим, что <tex>s \in s_d</tex>, а, значит, исходя из нашего наблюдения, мы получаем, что <tex>u_1 \in {su_d}_1</tex>, где <tex>{u_d}_1 = \delta_d(s, w_1)</tex> . Далее, несложно заметить, что <tex>\forall i \leqslant m : u_i \in {u_d}_i</tex>, где <tex>\langle s_d, w_1w_2 \dots w_m \rangle \vdash \langle {---u_d}_1, w_2 \dots w_m \rangle \vdash^* \langle {u_d} стартовое состояние НКА_i, причем допускать они могут только одновременноw_{i + 1} \dots w_m\rangle</tex>.* Пусть для Таким образом, <tex>|u_m \omega|=nin {u_d}_m</tex> - это верно, докажема из определения терминальных состояний в построенном ДКА мы получаем, что верно и для <tex>|{u_d}_m \omega|=n+1in T_d</tex>, то есть наш ДКА тоже принимает cлово <tex>w</tex>: .Пусть #Докажем, что любое слово, которое принимает построенный ДКА, принимает и НКА на шаге n мог находиться в состояниях . Сначала сделаем наблюдение, что если <tex>q_d=\{q_1...q_kq\}</tex>, тогда ДКА, и мы из него достигли по построениюстроке <tex>S</tex> какого-то состояния <tex>p_d</tex>, находится то <tex>\forall p \in p_d</tex> существует путь из <tex>q</tex> в <tex>p</tex> в состоянии НКА по строке <tex>Q={q_1...q_k}S</tex>. После перехода по Рассмотрим слово <tex>w=w_1 \omega[n+1] = cdots w_m</tex> НКА будет находиться в состояниях , которое принимает автомат ДКА: <tex>\langle s_d, w_1w_2 \dots w_m \rangle \vdash \langle {u_d}_1, w_2 \dots w_m \rangle \vdash^* \delta_N(q_1langle {u_d}_m, c)...\delta_N(q_kvarepsilon \rangle, c){u_d}_m \in T_d</tex>. Проверим, а ДКА в состоянии что НКА тоже принимает это слово. Так как <tex>Ps_d =\delta_D(Q, c){s\}</tex>, причем, в силу построения, оно будет допускающим, когда одно и мы из <tex>s_d</tex> достигли <tex>{u_d}_m \delta_N(q_1in T_d</tex>, c)...возьмём любое терминальное состояние <tex>u_m \delta_N(q_k, c)in {u_d}_m</tex>. По нашему наблюдению в НКА есть путь из <tex>s</tex> в <tex>u_m</tex> по строке <tex>w</tex> {{---}} допускающее, а, значит, НКА принимает это слово. Что нам Таким образом, множества слов, допускаемых ДКА и требовалосьНКА, совпадают, то есть они эквивалентны.