Jakie są warunki maksymalnego rozmiaru NFA dla jego równoważnego DFA?

Wiemy, że DFA są równoważne NFA pod względem siły wyrazu; znany jest również algorytm konwersji NFA na DFA (niestety teraz znam twórcę tego algorytmu), który w najgorszym przypadku daje nam $2^S$ stany , jeśli nasz NFA ma stany $S$

Moje pytanie brzmi: co determinuje najgorszy scenariusz?

Oto transkrypcja algorytmu w przypadku niejasności:

Niech będzie NFA. Konstruujemy DFA gdzie $A = (Q,\Sigma,\delta,q_0,F)$ $A' = (Q',\Sigma,\delta',q'_0,F')$

, $Q' = \mathcal{P}(Q)$
, $F' = \{S \in Q' | F \cap S \neq \emptyset \}$
i $\delta'(S,a) =\bigcup_{s \in S} (\delta(s,a) \cup \hat \delta(s,\varepsilon))$
, $q'_0 = \{q_0\} \cup \hat \delta(q_0, \varepsilon)$

gdzie jest rozszerzona funkcja przejścia . $\hat\delta$ $A$

— Daniil
źródło

ponieważ komentarze mówią, że możesz uratować to Q, prosząc o „minimalną” NFA dla DFA (otwarty problem). zawsze myślałem, że ten problem jest ściśle związany z pytaniem P =? NP na różne sposoby i mam podobne sformułowania, które to sugerują. podobnie jest z pytaniem o „kompresowalne” vs „nieściśliwe” DFA, gdzie „nieściśliwe” jest najgorszym przypadkiem, tak że minimalna NFA jest prawie wielkości DFA. prawdopodobnie istnieje pewne twierdzenie, takie jak: „większość DFA pobranych losowo jest nieściśliwych [do NFA]”, ponieważ w teorii informacji istnieje podobna złożoność łańcuchów ciągów

— kolmogorowskich

Odpowiedzi:

Algorytm, o którym mówisz, nazywa się Powerset Construction i został opublikowany po raz pierwszy przez Michaela Rabina i Dana Scott w 1959 roku.

Aby odpowiedzieć na twoje pytanie, jak podano w tytule, nie ma maksymalnego DFA dla zwykłego języka, ponieważ zawsze możesz wziąć DFA i dodać tyle stanów, ile chcesz z przejściami między nimi, ale bez przejść między jednym z oryginalnych stanów i jeden z nowych. W związku z tym nowe państwa nie będzie osiągalny z początkowego stanu , więc język akceptowany przez automat nie zmieni (od pozostaną takie same dla wszystkich ). $q_0$ $\hat\delta(q_0,w)$ $w\in\Sigma^*$

To powiedziawszy, jasne jest, że NFA nie może mieć warunków, aby jego równoważny DFA był maksymalny, ponieważ nie ma unikalnego równoważnego DFA. Natomiast minimalny DFA jest unikalny aż do izomorfizmu.

Kanonicznym przykładem języka akceptowanego przez NFA z stanami z równoważnym DFA stanów jest NFA dla jest $n+1$ $2^n$

L = {w \in {0, 1}^{*} : | w | \geq n and the n -th symbol from the last one is 1} .

$L=\{w\in\{0,1\}^*:|w|\geq n\text{ and the $n$-th symbol from the last one is 1}\}.$

L

$L$

, przy czym

dla

A = ⟨ Q, {0, 1}, δ, q_{0}, {q_{n + 1}} ⟩

$A=\langle Q,\{0,1\},\delta,q_0,\{q_{n+1}\}\rangle$

δ (q_{0}, 0) = {q_{0}}

$\delta(q_0,0)=\{q_0\}$

δ (q_{0}, 1) = {q_{0}, q_{1}}

$\delta(q_0,1)=\{q_0,q_1\}$

δ (q_{i}, 0) = δ (q_{i}, 1) = {q_{i + 1}}

$\delta(q_i,0)=\delta(q_i,1)=\{q_{i+1}\}$

. DFA wynikająca z zastosowania konstrukcji PowerSet do tego NFA będzie miał

stanów, bo trzeba reprezentować wszystkie

słów długości

jak przyrostków danego słowa w

i \in {1, \dots, n}

$i\in\{1,\ldots,n\}$

2^{n}

$2^n$

2^{n}

$2^n$

n

$n$

L

$L$

— Janoma
źródło

Nawiasem mówiąc, jeśli chcesz, aby nawiasy klamrowe pojawiały się w trybie matematyki wyświetlania, użyj \\ {i \\}.

— Zach Langley,

