Изменения

[[Категория: Теория формальных языков]]== Алгоритм систем подмножеств Описание ==Данный алгоритм заменяет Алгоритм Томпсона строит по [[Недетерминированные конечные автоматы|НКА из <tex>n</tex> состояний на ]] эквивалентный [[Детерминированные конечные автоматы|ДКА из <tex>2^n</tex> состояний]] следующим образом:* Начало.=== Алгоритм ===* '''Задание состояний:Шаг 1.''' Состояние нашего ДКА будет соответствовать подмножеству состояний НКА - то есть их будет ровно Помещаем в очередь <tex>2^nQ</tex>множество, состоящее только из стартовой вершины. * '''Задание переходов:Шаг 2.'''Затем, пока очередь не пуста выполняем следующие действия: Возьмём состояние нашего ДКА ** Достаем из очереди множество, назовем его <tex>q</tex>, соответствующее подмножеству состояний НКА {{---}} ** Для всех <tex>(a_1, a_2, ..., a_m)c \in \Sigma</tex>, и символ посмотрим в какое состояние ведет переход по символу <tex>c</tex>. Тогда из каждого состояния в <tex>\delta_D(q, c) = p</tex>, где p - состояние ДКА, соответствующее подмножеству . Полученное множество состояний НКА - положим в очередь <tex>\cup_{i=1}^{m} \delta(a_i, c)Q</tex>, где <tex>\delta_D</tex> {{---}} функция перехода только если оно не лежало там раньше. Каждое такое множество в итоговом ДКАбудет отдельной вершиной, а в которую будут вести переходы по соответствующим символам.** Если в множестве <tex>\deltaq</tex> {{---}} функция перехода в НКА. '''Задание стартового состояния:''' Стартовое состояние - состояние ДКА, соответствующее множеству хотя бы одна из одного стартового состояния НКА. '''Задание терминальных вершин:''' Если была терминальной в подмножестве состояний НКА есть хотя бы одна терминальная вершина, то соответствующая данному множеству вершина в ДКА, соответствующая этому подмножеству, также будет терминальной. '''Терминология:''' <tex>q</tex> - состояние НКА* Конец.

<tex>q_d</tex> - состояние == Построение эквивалентного ДКА.по НКА ==

Пусть нам дан произвольный НКА: <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta: Q \times \Sigma \to 2^Q \rangle</tex> - функция перехода в НКА.

Построим по нему следующий ДКА: <tex>\delta_Dlangle \Sigma , Q_d, s_d \in Q_d, T_d \subset Q_d, \delta_d : Q_d \times \Sigma \to Q_d \rangle</tex> - функция перехода в ДКА., где:# <tex>q Q_d = \{q_d \in mid q_d\subset 2^Q \}</tex> - ,# <tex>qs_d = \{s\}</tex> принадлежит ,# <tex>q_dT_d = \{q \in Q_d \mid \exists p \in T : p \in q\}</tex>, если множество состояний НКА, соответствующее состоянию # <tex>q_d</tex>\delta_d(q, c) = \{ \delta(a, содержит состояние <tex>c) \mid a \in q\}</tex>.

