Конструкция 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 , q 0 , F ) , в котором Q — набор состояний, Σ — набор входных символов, T — функция перехода (отображение состояния и входной символ для набора состояний), q 0 — начальное состояние, а F — набор принимающих состояний. Соответствующий DFA имеет состояния, соответствующие подмножествам Q . Начальным состоянием DFA является { q 0 } , (одноэлементный) набор начальных состояний. Функция перехода DFA отображает состояние S (представляющее подмножество Q ) и входной символ x в набор T ( S , x ) = ∪{ T ( q , x ) | q ∈ S } — множество всех состояний, которых можно достичь посредством x перехода из состояния в S. - Государство S DFA является принимающим состоянием тогда и только тогда, когда хотя бы один член S является принимающим государством NFA. [2] [3]
В простейшей версии конструкции набора степеней набор всех состояний DFA является степеней набором Q , набором всех возможных Q. подмножеств Однако многие состояния результирующего DFA могут оказаться бесполезными, поскольку они могут быть недоступны из исходного состояния. Альтернативный вариант конструкции создает только те состояния, которые действительно достижимы. [4]
NFA с ε-ходами
[ редактировать ]Для NFA с ε-ходами (также называемыми ε-NFA) конструкция должна быть изменена для работы с ними путем вычисления ε- замыкания состояний: набора всех состояний, достижимых из некоторого заданного состояния с использованием только ε-ходов. Ван Ноорд признает три возможных способа включения этого вычисления замыкания в конструкцию powerset: [5]
- Вычислите ε-замыкание всего автомата на этапе предварительной обработки, создав эквивалентный NFA без ε-ходов, а затем примените обычную конструкцию степенного набора. Эта версия, также обсуждавшаяся Хопкрофтом и Ульманом, [6] прост в реализации, но непрактичен для автоматов с большим количеством ε-ходов, которые обычно возникают в приложениях обработки естественного языка . [5]
- Во время вычисления набора мощности вычислите ε-замыкание каждого состояния 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 .