NFA z wykładniczą liczbą stanów po rozpoznaniu

10

Jak zbudować przykład DFA, który ma stanów, w których równoważny NFA ma stanów. Oczywiście zestaw stanów DFA powinien zawierać wszystkie podzestawy zestawu stanów NFA, ale nie wiem jak zacząć. Jakieś sugestie, żeby postawić mnie na właściwej drodze? $2^n$ $n$

automata finite-automata

— saadtaame
źródło

To pytanie jest nieco niejasne. Ogólnie rzecz biorąc, istnieje nieskończenie wiele równoważnych DFA dla każdego danego języka regularnego i nieskończenie wiele równoważnych NFA dla dowolnego danego języka regularnego. Jeśli chcesz mieć minimalne DFA z stanami, nie zawsze jest to nawet możliwe, ponieważ różne NFA mogą rozpoznawać ten sam język i mieć różną liczbę stanów, ale odpowiadają temu samemu minimalnemu DFA. Jeśli dodatkowo chcesz wziąć pod uwagę „minimalne” NFA, staje się to nieco bardziej interesujące ...

2^{n}

$2^n$

— Patrick87,

2

Patrick, myślę, że OP oznacza przykład, w którym minimalna DFA jest wykładniczo większa niż minimalna NFA.

— Yuval Filmus

@ Patrick87 Nie szukam algorytmu. Wszystko czego chcę to przykład pary maszyn: DFA z

2^{n}

$2^n$ stanami i NFA z

n

$n$ stanami akceptującymi ten sam język.

— saadtaame

@saadtaame: To banalne: weź dowolny DFA i dodaj wystarczającą liczbę stanów, aby osiągnąć

2^{n}

$2^n$ . Ciekawym przykładem są te, w których minimalna równoważna DFA ma tyle samo stanów.

— Raphael

1

Zauważ, że artykuł w Wikipedii na temat minimalizacji DFA zawiera odpowiednie przykłady (chociaż sam musisz dowiedzieć się o małym NFA).

— Raphael

18

Standardowym przykładem jest język wszystkich słów nad alfabetem o rozmiarze , które nie zawierają wszystkich różnych liter. Jest akceptując NFA z stanów (lub stanów, jeśli pozwalają na wielokrotne stany wyjściowe): najpierw odgadnąć list których brakuje, a następnie przejść (z Odsuń) na rzecz zakładu przejmującego stanu z własnym pętli dla wszystkich liter innych niż . $L$ $A$ $n$ $L$ $n+1$ $n$ $a$ $\epsilon$ $A$

Każdy DFA dla wymaga co najmniej stanów. Można to zobaczyć za pomocą twierdzenia Myhill-Nerode. Niech będą dwoma różnymi podzbiorami słów i które zawierają wszystkie i tylko litery odpowiednio w . Bez utraty ogólności załóżmy, że , i niech . Następnie , podczas gdy . $L$ $2^n$ $S_1,S_2$ $A$ $w(S_1),w(S_2)$ $S_1,S_2$ $a \in S_1 \setminus S_2$ $w = w(A-a)$ $w(S_1)w \notin L$ $w(S_2)w \in L$

— Yuval Filmus
źródło

10

jest to ćwiczenie z książki „Finite Automata” Mark V. Lawson Heriot-Watt University, Edynburg, strona 68:

Niech . Pokaż, że język może zostać rozpoznany przez niedeterministyczny automat ze stanami . Pokaż, że każdy automat deterministyczny rozpoznający ten język musi mieć co najmniej stany. Ten przykład pokazuje, że wykładniczy wzrost liczby stanów przechodzących od niedeterministycznego automatu do odpowiedniego automatu deterministycznego jest czasami nieunikniony. $n \geq 1$ $(0+1)^\ast 1(0+1)^{n−1}$ $n+1$ $2^n$

— MK Dadsetani
źródło

10

Zgaduję, że masz na myśli, że optymalny DFA ma stanów. Może to nie daje ci stanów, ale jest to . $2^n$ $2^n$ $\Omega(2^n)$

Z „Złożoności komunikacyjnej” Kushilevitza i Nisana w ćwiczeniu 12.6:

„W przypadku niektórych stałych [nieujemnych liczb całkowitych] , rozważ (skończony) język .” $c$ $L_c = \{ww\mid w \in \{0,1\}^c\}$

a książka dalej prosi o udowodnienie, że możesz znaleźć współ-NFA rozpoznającego który używa stanów , a także że nie możesz zrobić lepiej niż stany dla DFA. $L_c$ $O(c)$ $\Omega(2^c)$

— Timothy Sun
źródło

Ponadto dowód drugiej części „wymaga” złożoności komunikacji, więc może nie być odpowiedni do twoich celów.

— Timothy Sun

Dziękuję za odpowiedź! Co masz na myśli przez co-NFA?

— saadtaame

Zasadniczo przełącz „akceptuj” na „odrzucając” w definicji NFA. Oznacza to, że jeśli żadna z możliwych ścieżek nie prowadzi do stanu odrzucenia, akceptujesz, w przeciwnym razie odrzucasz.

— Timothy Sun

W rzeczywistości dolna granica dość łatwo wynika z Myhill-Nerode. (W rzeczywistości można uzyskać coś takiego jak .) Ale moje współdziałanie z NFA używa stanów .

2^{c}

$2^c$

(c + 1) 2^{c}

$(c+1)2^c$

Θ (c^{2})

$\Theta(c^2)$

— Yuval Filmus

Skończone języki są pod tym względem nieco nudne. Zobacz także tutaj .

— Raphael

9

To późna odpowiedź, ale najwyraźniej nikt nie dał optymalnego rozwiązania. Weź , i , z Ten NFA na dwuliterowy alfabet ma stanów, tylko jeden stan początkowy i jeden końcowy, a jego równoważny minimalny DFA ma stanów. $A = \{a, b\}$ $Q_n = \{0, 1, \ldots, n-1\}$ ${\cal A}_n = (Q_n, A, E_n, \{0\}, \{0\})$

E_{n} = {(i, a, i + 1) ∣ 0 ⩽ i ⩽ n - 1} \cup {(n - 1, a, 0)} \cup {(i, b, i) ∣ 1 ⩽ i \leq n - 1} \cup {(i, b, 0) ∣ 1 ⩽ i ⩽ n - 1}}

$E_n = \{(i, a, i+1) \mid 0 \leqslant i \leqslant n-1\} \cup \{(n-1, a, 0)\} \cup \{(i, b, i) \mid 1 \leqslant i \leq n-1\} \cup \{(i, b, 0) \mid 1 \leqslant i \leqslant n-1\}\}$

n

$n$

2^{n}

$2^n$

— J.-E. Kołek
źródło

3

Bardzo mądry! Językiem akceptowanym przez ten automat jest , gdzie składa się ze wszystkich słów zawierających literę co najwyżej razy.

(a^{n} + a W_{n - 1} b)^{*}

$(a^n + aW_{n-1}b)^*$

W_{n - 1}

$W_{n-1}$

a

$a$

n - 1

$n-1$

— Yuval Filmus

2

@ yuval-filmus Ten przykład nie jest mój. Chciałem podać referencje, ale w tej chwili nie pamiętam, gdzie to widziałem.

— J.-E.