&nbsp;#Докажем, что любое слово, которое принимает НКА, будет принято построенным ДКА. Заметим, что <tex>\forall 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 \dots 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 {u_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 \in {u_d}_m</tex>, а из определения терминальных состояний в построенном ДКА мы получаем, что <tex>{u_d}_m \in T_d</tex>, то есть наш ДКА тоже принимает cлово <tex>w</tex> .#Докажем, что любое слово, которое принимает построенный ДКА, принимает и НКА. Сначала сделаем наблюдение, будет принято построенным что если <tex>q_d=\{q\}</tex>, и мы из него достигли по строке <tex>S</tex> какого-то состояния <tex>p_d</tex>, то <tex>\forall p \in p_d</tex> существует путь из <tex>q</tex> в <tex>p</tex> в НКА по строке <tex>S</tex>. Рассмотрим слово <tex>w=w_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 \langle {u_d}_m, \varepsilon \rangle, {u_d}_m \in T_d</tex>. Проверим, что НКА тоже принимает это слово. Так как <tex>s_d = \{s\}</tex>, и мы из <tex>s_d</tex> достигли <tex>{u_d}_m \in T_d</tex>, возьмём любое терминальное состояние <tex>u_m \in {u_d}_m</tex>. По нашему наблюдению в НКА есть путь из <tex>s</tex> в <tex>u_m</tex> по строке <tex>w</tex>, а, значит, НКА принимает это слово. Таким образом, множества слов, допускаемых ДКА и НКА, совпадают, то есть они эквивалентны.}} == Алгоритм Томпсона ==Данный алгоритм преобразовывает НКА в эквивалентный ДКА. Будем использовать вышеуказанный способ построения с одним дополнением {{---}} не будем учитывать состояния недостижимые из стартового.Поэтому в алгоритме используется обход в ширину. ===Алгоритм===* <tex>\mathtt{P}</tex> {{---}} очередь состояний, соответствующих множествам, состоящих из состояний НКА. * <tex>\mathtt{Q_d}</tex> {{---}} массив множеств, соответствующих состояниям ДКА.* <tex>\mathtt{s}</tex> {{---}} стартовое состояние НКА. '''Automaton''' getDFAbyNFA(<tex>\langle \Sigma, Q, s, T, \delta \rangle</tex> : '''Automaton'''): <tex>P</tex>.push(<tex>\{s\}</tex>) <tex>Q_d</tex> = <tex>\varnothing</tex> '''while''' <tex>P</tex> <tex> \neq </tex> <tex>\varnothing </tex> <tex>P</tex>.pop(<tex>p_d</tex>) '''for''' <tex>c \in \Sigma</tex> <tex>q_d</tex> = <tex>\varnothing</tex> '''for''' <tex>p \in p_d</tex> <tex>q_d</tex> = <tex>q_d \cup \{ \delta(p, c) \}</tex> <tex>\delta_d(p_d, q_d)</tex> = <tex>c</tex> '''if''' <tex>q_d \notin Q_d</tex> <tex>P</tex>.push(<tex>q_d</tex>) <tex>Q_d</tex>.add(<tex>q_d</tex>) <tex>T_d</tex> = <tex>\{q_d \in Q_d \mid \exists p \in T : p \in q_d\}</tex> '''return''' <tex>\langle \Sigma, Q_d, \{s\}, T_d, \delta_d \rangle</tex>

