Как доказать, что ДФА от НФА могут иметь экспоненциальное число штатов?

20

Все недетерминированные конечные автоматы можно превратить в эквивалентные детерминированные конечные автоматы. Однако детерминированные конечные автоматы допускают только одну стрелку на символ, указывающую из состояния. Следовательно, его штаты должны входить в состав множества штатов НФА. Похоже, это указывает на то, что число штатов DFA может экспоненциально масштабироваться с точки зрения количества штатов NFA. Однако мне было интересно, как на самом деле это доказать.

Джон Хоффман
источник
7
Это разумный вопрос, и конструкция не совсем очевидна, но все же это может быть домашнее задание. Итак, было бы полезно услышать, почему вы хотите знать.
Theres некоторые конструкции здесь , но кажется , что это должно быть в бумагоделательной где - нибудь. не знаю реф. Кроме того, мне кажется, что есть такая конструкция, что NFA считает в двоичном виде в своих активных состояниях и принимает только после примерно переходов ...? 2n
vzn
См. Также cs.stackexchange.com/questions/3381/…
Жиль "

Ответы:

15

Одна операция, которая преобразует NFA в другую NFA, но не делает этого для DFA, - это разворот (направьте все стрелки в обратном направлении и поменяйте местами начальные состояния с принимающими состояниями). Язык, распознаваемый преобразованным автоматом, является обращенным языком .LR={un1u0u0un1L}

Таким образом, одна идея состоит в том, чтобы искать язык, который имеет асимметричную конструкцию. В дальнейшем этот язык должен быть распознан путем проверки первых символов, требующих только n + O ( 1 ) состояний. Возвращаясь назад, необходимо сохранить память о последних n состояниях, для чего требуется A n + O ( 1 ) состояний, где A - размер алфавита.nn+O(1)nAn+O(1)A

Мы ищем язык вида где M n состоит из слов длины n , S - нетривиальное подмножество алфавита, а M не предоставляет каких-либо дополнительных ограничений. Мы могли бы также выбрать самый простой алфавит A = { a , b } (одноэлементный алфавит не подойдет, там вы не получите меньшие NFA) и M = A . Нетривиальный S означает S = { a } . Что касаетсяMnSMMnnSMA={a,b}M=ASS={a} , мы требуем, чтобы он не коррелировал с S (так что DFA для обращенного языка должен будет хранить память S ): возьмем M n = A n .MnSSMn=An

Итак, пусть . Это распознается простым DFA с n + 2 состояниями.Ln=(a|b)na(a|b)n+2

DFA

Обращение его приводит к NFA, который распознает .LnR=(a|b)a(a|b)n

NFA

Минимальная ДКА , который распознает имеет , по меньшей мере , 2 п + 1 состояние. Это потому, что все слова длиной 2 n + 1 должны достигать различных состояний в DFA. (Другими словами, они принадлежат к разным классам эквивалентности Майхилла-Нерода .) Чтобы доказать это, возьмем два разных слова u , v A n + 1 и пусть k будет позицией, в которой они различаются ( u kv k ). Не ограничивая общности, предположим , что у KLnR2n+12n+1u,vAn+1kukvk и v k = b . Тогда u b kL R n и v b kL R n ( b k является отличительным расширением для u и v ). Если бы u и v приводили к одному и тому же состоянию в DFA, распознающем L R n, то и u b k, и v b kuk=avk=bubkLnRvbkLnRbkuvuvLnRubkvbk, что невозможно, поскольку один ведет к принимающему состоянию, а другой - нет.

Подтверждение: этот пример был приведен в Википедии без объяснений. В статье дается ссылка на статью, которую я не читал, которая дает более
строгую оценку: Leiss, Ernst (1981), «Краткое представление регулярных языков с помощью булевых автоматов», Теоретическая информатика 13 (3): 323–330, doi: 10.1016 / S0304-3975 (81) 80005-9 .

Жиль "ТАК - перестань быть злым"
источник
Логический ответ: Состояния в DFA используются в качестве памяти (для хранения некоторой информации, например, двухпозиционного переключателя вентилятора), поэтому то, что может быть представлено в одном состоянии в DFA, может быть представлено с помощью комбинации состояний в эквивалентном NFA. По этой причине NFA имеет меньше состояний по сравнению с эквивалентным DFA. Теперь , если у вас есть состояния в множестве Q , то множество всех возможных комбинаций Q является мощность посаженными что 2 п , Так что, если мы поменяем НКУ из п состояний в эквивалентные DFA, то DFA будет состоять из не более 2 л состояния. - Имеет ли это смысл? nQQ2nn2n
Грижеш Чаухан
1
@GrijeshChauhan Это не то, что задал вопрос. Да, легко увидеть, что для каждого NFA с состояниями существует DFA с максимум 2 n состояниями. Но здесь мы хотим видеть, что граница достигнута, т. Е. Для любого n существует NFA с n- состоянием, такой что наименьший эквивалентный DFA имеет по крайней мере 2 n состояний (или близко к этому, здесь я докажу оценку 2 n - 1 ). n2nnn 2n2n1
Жиль "ТАК - перестать быть злым"
хм ... прочитав ваш ответ дважды и из комментария "Но здесь мы хотим видеть, что предел достигнут", теперь я мог бы понять. Благодарю.
Грижеш Чаухан
8

Рассмотрим следующее семейство языков: Ln={x1,x2,,xk#xk+1:i{1,,k} with xi=xk+1}

Ln{#,1,,n}

O(n)Lnnii3

Ln2O(n){1,,n}

Я почти уверен, что в книге Сипсера есть этот пример.

парень
источник
Конструкция в книге Сайпера дает DFA с ровно 2 ^ n состояниями. Если NFA имеет набор состояний Q, то набор состояний DFA - это Pow (Q), чтобы имитировать все возможные «параллельные» состояния, в которых может быть миг NFA. (Отредактируйте, чтобы добавить мнение по объему вопроса). Учитывая, что Конструкция, используемая для этого в стандартном тексте, ясно показывает возможность экспоненциального числа состояний, мне кажется, что это не уровень исследования. Может подойти как справочный запрос, хотя.
Логан Мэйфилд
8

nn2n

Этот пример также показывает, что NFA могут подвергаться экспоненциальному увеличению при комплементации. Действительно, известно, что любая NFA (или даже неконтекстная грамматика) для языка всех слов, содержащего все символы алфавита, должна иметь экспоненциальное число состояний.

Юваль Фильмус
источник
1
σΣ(Σσ)
ΣnO(n2)2n2n
Смысл этого примера в том, что взрыв соответствует точно конструкции силовой установки. Существует бинарный пример с таким же увеличением, но он более сложный.
Ювал Фильмус
Да, это хороший пример.
6005
1
O(nlogn)