Если язык (L) распознается NFA из n-состояний, может ли он также распознаваться DFA с не более чем 2 ^ n состояниями?

Question

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

Я здесь не прав?

Answer 1

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

Но, как упомянул @SasQ, это худший вариант развития событий. Как правило, вы не получите столько состояний, если используете алгоритм Хопкрофта или Брозовского.

Answer 2

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

Но, насколько мне известно, алгоритм для прогнозирования того, сколько состояний в действительности будет иметь результирующий DFA, еще не существует.Поэтому, если вы найдете это, пожалуйста, дайте мне знать;)