Конструкция Powerset

В теории вычислений и теории автоматов или построение степенного множества построение подмножества — это стандартный метод преобразования недетерминированного конечного автомата (NFA) в детерминированный конечный автомат (DFA), распознающий тот же формальный язык . Это важно в теории, поскольку устанавливает, что NFA, несмотря на свою дополнительную гибкость, не способны распознавать любой язык, который не может быть распознан некоторыми DFA. На практике это также важно для преобразования более простых в построении NFA в более эффективно исполняемые DFA. Однако если NFA имеет n состояний, результирующий DFA может иметь до 2 состояний. ^н штатов, экспоненциально большее число, что иногда делает построение непрактичным для больших NFA.

Конструкция, которую иногда называют конструкцией степенного множества Рабина-Скотта (или конструкцией подмножества), чтобы отличить ее от аналогичных конструкций для других типов автоматов, была впервые опубликована Майклом О. Рабином и Даной Скотт в 1959 году. ^[1]

Интуиция

Чтобы смоделировать работу DFA с заданной входной строкой, необходимо в любой момент времени отслеживать одно состояние: состояние, которого автомат достигнет после просмотра префикса входных данных. Напротив, для моделирования NFA необходимо отслеживать набор состояний: все состояния, которых автомат может достичь после просмотра одного и того же префикса входных данных, в соответствии с недетерминированным выбором, сделанным автоматом. Если после определенного префикса входа может быть достигнут набор $S$ состояний, то после следующего входного символа $x$ набор достижимых состояний является детерминированной функцией $S$ и $x$ . Следовательно, наборы достижимых состояний NFA играют ту же роль в моделировании NFA, что и отдельные состояния DFA играют в моделировании DFA, и фактически наборы состояний NFA, появляющиеся в этом моделировании, могут быть переинтерпретированы как состояния DFA. ^[2]

Строительство

Конструкция powerset наиболее непосредственно применима к NFA, который не позволяет выполнять преобразования состояний без использования входных символов (также известных как «ε-перемещения»). Такой автомат можно определить как набор из 5 $(Q, Σ, T, q0 Σ, F)$ , в котором $Q$ — набор состояний, $—$ набор входных символов, $T$ — функция перехода (отображение состояния и входной символ для набора состояний), $q 0$ — начальное состояние, а $F$ — набор принимающих состояний. Соответствующий DFA имеет состояния, соответствующие подмножествам $Q$ . Начальным состоянием DFA является ${q 0}$ , (одноэлементный) набор начальных состояний. Функция перехода DFA отображает состояние $S$ (представляющее подмножество $Q$ ) и входной символ $x$ в набор $T (S, x) = \cup{T (q, x) | q \in S}$ — множество всех состояний, в которые можно попасть при $-$ переходе из состояния в $S.$ x Государство $S$ DFA является принимающим состоянием тогда и только тогда, когда хотя бы один член $S$ является принимающим государством NFA. ^[2]^[3]

В простейшей версии конструкции набора степеней набор всех состояний DFA является степеней набором $Q$ , набором всех возможных $Q.$ подмножеств Однако многие состояния результирующего DFA могут оказаться бесполезными, поскольку они могут быть недоступны из исходного состояния. Альтернативный вариант конструкции создает только те состояния, которые действительно достижимы. ^[4]

NFA с ε-ходами

Для NFA с ε-ходами (также называемыми ε-NFA) конструкция должна быть изменена для работы с ними путем вычисления ε- замыкания состояний: набора всех состояний, достижимых из некоторого заданного состояния с использованием только ε-ходов. Ван Ноорд признает три возможных способа включения этого вычисления замыкания в конструкцию powerset: ^[5]

