Изменения

[[Категория: Теория формальных языков]]== Алгоритм систем подмножеств Описание ==Данный алгоритм заменяет Алгоритм Томпсона строит по [[Недетерминированные конечные автоматы|НКА из <tex>n</tex> состояний на ]] эквивалентный [[Детерминированные конечные автоматы|ДКА из <tex>2^n</tex> состояний. НКА: <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta ]] следующим образом: Q \times \Sigma \to P(Q) \rangle</tex>. ДКА: <tex>\langle \Sigma , Q_d, \{s\} \in Q_d, T_d \subset Q_d, \delta_D : Q_d \times \Sigma \to Q_d \rangle</tex>, где <tex>Q_d = 2^Q</tex>* Начало. === Алгоритм ===* '''Задание состояний:Шаг 1.''' &nbsp;&nbsp;&nbsp;&nbsp;Состояние нашего ДКА будет соответствовать подмножеству состояний НКА - то есть их будет ровно Помещаем в очередь <tex>2^nQ</tex>множество, состоящее только из стартовой вершины. * '''Задание переходов:Шаг 2.'''Затем, пока очередь не пуста выполняем следующие действия: &nbsp;&nbsp;&nbsp;&nbsp;Возьмём состояние нашего ДКА ** Достаем из очереди множество, назовем его <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> {{---}} функция перехода хотя бы одна из вершин была терминальной в НКА. '''Задание стартового состояния:''' &nbsp;&nbsp;&nbsp;&nbsp;Стартовое состояние - состояние ДКА, соответствующее то соответствующая данному множеству из одного стартового состояния НКАвершина в ДКА также будет терминальной. '''Задание терминальных вершин:'''* Конец.

&nbsp;&nbsp;&nbsp;&nbsp;Если в подмножестве состояний == Построение эквивалентного ДКА по НКА есть хотя бы одна терминальная вершина, то вершина ДКА, соответствующая этому подмножеству, будет терминальной.==

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

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

#Докажем, что любое слово, которое принимает НКА, будет принято построенным ДКА. Заметим, что <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>, а, значит, НКАпринимает это слово. Таким образом, будет принято построенным множества слов, допускаемых ДКАи НКА, совпадают, то есть они эквивалентны.}}

&nbsp;&nbsp;&nbsp;&nbsp;Сделаем наблюдение, что если <tex>q \in q_d</tex> и символ перехода == Алгоритм Томпсона ==Данный алгоритм преобразовывает НКА в эквивалентный ДКА. Будем использовать вышеуказанный способ построения с одним дополнением {{- <tex>c</tex>, то <tex>\forall p \in \delta(q, c)</tex>: <tex>p \in \delta_D(q_d, c)</tex>--}} не будем учитывать состояния недостижимые из стартового.Поэтому в алгоритме используется обход в ширину.

&nbsp;&nbsp;&nbsp;&nbsp;Рассмотрим последовательность ===Алгоритм===* <tex>\mathtt{P}</tex> {{---}} очередь состояний, соответствующих множествам, состоящих из состояний НКА. * <tex>\mathtt{Q_d}</tex> {{---}} массив множеств, когда принимали слово соответствующих состояниям ДКА.* <tex>\mathtt{s}</tex> {{-- -}} стартовое состояние НКА. '''Automaton''' getDFAbyNFA(<tex>(q_1\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, q_mc)\}</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\}_1</tex> '''return''' <tex>\langle \Sigma, ...Q_d, \{q_ds\}_m), T_d, \delta_d \rangle</tex>.

&nbsp;&nbsp;&nbsp;&nbsp;Мы знаем===Асимптотика===Так как количество подмножеств множества состояний НКА не более, что чем <tex>q_m2^n</tex> - терминальная, так как НКА принимает слово. Надо доказать, что а каждое подмножество мы обрабатываем ровно один раз за время <tex>O(n)</tex>, получаем верхнюю оценку времени работы алгоритма {q_d{---}}_m<tex>O(n \cdot 2^n)</tex> - терминальная.

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

&nbsp;&nbsp;&nbsp;&nbsp;Рассмотрим последовательность состояний По нашему заданию эквивалентного ДКА, когда принимали слово - <tex>({q_d}_1, ..., {q_d}_m)</tex>.мы получаем:

&nbsp;&nbsp;&nbsp;&nbsp;Сделаем наблюдение, что если <tex>q_d</tex>, соответствует множеству из одного элемента - <tex>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>NKA_definition.png|250px]]

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

ПолучаетсяВ итоге получаем ДКА, что мы доказали, что если НКА принимает слово, равносильно тому, что ДКА его тоже принимает.эквивалентный исходному:

А это означает, что автоматы эквивалентны[[Файл:NKA_algorithm.png|250px]].}}

== Алгоритм Томпсона См. также ==Данный алгоритм преобразовывает НКА в эквивалентный ДКА.Мы будем использовать предыдущий алгоритм построения с одним дополнением - нам не нужны состояния недостижимые из стартового.

===Алгоритм=Источники информации ==<tex>Q</tex> - очередь состояний, соответствующих множествам, состоящих из состояний НКА* ''Серебряков В.<tex>s</tex> - стартовое состояние НКАА. '''Теория и реализация языков программирования. М.: МЗ-Пресс, 2003 (1:''' <tex>Q-е изд.push) и 2006 (\{s\})</tex> '''2:''' <tex>while</tex> <tex>not</tex> <tex>(isEmpty(Q-е изд))\{</tex> '''3:''' <tex>Q— С. 294.pop(q_d)</tex> '''4:''' <tex>for</tex> <tex>c \in \Sigma \{</tex> '''— ISBN 5:''' <tex>p_d = \o</tex> '''6:''' <tex>for</tex> <tex>q \in q_d</tex> '''7:''' <tex>p_d = p_d \cup \delta(q, c)</tex> '''8:''' <tex>if</tex> <tex>(p_d</tex> <tex>haven't</tex> <tex>been</tex> <tex>in</tex> <tex>Q</tex>) '''-94073-094-9:''' <tex>Q.push(p_d)</tex> '''10:''' <tex>\}</tex> '''11:''' <tex>\}</tex>

Верхняя оценка на работу алгоритмы - <tex>O(n \cdot 2^n)</tex> - так как количество подмножеств множества состояний НКА не более, чем <tex>2^n</tex>, а каждое подмножество мы обрабатываем за <tex>O(n)</tex> [[Категория: Теория формальных языков]][[Категория: Автоматы и ровно один раз.регулярные языки]]