Изменения

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