Все недетерминированные конечные автоматы можно превратить в эквивалентные детерминированные конечные автоматы. Однако детерминированные конечные автоматы допускают только одну стрелку на символ, указывающую из состояния. Следовательно, его штаты должны входить в состав множества штатов НФА. Похоже, это указывает на то, что число штатов DFA может экспоненциально масштабироваться с точки зрения количества штатов NFA. Однако мне было интересно, как на самом деле это доказать.
automata
finite-automata
nondeterminism
Джон Хоффман
источник
источник
Ответы:
Одна операция, которая преобразует NFA в другую NFA, но не делает этого для DFA, - это разворот (направьте все стрелки в обратном направлении и поменяйте местами начальные состояния с принимающими состояниями). Язык, распознаваемый преобразованным автоматом, является обращенным языком .Lр= { тыn - 1… Ты0∣ ты0… Тыn - 1∈ L }
Таким образом, одна идея состоит в том, чтобы искать язык, который имеет асимметричную конструкцию. В дальнейшем этот язык должен быть распознан путем проверки первых символов, требующих только n + O ( 1 ) состояний. Возвращаясь назад, необходимо сохранить память о последних n состояниях, для чего требуется A n + O ( 1 ) состояний, где A - размер алфавита.N n + O ( 1 ) N AN+ O ( 1 ) A
Мы ищем язык вида где M n состоит из слов длины n , S - нетривиальное подмножество алфавита, а M ′ не предоставляет каких-либо дополнительных ограничений. Мы могли бы также выбрать самый простой алфавит A = { a , b } (одноэлементный алфавит не подойдет, там вы не получите меньшие NFA) и M ′ = A ∗ . Нетривиальный S означает S = { a } . Что касаетсяMNSM' MN N S M' A={a,b} M′=A∗ S S={a} , мы требуем, чтобы он не коррелировал с S (так что DFA для обращенного языка должен будет хранить память S ): возьмем M n = A n .Mn S S Mn=An
Итак, пусть . Это распознается простым DFA с n + 2 состояниями.Ln=(a|b)na(a|b)∗ n+2
Обращение его приводит к NFA, который распознает .LRn=(a|b)∗a(a|b)n
Минимальная ДКА , который распознает имеет , по меньшей мере , 2 п + 1 состояние. Это потому, что все слова длиной 2 n + 1 должны достигать различных состояний в DFA. (Другими словами, они принадлежат к разным классам эквивалентности Майхилла-Нерода .) Чтобы доказать это, возьмем два разных слова u , v ∈ A n + 1 и пусть k будет позицией, в которой они различаются ( u k ≠ v k ). Не ограничивая общности, предположим , что у KLRn 2n+1 2n+1 u,v∈An+1 k uk≠vk и v k = b . Тогда u b k ∈ L R n и v b k ∉ L R n ( b k является отличительным расширением для u и v ). Если бы u и v приводили к одному и тому же состоянию в DFA, распознающем L R n, то и u b k, и v b kuk=a vk=b ubk∈LRn vbk∉LRn bk u v u v LRn ubk vbk , что невозможно, поскольку один ведет к принимающему состоянию, а другой - нет.
Подтверждение: этот пример был приведен в Википедии без объяснений. В статье дается ссылка на статью, которую я не читал, которая дает более
строгую оценку: Leiss, Ernst (1981), «Краткое представление регулярных языков с помощью булевых автоматов», Теоретическая информатика 13 (3): 323–330, doi: 10.1016 / S0304-3975 (81) 80005-9 .
источник
Рассмотрим следующее семейство языков:Ln={x1,x2,…,xk#xk+1:∃i∈{1,…,k} with xi=xk+1}
Я почти уверен, что в книге Сипсера есть этот пример.
источник
Этот пример также показывает, что NFA могут подвергаться экспоненциальному увеличению при комплементации. Действительно, известно, что любая NFA (или даже неконтекстная грамматика) для языка всех слов, содержащего все символы алфавита, должна иметь экспоненциальное число состояний.
источник