@ZachLangley Próbowałem już, to nie działa :-(

— Janoma

Wygląda na to, że działa dla mnie w podglądzie. Nie mogę jednak przesłać zmiany, ponieważ dodam tylko cztery znaki, a minimum to sześć. Używasz dwóch odwrotnych ukośników i to nie działało?

— Zach Langley,

@ZachLangley Działa teraz, ale dwie rzeczy: po pierwsze, nie zadziałało, kiedy po raz pierwszy opublikowałem odpowiedź. Po drugie, myślę, że jest to niespójne z zachowaniem renderowania LaTeX w cstheory, ale mogę się mylić.

— Janoma

Wynikowy DFA jest minimalny? Czy możesz powiedzieć coś o tym, jak udowodnić, że jest minimalny?

— user834

Najgorszy przypadek $2^{s}$ pochodzi z liczby podzbiorów stanów NFA. Aby algorytm z twierdzenia Kleene'a dał równoważny DFA o najgorszej liczbie stanów, musi istnieć sposób na dotarcie do każdego możliwego podzbioru stanów w NFA. Przykład z dwoma stanami nad alfabetem $\{a, b\}$ has a transition from the initial state to the sole accepting state on symbol $a$ , a transition from the accepting state back to the initial on $b$ , and a transition from the accepting state back to itself on either an $a$ or a $b$ . The strings $\lambda$ , $a$ , $b$ , and $ab$ lead to subsets $\{q_{1}\}$ , $\{q_{2}\}$ , $\{\}$ , and $\{q_{1}, q_{2}\}$ , respectively, and these would need separate states in the DFA Kleene gives.

— Patrick87
źródło

zgodziło się, ale pytanie „czy jest sposób na dotarcie do każdego możliwego podzbioru stanów w NFA” jest nietrywialne i warte dalszych badań ....

— wer 1'12

-1

Uważam, że jest to pytanie z pogranicza wiedzy, czyli w zasadzie pytanie badawcze. Z szybkiego wyszukiwania w Google wydaje się, że jest w większości otwarty. Ponadto przez wiele lat uważałem, że jest to ważne i powiązane z dolnymi granicami teorii złożoności. Nie wspominasz bezpośrednio o analizie statystycznej, ale to sugeruje twoje pytanie. Oto dwa przykłady badań statystycznych dotyczących DFA / NFA, które są podobne, aby pokazać ogólne podejście do tego typu pytań. Wydaje się, że podstawowe badania empiryczne dotyczące takich pytań są nadal w większości niezbadane. Wprawdzie drugi nie dotyczy bezpośrednio twojego pytania, ale jest najbliższy, jaki mogłem znaleźć w obecnych badaniach.

Aby przestudiować twoje pytanie, można przewidzieć atak statystyczny, taki jak poniżej. Konstruowane są losowe NFA. Następnie określa się minimalny DFA. Wyświetl wykres histogramu, ile DFA wielkości $x$ wynik. Rozdziel „duże” DFA na podstawie pewnego progu. Sformułuj pewną miarę lub miarę NFA, która daje oszacowanie wynikowej wielkości DFA.

Metryka ta byłaby powiązana z metryką teorii grafów, taką jak gęstość krawędzi itp. Prawdopodobnie istnieje jakaś bardzo ważna metryka teorii grafów lub mieszanka metryk, która ocenia „wysadzenie”, ale nie jest to dla mnie od razu oczywiste. Mógłbym zasugerować coś w rodzaju metryki kolorowania wykresu lub metryki kliki. Następnie przetestuj metrykę w porównaniu z dwoma zestawami „wysadzenie w powietrze” vs „nie wysadzenie w powietrze”.

Inne odpowiedzi na twoje pytanie do tej pory podają jedynie przykładowy „wysadzenie” (przydatne w studium przypadku), ale nie odnoszą się do kluczowej kwestii ogólnej miary.

Kolejnym obszarem do przyjrzenia się z powodzeniem opracowanemu programowi badań empirycznych są badania punktu przejścia SAT. To rozwinęło bardzo głębokie powiązania z koncepcjami fizyki i termodynamiki. Wydaje mi się prawdopodobne, że podobne koncepcje mają tu zastosowanie. Na przykład można znaleźć analogiczne miary typu punktu przejścia; prawdopodobnie gęstość krawędzi itp. Zwróć uwagę na teorię ściśliwości Kołmogorowa.

Przypuszczam również, że NFA, które „wysadzają” w powietrze, w porównaniu z tymi, które nie są w jakiś sposób dość analogiczne do „twardych” i „łatwych” przypadków problemów z NP.

Yet another way to study this problem would be to formulate an NFA minimization problem. That is, given a DFA, find the minimal NFA, which last I heard (many years ago) was still an open problem.

[1] On the performance of automata minimization algorithms Marco Almeida, Nelma Moreira, Rogério Reis

[2] Automata Recognizing No Words: A Statistical Approach Cristian S. Calude, Cezar Câmpeanu, Monica Dumitrescu

— vzn
źródło