NFA to DFA вопрос

Question

Во-первых, это не вопрос, касающийся алгоритма преобразования NFA в DFA.

Известно (и доказано), что эквивалентный DFA NFA имеет не более 2 ⁿ состояний, хотя в большинстве случаев он будет иметь более или менее такое же количество состояний, что и NFA.

Как я могу предсказать оценку числа штатов, которые будут иметь NFA-эквивалент? Какой конкретный тип NFA потребует, чтобы эквивалентный DFA имел 2 ⁿ состояний?

Моя причина, по которой я спрашиваю об этом, состоит в том, чтобы иметь возможность «изобрести» некоторые NFA, которые, безусловно, будут производить, не учитывая минимизацию, 2 ⁿ - 1 состояние плюс «мертвое состояние».

Answer 1

Количество состояний взрывается из-за недетерминизма , который является ключом к вашему вопросу.

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

Рассмотрите алгоритм преобразования и посмотрите, что произойдет, если у вас есть два или более переходов с одинаковой меткой для состояния. Именно здесь вам нужны те новые состояния, которые соответствуют наборам состояний.

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

Что касается NFA с n состояниями, для которых эквивалентный DFA имеет 2 ^ n состояний, подумайте об использовании недетерминизма. Первой идеей было бы пометить все переходы одинаково, однако это не слишком хорошо работает. Вместо этого помните, что вам нужно каким-то образом достичь всех подмножеств состояний с некоторыми метками.

Если вы не учитываете начальное состояние, то вы можете выполнить следующую конструкцию: создать n узлов и для каждого набора из 2 ^ n создать уникальную метку и в NFA добавить переход с этой меткой к каждому узлу этот набор. Это дает вам NFA с n + 1 состояниями (1 является начальным состоянием), где DFA требует 2 ^ n +1 состояний. Конечно, становится сложнее, если вы хотите иметь 2 ^ n состояний DFA после минимизации.

Answer 2

Хорошо, начнем с предположения, что n -> n. Теперь для каждого недетерминированного перехода, в котором из одного состояния вы можете попасть в x других состояний, умножьте свою оценку на x. Это может быть неточным, так как вы могли бы удвоить счет. Но это должно дать вам верхнюю границу.

Тем не менее, единственный верный способ - создать соответствующий DFA и затем подсчитать состояния (я думаю).

Наконец, вы, вероятно, можете упростить некоторые из DFA (и NFA в этом отношении), но это совершенно новая история ...

Answer 3

Чтобы еще больше рассказать о превосходном ответе Джонатана Грэла.

Добавьте к каждому состоянию 0, 1, ..., N из A(N) самоконтролируемый ярлык c, то есть добавьте следующие переходы:
0 c-> 0
1 c-> 1
...
N c-> N

Тогда, предполагая, что c никогда не срабатывает, DFA содержит те же 2^(N+1) состояния DFA Джонатана.Однако всякий раз, когда c наблюдается из состояния {S,j,k,...,z} <> {S}, мы достигаем состояния {j,k,...,z}.Следовательно, возможны все подмножества {S,0,...,N}, кроме пустого набора, и DFA имеет 2^(N+2)-1 состояния, в то время как A(N) имеет N+2 состояния.

Answer 4

Взять как функцию N с начальным состоянием S и конечным состоянием N, это NFA A(N):

S a-> S
S b-> S
S a-> 0 // NOTE: only "a" allows you to leave state S
0 a-> 1
0 b-> 1
1 a-> 2
1 b-> 2
...
N-1 a-> N
N-2 b-> N
N

Должно быть очевидно, что он принимает все строки в [ab]*, чья буква Nth от последней равна a.

Определение A(N) должно эффективно запомнить предыдущие N-1 буквы (вам нужно знать все позиции в этом окне, которые были a, чтобы, когда строка неожиданно заканчивалась, вы могли сказать, есть ли было a N букв назад).

Я не уверен, соответствует ли это именно тому количеству состояний, которое вы хотели, но это по крайней мере с коэффициентом 2 - возможны все подмножества {0,...,N}, но вы также всегда в S. Это должно быть 2^(N+1) состояний, но A(N) было N+2 состояний.