Введение
Метод приведения конечных автоматов к детерминированному виду
В теории вычислений и теории автоматов, построение по множеству степеней (powerset construction) или построение по подмножествам является стандартным методом преобразования недетерминированного конечного автомата (NFA) в детерминированный конечный автомат (DFA), распознающий тот же формальный язык. Это важно с теоретической точки зрения, поскольку демонстрирует, что НКА, несмотря на их дополнительную гибкость, не способны распознавать язык, который не может быть распознан каким-либо ДКА. Это также важно на практике для преобразования НКА, которые проще построить, в ДКА, которые более эффективно выполняются. Однако, если НКА имеет n состояний, результирующий ДКА может иметь до 2n состояний, что экспоненциально больше, и иногда делает построение непрактичным для больших НКА. Построение, иногда называемое построением по множеству степеней Рабина — Скотта (или построением по подмножествам), чтобы отличать его от аналогичных построений для других типов автоматов, было впервые опубликовано Майклом О. Рабином и Даной Скоттом в 1959 году.
In the theory of computation and automata theory, the powerset construction or subset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language that cannot be recognized by some DFA. It is also important in practice for converting easier to construct NFAs into more efficiently executable DFAs. However, if the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs. The construction, sometimes called the Rabin–Scott powerset construction (or subset construction) to distinguish it from similar constructions for other types of automata, was first published by Michael O. Rabin and Dana Scott in 1959.
Интуиция
Для моделирования работы ДКА на заданной входной строке необходимо отслеживать одно состояние в любой момент времени: состояние, в которое автомат перейдет после обработки префикса входной строки. В отличие от этого, для моделирования НКА необходимо отслеживать множество состояний: все состояния, в которые автомат мог бы перейти после обработки того же префикса входной строки, в соответствии с недетерминированными переходами автомата. Если после определенного префикса входной строки достижимо множество состояний S, то после следующего входного символа x множество достижимых состояний является детерминированной функцией от S и x. Следовательно, множества достижимых состояний НКА играют ту же роль в моделировании НКА, что и отдельные состояния ДКА в моделировании ДКА, и фактически множества состояний НКА, возникающие в процессе моделирования, можно интерпретировать как состояния ДКА.
Строительство
Конструкция подмножеств применяется непосредственно к NFA, которая не допускает переходов между состояниями без потребления входных символов (также известных как "ε-переходы"). Такой автомат может быть определен как 5-ка (Q, Σ, T, q0, F), где Q – множество состояний, Σ – множество входных символов, T – функция перехода (отображающая состояние и входной символ в множество состояний), q0 – начальное состояние, а F – множество принимающих состояний. Соответствующий DFA имеет состояния, соответствующие подмножествам Q. Начальное состояние DFA – это множество, состоящее из одного начального состояния. Функция перехода DFA отображает состояние S (представляющее подмножество Q) и входной символ x в множество – множество всех состояний, которые могут быть достигнуты переходом по x из какого-либо состояния в S. Состояние S в DFA является принимающим, если и только если хотя бы один элемент S является принимающим состоянием в NFA. В простейшей версии построения подмножеств, множество всех состояний DFA является подмножеством Q, множеством всех возможных подмножеств Q. Однако многие состояния полученного DFA могут быть бесполезными, поскольку они могут быть недостижимы из начального состояния. Альтернативная версия построения создает только те состояния, которые действительно достижимы.
A state S of the DFA is an accepting state if and only if at least one member of S is an accepting state of the NFA. In the simplest version of the powerset construction, the set of all states of the DFA is the powerset of Q, the set of all possible subsets of Q. However, many states of the resulting DFA may be useless as they may be unreachable from the initial state. An alternative version of the construction creates only the states that are actually reachable.
NFA с ε-движениями
Для NFA с ε-переходами (также называемой ε-NFA) конструкцию необходимо модифицировать для обработки этих переходов, вычисляя ε-замыкание состояний: множество всех состояний, достижимых из заданного состояния, используя только ε-переходы. Ван Норд выделяет три возможных способа включения вычисления этого замыкания в построение множества степеней:
Вычислить ε-замыкание всего автомата как предварительный этап обработки, получив эквивалентный NFA без ε-переходов, а затем применить стандартное построение множества степеней. Эта версия, также обсуждаемая Хопкрофтом и Уллманом, проста в реализации, но непрактична для автоматов с большим количеством ε-переходов, что часто встречается в задачах обработки естественного языка. Во время построения множества степеней вычислять ε-замыкание каждого состояния q, рассматриваемого алгоритмом (и сохранять результат в кэше). Во время построения множества степеней вычислять ε-замыкание каждого подмножества состояний Q', рассматриваемого алгоритмом, и добавлять его элементы в Q'.
Многочисленные начальные состояния
Если недетерминированные конечные автоматы (NFA) определены таким образом, чтобы допускать несколько начальных состояний, то начальным состоянием соответствующего детерминированного конечного автомата (DFA) является множество всех начальных состояний NFA, или (если NFA также имеет ε-переходы) множество всех состояний, достижимых из начальных состояний по ε-переходам.
Пример
Нижеприведенный 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 недостижимы.
Сложность
[[Файл:NFA и взрыв эквивалент DFA 01. svg|thumb|upright=1.8|НКА с 5 состояниями (слева), эквивалентный ДКА (справа), требующий 16 состояний. Простой пример, требующий почти такого же количества состояний, – это язык строк над алфавитом {0,1}, содержащих как минимум n символов, при этом n-й с конца символ равен 1. Он может быть представлен НКА с (n + 1) состояниями, но для его реализации требуется 2^(n) состояний ДКА, по одному для каждого суффикса входной строки длиной n; см. рисунок для n=4. Конструкция Сафры, преобразующая недетерминированный автомат Бюхи с n состояниями в детерминированный автомат Мюллера или детерминированный автомат Рабина с 2O(n log n) состояниями, использует построение по подмножествам (powerset construction) как часть своего механизма.