Вычислите ε-замыкание всего автомата на этапе предварительной обработки, создав эквивалентный NFA без ε-ходов, а затем примените обычную конструкцию степенного набора. Эта версия, также обсуждавшаяся Хопкрофтом и Ульманом, ^[6] прост в реализации, но непрактичен для автоматов с большим количеством ε-ходов, которые обычно возникают в приложениях обработки естественного языка . ^[5]
Во время вычисления набора мощности вычислите ε-замыкание $\{q'~|~q\to _{\varepsilon }^{*}q'\}$ каждого состояния $q$ , которое рассматривается алгоритмом (и кэширует результат).
Во время вычисления набора мощности вычислите ε-замыкание $\{q'~|~\exists q\in Q',q\to _{\varepsilon }^{*}q'\}$ каждого подмножества состояний $Q',$ рассматриваемого алгоритмом, и добавляем его элементы в $Q'$ .

Несколько начальных состояний

Если NFA определены так, чтобы разрешить несколько начальных состояний, ^[7] начальным состоянием соответствующего ДКА является множество всех начальных состояний НКА или (если НКА также имеет ε-ходы) множество всех состояний, достижимых из начальных состояний ε-ходами.

Пример

Нижеприведенный NFA имеет четыре штата; состояние 1 является исходным, а состояния 3 и 4 — принимающими. Его алфавит состоит из двух символов 0 и 1 и имеет ε-ходы.

Начальное состояние DFA, построенное из этого NFA, представляет собой набор всех состояний NFA, достижимых из состояния 1 с помощью ε-ходов; то есть это набор {1,2,3}. Переход из {1,2,3} по входному символу 0 должен следовать либо по стрелке из состояния 1 в состояние 2, либо по стрелке из состояния 3 в состояние 4. Кроме того, ни состояние 2, ни состояние 4 не имеют исходящих ε-ходов. Следовательно, $T$ ({1,2,3},0) = {2,4}, и по тем же соображениям полный DFA, построенный из NFA, выглядит так, как показано ниже.

Как видно из этого примера, из начального состояния DFA можно достичь пяти состояний; остальные 11 наборов в наборе состояний NFA недоступны.

Сложность

Поскольку состояния DFA состоят из наборов состояний NFA, $NFA с n$ -состояниями может быть преобразовано в DFA с максимум $2 состояниями. н$ государства. ^[2] Для каждого $n$ существуют $NFA с n$ состояниями, такие, что каждое подмножество состояний достижимо из исходного подмножества, так что преобразованный DFA имеет ровно $2 н$ состояния, давая Θ( $2 н$ ) временная сложность наихудшего случая . ^[8]^[9] Простой пример, требующий почти такого же количества состояний, — это язык строк в алфавите {0,1}, в котором есть как минимум $n$ символов, $n$ -й от последнего из которых равен 1. Его можно представить в виде $(n + 1 )$ -государственный НФА, но для него требуется $2 н$ DFA утверждает: по одному на каждый $n$ -символьный суффикс входных данных; ср. картинка для $n =4$ . ^[4]

Приложения

Алгоритм Бжозовского для минимизации DFA дважды использует конструкцию powerset. Он преобразует входной DFA в NFA для обратного языка, меняя местами все стрелки и меняя роли начального и принимающего состояний, преобразует NFA обратно в DFA с использованием конструкции powerset, а затем повторяет свой процесс. Его сложность в наихудшем случае экспоненциальна, в отличие от некоторых других известных алгоритмов минимизации DFA, но во многих примерах он работает быстрее, чем можно было бы предположить из его сложности в наихудшем случае. ^[10]

Конструкция Сафры , преобразующая недетерминированный автомат Бюхи с $n$ состояниями в детерминированный автомат Мюллера или в детерминированный автомат Рабина с 2 состояниями. ^{О( $п$ журнал $п$ )} заявляет, использует конструкцию силового агрегата как часть своего оборудования. ^[11]

Ссылки

^ Рабин, Миссури ; Скотт, Д. (1959). «Конечные автоматы и проблемы их решения». Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 . ISSN 0018-8646 .
^ Перейти обратно: ^а ^б ^с Сипсер, Майкл (1997). «Теорема 1.19». Введение в теорию вычислений . стр. 55–56 . ISBN 0-534-94728-Х .
^ Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979). «Эквивалентность DFA и NFA». Введение в теорию автоматов, языки и вычисления . Чтение Массачусетса: Аддисон-Уэсли. стр. 22–23 . ISBN 0-201-02988-Х .
^ Перейти обратно: ^а ^б ^с Шнайдер, Клаус (2004). Верификация реактивных систем: формальные методы и алгоритмы . Спрингер. стр. 210–212. ISBN 978-3-540-00296-3 .
^ Перейти обратно: ^а ^б Ван Ноорд, Гертьян (2000). «Обработка эпсилон-ходов в построении подмножества» . Компьютерная лингвистика . 26 (1): 61–76. arXiv : cmp-lg/9804003 . дои : 10.1162/089120100561638 . S2CID 5622079 .
^ Хопкрофт и Ульман (1979) , стр. 26–27.
^ Роте, Йорг (2006). Теория сложности и криптология: введение в криптосложность . Тексты по теоретической информатике. Спрингер. стр. 21–22. ISBN 9783540285205 . .
^ Лупанов, Олег Борисович (1963). «Сравнение двух типов конечных источников». Проблемы Кибернетики . 9 : 321–326.
^ Мур, Фрэнк Р. (1971). «Об границах размера множества состояний в доказательствах эквивалентности детерминированных, недетерминированных и двусторонних конечных автоматов». Транзакции IEEE на компьютерах . С-20 (10): 1211–1214. дои : 10.1109/TC.1971.223108 . S2CID 206618275 . .
^ Бжозовский, Ю.А. (1963). «Канонические регулярные выражения и минимальные графы состояний для определенных событий». Учеб. Симпозиумы. Математика. Теория автоматов (Нью-Йорк, 1962) . Политехническое издательство Политехнического института. Бруклина, Бруклин, Нью-Йорк, стр. 529–561. МР 0175719 .
^ Сафра, С. (1988). «О сложности ω-автоматов». Материалы 29-го ежегодного симпозиума по основам информатики (FOCS '88) . Вашингтон, округ Колумбия, США: Компьютерное общество IEEE. стр. 319–327. дои : 10.1109/SFCS.1988.21948 . .

Дальнейшее чтение

Андерсон, Джеймс Эндрю (2006). Теория автоматов с современными приложениями . Издательство Кембриджского университета. стр. 43–49. ISBN 978-0-521-84887-9 .

[1] Рабин, Миссури ; Скотт, Д. (1959). «Конечные автоматы и проблемы их решения». Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 . ISSN 0018-8646 .

[sipser-2] Перейти обратно: ^а ^б ^с Сипсер, Майкл (1997). «Теорема 1.19». Введение в теорию вычислений . стр. 55–56 . ISBN 0-534-94728-Х .

[hu-3] Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979). «Эквивалентность DFA и NFA». Введение в теорию автоматов, языки и вычисления . Чтение Массачусетса: Аддисон-Уэсли. стр. 22–23 . ISBN 0-201-02988-Х .

