NFA к вопросу DFA
Во-первых, это не вопрос, просящий алгоритм преобразовать NFA в DFA.
Это знало (и доказало), который эквивалентный DFA NFA имеет самое большее 2n состояния, даже при том, что большинство времен это будет иметь более или менее то же количество состояний как NFA.
Как я могу предсказать оценку для количества состояний, которые будет иметь NFA-эквивалентный DFA? Который конкретный тип NFA потребует, чтобы эквивалентный DFA имел 2n состояния?
Моя причина выяснения у этого состоит в том, чтобы быть в состоянии "изобрести" некоторый NFAs, который, конечно, произведет, не рассматривая минимизацию, 2n - 1 состояние плюс "мертвое состояние".
2 ответа
Количество состояний взрывается из-за недетерминизма, что является ключом к вашему вопросу.
Если взять NFA, в которой каждый переход определяется однозначно, т.е. детерминированную NFA, то это ничто иное, как обычная DFA. Однако, как только вы имеете состояние, в котором возможны два перехода, это отличается от DFA.
Рассмотрим алгоритм преобразования и посмотрим, что произойдет, если вы имеете два или более переходов с одной и той же меткой для состояния. Именно здесь вам нужны те новые состояния, которые соответствуют множествам состояний.
Так что вопрос сводится к тому, чтобы выяснить, сколько из этих сверхсложных состояний на самом деле достижимо. Конечно, для этого можно придумать причудливый алгоритм, но чтобы получить правильное число, просто запустите обычный алгоритм преобразования и удалите недостижимые состояния.
Что касается NFA с n состояниями, для которых эквивалентная DFA имеет 2^n состояний, подумайте об использовании недетерминизма. Первая идея заключается в том, чтобы обозначить все переходы одинаково, однако, это не очень хорошо работает. Вместо этого помните, что вам нужно каким-то образом достигать всех подмножеств состояний с некоторой меткой каждое.
Если вы не считаете начальное состояние, то вы можете сделать следующую конструкцию: создать узлы и для каждого множества из 2^n создать уникальную метку и в NFA добавить переход с этой меткой к каждому узлу этого множества. Это даст вам NFA с n+1 состояниями (1 - начальное состояние), где DFA требует 2^n +1 состояний. Конечно, это становится сложнее, если вы хотите иметь 2^n состояний DFA после сворачивания.
.Хорошо, начнем с предположения, что n -> n. Теперь при каждом недетерминистическом переходе, при котором из одного состояния вы можете оказаться в x других, умножайте вашу оценку на x. Это может быть неточно, так как вы можете двойной подсчет. Но это должно дать вам верхнюю границу.
Однако, единственный верный способ - это построить соответствующую DFA, а затем посчитать состояния (я думаю).
Наконец, вы, вероятно, можете упростить некоторые из DFA (и NFA, если уж на то пошло), но это совершенно новая история ...