Вопрос от NFA к DFA

Question

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

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

Как я могу спрогнозировать оценку количества состояний, которые будут иметь DFA, эквивалентные 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. Это может быть не точным, так как вы можете дважды отсчета. Но это должно дать вам верхнюю границу.

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

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

Answer 3

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

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

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

Answer 4

Для дальнейшего расширения отличного ответа Джонатана Греля.

Добавить в каждое состояние 0, 1, ..., N из A(N) Selfloop помечен 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 состояния.