Экспоненциальное разделение между НФА и ДФА в присутствии союзов

15

Недавно был задан интересный вопрос, который впоследствии был удален.

Для обычного языка его сложность DFA - это размер минимального DFA, принимающего его, а сложность NFA - это размер минимального NFA, принимающего его. Хорошо известно, что между двумя сложностями существует экспоненциальное разделение, по крайней мере, когда размер алфавита не ограничен. Действительно, рассмотрим язык над алфавитом состоящим из всех слов, не содержащих всех символов. Используя теорему Майхилла-Нерода, легко вычислить сложность DFA 2 ^ n . С другой стороны, сложность NFA составляет только n (если допускается несколько начальных состояний; в противном случае это n + 1 ).LLn{1,,n}2nnn+1

Удален вопрос касался DFA покрытия сложности на языке, который является минимальным такая , что можно записать в виде (не обязательно пересекаются) объединение языков сложности DFA в большинстве . DFA, покрывающий сложность составляет всего .L C L n 2CLCLn2

Существует ли экспоненциальное разделение между сложностью NFA и сложностью DFA?

Юваль Фильмус
источник

Ответы:

8

Рассмотрим язык , где - новый символ. Сложность NFA равна . Мы покажем, что сложность покрытия DFA равна . # M n n 2 nMn=ϵ+(Ln#)Ln#Mnn2n

Пусть - DFA, принимающий некоторый язык с функцией перехода . Назовите состояние жизнеспособным, если существует какое-то слово такое, что является принимающим состоянием. Для любых двух безотказных состояний пустьНетрудно проверить, что каждое слово может быть записано как где для некоторого жизнеспособного .L ( A ) M n q A s w q A ( s , w ) s , t A s , t = { w ( 1 + + n ) : q A ( s , w ) = t } . w L ( A ) w = w 1 #AL(A)MnqAswqA(s,w)s,t

As,t={w(1++n):qA(s,w)=t}.
wL(A)w iA s i , t i s i , t iw=w1##wlwiAsi,tisi,ti

Предположим, что , где каждый является DFA. Пусть - решетка, порожденная всеми языками . Мы можем рассматривать как язык над , пробелом между любыми двумя символами, соответствующими . Согласно этой точке зрения, соответствует .A i P A i s , t L ( A i ) L P ( A i ) P # M n P Mn=i=1NL(Ai)AiPAs,tiL(Ai)LP(Ai)P#MnP

Назовем универсальным, если для некоторого это тот случай, когда для всех найдется такой, что . Покажем, что некоторая универсальна. В противном случае каждый содержит не более слов длины . В общей сложности должно содержать все слова длины , следовательно, , что нарушается при достаточно большом .x P y P z P x y z L P ( A i ) L P ( A i ) L P ( A i ) ( | P | - 1 ) l l L P ( A i ) | P | л л | пLP(Ai) xPyPzPxyzLP(Ai)LP(Ai)LP(Ai)(|P|1)llLP(Ai)|P|ll l|P|lN(|P|1)ll

Предположим, что универсален, и для краткости напишите . Пусть будет соответствующим префиксом, и пусть будет некоторым словом, соответствующим ему. Таким образом, для каждого существует некоторый такой, что .A = A i x P x M n y L n z yM n x # y # z yL ( A i )LP(Ai)A=AixPxMnyLnzyMnx#y#zyL(Ai)

Для подмножества , пусть состоит из букв в написанных по порядку. Мы утверждаем , что слова неэквивалентны для Myhill-Nerode отношения . Действительно, предположим, что и найдем некоторый (без ограничения общности). Тогда то время как . Следовательно, должно иметь не менее состояний.y S S x # y S A S T a S T x # y T y { 1 , , n } - a # z y T y { 1 , , n } - aL ( A ) x # yS{1,,n}ySSx#ySASTaSTx#yTy{1,,n}a#zyTy{1,,n}aL(A)x#ySy{1,,n}a#zyTy{1,,n}aMnA2n

Юваль Фильмус
источник