Сделаем наблюдение===Асимптотика===Так как количество подмножеств множества состояний НКА не более, что если чем <tex>q \in q_d</tex> и символ перехода - <tex>c2^n</tex>, то а каждое подмножество мы обрабатываем ровно один раз за время <tex>\forall p \in \deltaO(q, cn)</tex>: , получаем верхнюю оценку времени работы алгоритма {{---}} <tex>p O(n \in \delta_D(q_d, ccdot 2^n)</tex>.

Мы знаем, что <tex>q_m</tex> - терминальная, так как НКА принимает слово. Надо доказать, что <tex>{q_d}_m</tex> - терминальная[[Файл:DKA.png|250px]]

Заметим, что <tex>q_1 \in {q_d}_1</tex> - так как это стартовые состояния, а, значит, по По нашему наблюдению <tex>q_2 \in {q_d}_2</tex> и так далее. Получается, что <tex>q_m \in {q_d}_m</tex>. Мы знаем, что <tex>q_m</tex> - терминальная вершина, а, значит, по определению терминальной вершины в нашем заданию эквивалентного ДКА, что <tex>{q_d}_m</tex> - тоже терминальная.мы получаем:

&nbsp;<tex>2.</tex> Докажем, что любое слово, которое принимает построенный ДКА, принимает и НКА[[Файл:NKA_definition.png|250px]]

Рассмотрим последовательность состояний НКА#Помещаем в очередь множество из одной стартовой вершины — <tex>\{1\}</tex>: <tex>Q = \{\{1\}\}</tex>.#Достаём из очереди множество <tex>\{1\}</tex>: <tex>Q = \{\}</tex>.#<tex>q_d(\{1\}, a) = \{1, 2\}</tex>, когда принимали слово - кладём множество <tex>\{1, 2\}</tex> в очередь: <tex>Q = \{\{1, 2\}\}</tex>.#<tex>q_d(q_1\{1\}, b) = \{1\}</tex>, нам не надо класть множество <tex>\{1\}</tex> в очередь, так как оно уже там было.#Достаём из очереди множество <tex>\{1, 2\}</tex>: <tex>Q = \{\}</tex>.#<tex>q_d(\{1, 2\}, a) = \{1, 2\}</tex>, нам не надо класть множество <tex>\{1, 2\}</tex> в очередь, так как оно уже там было.#<tex>q_d(\{1, 2\}, q_mb)= \{1, 2\}</tex> - и последовательность состояний ДКА, когда принимали слово - нам не надо класть множество <tex>(\{q_d1, 2\}_1</tex> в очередь, так как оно уже там было...#Помечаем все терминальные вершины, в данном случае — <tex>\{q_d1, 2\}_m)</tex>.

Мы знаем, что <tex>{q_d}_m</tex> - терминальная, так как В итоге получаем ДКА принимает слово. Надо доказать, что <tex>q_m</tex> - терминальная.эквивалентный исходному:

}}== См. также == * [[Регулярные языки: два определения и их эквивалентность]]* [[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]* [[Теорема Клини (совпадение классов автоматных и регулярных языков)]]

== Алгоритм Томпсона Источники информации ==Данный алгоритм используется для преобразования НКА в ДКА* ''Серебряков В.А.Смысл этого алгоритма, как '' Теория и предыдущего, состоит в замене множества из <tex>n</tex> состояний НКА, множеством из <tex>2^n</tex> подмножеств его состоянийреализация языков программирования. Но не все из <tex>2^n</tex> состояний будут присутствовать в ДКА, ввиду недостижимости многих из них, поэтому в алгоритме используется обход в ширинуМ. ===Алгоритм===Вначале в очередь помещается множество: МЗ-Пресс, состоящее только из стартового состояния НКА <tex>{q_0}</tex>.Затем из очереди изымается очередное множество <tex>P</tex> {{-2003 (1--}} новое состояние ДКА. Если в <tex>P</tex> есть допускающие состояния, то оно допускающеее изд. Функция перехода строится по следующему правилу: <tex>\delta_D(P, c) = \bigcup_{q_i \in P}\delta_Nи 2006 (q_i, c)</tex>.<br>В результате <tex>\delta_D(P, c2-е изд)</tex> задаст новое состояние <tex>Q</tex> автомата— С. Если <tex>Q</tex> еще нет в ДКА, тогда мы помещаем <tex>Q</tex> в очередь294.Так как <tex>|Q_N|</tex> — ISBN 5- конечна, а <tex>|Q_D| \le 2^{|Q_N|}</tex>, то алгоритм завершится за конечное число шагов. Отсюда же получается верхняя оценка на время работы алгоритма {{94073-094--}} в худшем случае это <tex>O(2^n)</tex>.9

===Корректность===[[Категория: Теория формальных языков]]{{Утверждение|statement=Построенный автомат принимает тот же язык|proof=Применим индукцию по длине слова <tex>\omega</tex>.* <tex>|\omega|=1</tex>[[Категория: По построению стартовое состояние ДКА будет <tex>{s}</tex>, где <tex>s</tex> {{---}} стартовое состояние НКА, причем допускать они могут только одновременно.* Пусть для <tex>|\omega|=n</tex> - это верно, докажем, что верно Автоматы и для <tex>|\omega|=n+1</tex>: Пусть НКА на шаге n мог находиться в состояниях <tex>{q_1...q_k}</tex>, тогда ДКА, по построению, находится в состоянии <tex>Q={q_1...q_k}</tex>. После перехода по <tex>\omega[n+1регулярные языки]] = c</tex> НКА будет находиться в состояниях <tex>{\delta_N(q_1, c)...\delta_N(q_k, c)}</tex>, а ДКА в состоянии <tex>P=\delta_D(Q, c)</tex>, причем, в силу построения, оно будет допускающим, когда одно из <tex>{\delta_N(q_1, c)...\delta_N(q_k, c)}</tex> {{---}} допускающее. Что нам и требовалось.}}