[schneider-4] Перейти обратно: ^а ^б ^с Шнайдер, Клаус (2004). Верификация реактивных систем: формальные методы и алгоритмы . Спрингер. стр. 210–212. ISBN 978-3-540-00296-3 .

[vannoord-5] Перейти обратно: ^а ^б Ван Ноорд, Гертьян (2000). «Обработка эпсилон-ходов в построении подмножества» . Компьютерная лингвистика . 26 (1): 61–76. arXiv : cmp-lg/9804003 . дои : 10.1162/089120100561638 . S2CID 5622079 .

[6] Хопкрофт и Ульман (1979) , стр. 26–27.

[7] Роте, Йорг (2006). Теория сложности и криптология: введение в криптосложность . Тексты по теоретической информатике. Спрингер. стр. 21–22. ISBN 9783540285205 . .

[8] Лупанов, Олег Борисович (1963). «Сравнение двух типов конечных источников». Проблемы Кибернетики . 9 : 321–326.

[moore71-9] Мур, Фрэнк Р. (1971). «Об границах размера множества состояний в доказательствах эквивалентности детерминированных, недетерминированных и двусторонних конечных автоматов». Транзакции IEEE на компьютерах . С-20 (10): 1211–1214. дои : 10.1109/TC.1971.223108 . S2CID 206618275 . .

[10] Бжозовский, Ю.А. (1963). «Канонические регулярные выражения и минимальные графы состояний для определенных событий». Учеб. Симпозиумы. Математика. Теория автоматов (Нью-Йорк, 1962) . Политехническое издательство Политехнического института. Бруклина, Бруклин, Нью-Йорк, стр. 529–561. МР 0175719 .

[11] Сафра, С. (1988). «О сложности ω-автоматов». Материалы 29-го ежегодного симпозиума по основам информатики (FOCS '88) . Вашингтон, округ Колумбия, США: Компьютерное общество IEEE. стр. 319–327. дои : 10.1109/SFCS.1988.21948 . .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]