NFA в DFA вопрос

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

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

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

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

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

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

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

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

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

Возьмем в качестве функции 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]*, у которых N-ая от последней буква равна a.

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

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

Чтобы еще больше расширить превосходный ответ Джонатана Граэля.

Добавьте к каждому состоянию 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 состояний.