Dlaczego NFA nazywany jest niedeterministyczny?

14

Mam na myśli to [zabawne] pytanie. Dlaczego niedeterministyczny automat skończony nazywa się niedeterministyczny, podczas gdy my definiujemy przejścia dla danych wejściowych. Cóż, mimo że istnieje wiele przejść i epsilon , są one zdefiniowane, co oznacza, że maszyna jest deterministyczna dla tych przejść. Co oznacza, że jest deterministyczny.

finite-automata nondeterminism Madhusoodan P.
źródło

12

Niedeterministyczny stosowany w informatyce teoretycznej różni się od przypadkowego.

adrianN

10

Jest to wybór między przejściami, które jest niedeterministyczny.

reinierpost

Co to jest NFA? (Dla nieoświeconych wśród nas)

DarcyThomas,

@DarcyThomas, moim pierwszym wprowadzeniem było swtch.com/~rsc/regexp/regexp1.html . To dobra lektura - nie jest celem tego artykułu wprowadzenie NFA, ale robi to dobrze w dyskusji na temat wyrażeń regularnych.

Wildcard,

1

@Trilarion cs.stackexchange.com/questions/5008/…

adrianN

23

„Deterministyczny” oznacza „jeśli dwukrotnie postawisz system w tej samej sytuacji, gwarantuje się, że dokonasz tego samego wyboru za każdym razem”.

„Niedeterministyczny” oznacza „niedeterministyczny”, czyli innymi słowy „jeśli postawisz system dwukrotnie w tej samej sytuacji, może on lub nie dokonać tego samego wyboru za każdym razem”.

Niedeterministyczny automat skończony (NFA) może mieć wiele przejść poza stan. Oznacza to, że istnieje wiele opcji tego, co można zrobić w tej sytuacji. Nie musi się zawsze wybierać tego samego; na jednym wejściu może wybrać pierwsze przejście, a na innym wejściu może wybrać to samo przejście.

Tutaj możesz pomyśleć o „sytuacji” jako „w jakim stanie znajduje się NFA, wraz z tym, jaki symbol jest odczytywany następnie z wejścia”. Nawet jeśli oba są takie same, NFA nadal może mieć wiele pasujących przejść, które można usunąć z tego stanu, i może dowolnie wybrać, które wybrać. W przeciwieństwie do tego DFA ma tylko jedno pasujące przejście, które można podjąć w tej sytuacji, więc nie ma wyboru - zawsze będzie przechodził to samo przejście, ilekroć jest w tej sytuacji.

DW
źródło

„może dowolnie wybrać, który wybrać”. Więc w zasadzie ma charakter probabilistyczny?

Trilarion

@Trilarion, nie, zależy to od tego, czy prowadzi do akceptacji stanu. W rzeczywistości probabilistyczny FA jest uogólnieniem dla NFA.

rus9384

„Niedeterministyczny” oznacza „niedeterministyczny”, innymi słowy, „jeśli postawisz system dwukrotnie w tej samej sytuacji, może on lub nie dokonać tego samego wyboru za każdym razem”. rozumiesz przez to, że maszyna może zaakceptować i odrzucić ten sam ciąg w dwóch różnych przypadkach.

Madhusoodan P

3

@MadhusoodanP Twoja intuicja jest zgodna z tym, co tu napisano, i to prowadzi nas do tego, czego brakuje w tej odpowiedzi: Analizując NFA, zawsze bierzemy pod uwagę wszystkie możliwe ścieżki wykonania. Tak długo, jak dowolna ścieżka na tym komputerze prowadzi do stanu akceptacji, uważamy dane wejściowe za zaakceptowane. Więc w ogóle nie chodzi o prawdopodobieństwo, chodzi tylko o to, czy można osiągnąć stan akceptacji, czy nie. Ta intuicja staje się jaśniejsza, gdy myślimy o tym, w jaki sposób NFA są redukowane do DFA: Musimy symulować wszystkie możliwe wykonania NFA, co prowadzi do wykładniczego wybuchu w konstrukcji.

ComicSansMS

3

Sposobem na jego wizualizację jest założenie, że tam, gdzie można wybrać wiele przejść, NFA bierze wszystkie przejścia. Tworzysz drzewiastą strukturę wszystkich stanów osiągniętych przez łańcuch wejściowy, a jeśli którakolwiek z gałęzi zakończy się stanem akceptacji, łańcuch zostanie zaakceptowany. Innymi słowy, w przypadku DFA pytasz „ czy stan osiągnięty przez moje wejście jest stanem akceptacji?”, Podczas gdy w przypadku NFA pytasz „czy jakikolwiek stan, który można osiągnąć przez moje wejście, jest stanem akceptacji?”.

Harrison Paine,

9

Weźmy na przykład ten automat, jest to NFA i akceptuje ciąg . Aby być bardziej pedantycznym, akceptuje ciągi, które kończą się na . $0110$ $10$

Aby to sprawdzić, wystarczy sprawdzić, czy osiąga stan akceptacji.

\begin{aligned} q_{0} & \to 1 \\ q_{0} & \to 0 \\ q_{1} & \to 1 \\ q_{2} & \to 0 \end{aligned}

$\begin{align*} q_0 & \rightarrow 1\\ q_0 & \rightarrow 0\\ \color{red}{q_1} &\rightarrow \color{red}{1}\\ q_2 &\rightarrow 0\\ \end{align*}$

Teraz w czerwonej linii istniała inna możliwość, tzn. Podczas czytania drugiego mogłem pozostać w a następnie pozostać w podczas czytania ostatniego . Automaty nie mają pamięci, więc nie ma sposobu, aby „zapisać” stan i sprawdzić później, czy mój ciąg kończy się na , to tak, jak ten NFA, zgaduje, czy ciąg kończy się na przed rozgałęzieniem do akceptowalnego stanu. Niedeterminizm tutaj dokonuje wielu wyborów i zawsze dokonuje właściwych wyborów. $1$ $q_0$ $q_0$ $0$ $10$ $10$

Łatwiej jest zbudować NFA niż zbudować DFA, dobrą rzeczą jest to, że oba są równoważne .

Aristu
źródło

Tak, znam część teoretyczną NFA. Ale pytałem o to, mimo że istnieje wiele przejść dla pojedynczych znaków wejściowych, maszyna jest deterministyczna co do tego, do którego stanu może dojść (powiedzmy, tworząc wątki). Stąd to dosłownie DFA. [Czy uważasz, że źle interpretuję znaczenie determinizmu ]

Madhusoodan P

1

Przykład można ulepszyć nieco bardziej skomplikowanym NFA, ponieważ DFA do tego samego celu użyłby tej samej liczby stanów co NFA i nie byłby szczególnie skomplikowany. Natomiast dopasowanie bardziej skomplikowanego wyrażenia regularnego może wymagać skomplikowanego i bałaganu DFA, ale może być banalne w NFA.

supercat

ε

$\varepsilon$

1

@Aristu Jeśli wdrażasz NFA w swoim ulubionym języku programowania, wątki są okropnym wyborem. Raczej powinieneś po prostu śledzić zestaw stanów, w których automat „może być” po odczytaniu każdego znaku wejściowego. Wynikowy kod będzie prawie tak szybki jak implementacja DFA.

David Richerby,

1

ϵ

$\epsilon$

5

Funkcja przejścia NFA określa dozwolone przejścia w dowolnym momencie. Może istnieć więcej niż jedna opcja, a NFA wybiera przejście niedeterministycznie w celu ostatecznego osiągnięcia stanu akceptacji.

Być może powinieneś poczekać, aż dowiesz się o niedeterministycznych maszynach Turinga. Niedeterminizm oznacza to samo w obu przypadkach.

Yuval Filmus
źródło

czy możesz podkreślić, że „przejście nie jest deterministyczne”? A także proszę przejrzeć moją odpowiedź

Madhusoodan P

Myślę, że obie nasze odpowiedzi nie są super dobre, choć twoja intuicja jest zdrowa.

Yuval Filmus,

3

Zacznij od skończonego automatu. Ma stany i stany akceptacji i przejścia.

Teraz podaj mu więcej niż jedną regułę tras dla każdego stanu i powiedz, że akceptuje, jeśli istnieje zbiór reguł przejścia wybieranych po fakcie, który prowadzi do stanu akceptacji podanego ciągu wejściowego.

Po uzyskaniu łańcucha wejściowego jest ustalony zestaw konkretnych przejść i stanów, przez które przechodzi (jeden po drugim), aby zaakceptować ten ciąg. Ale które przejścia wybiera, wybiera się tylko na końcu łańcucha . Podczas odczytywania ciągu nie jest ustalana ścieżka do wyboru.

Jest niedeterministyczny. Po wskazaniu całego problemu może wybrać ścieżkę przez wykres, a nie podczas odczytu danych wejściowych.

Teraz formalizujemy to inaczej niż ten eksperyment myślowy, ale daje to motywację, dlaczego ma taką nazwę.

To wyjaśnia, w jaki sposób otrzymało nazwę. Tak, możesz modelować NDFA w całkowicie deterministyczny sposób, ale nazwy są lepkie . Gdy zadzwonisz do Boba, zmiana nazwy na coś innego będzie kosztować, ponieważ nikt nie wie, o czym mówisz, gdy nazywasz to Alice.

Jak
źródło

tak! Zgadzam się z twoim wyjaśnieniem na temat NFA. Ale moje pytanie dotyczy tego, dlaczego jest niedeterministyczne, mimo że zbiór stanów jest zdefiniowany dla pojedynczego wejścia

Madhusoodan P

@MadhusoodanP Jest nazywany niedeterministyczne z powodu, jak to zostało wynalezione / przewidywał. A nazwy są lepkie, nawet po zdefiniowaniu wielu deterministycznych sposobów modelowania.

Jak

1

Z wikipedii najlepszym sposobem na przemyślenie tego jest rozpoczęcie od deterministycznych skończonych maszyn stanu (DFA). W przypadku DFA każde przejście jest jednoznacznie określone przez aktualny stan i symbol wejściowy do przetworzenia. Niedeterministyczne maszyny stanów skończonych (NFA) są po prostu tym, co uzyskuje się, rozluźniając tę regułę determinizmu, aby umożliwić unikalne zdefiniowanie przejść. Otrzymujesz to, gdy usuniesz regułę determinisim z DFA.

Cort Ammon
źródło

Jest to nieco bardziej skomplikowane, ponieważ niedeterminizm jest również specyficznym warunkiem akceptacji.

Yuval Filmus,

1

Zarówno NFA, jak i DFA służą (między innymi) do rozpoznawania niektórych ciągów.

Niedeterministyczny automat skończony działa tak, jakby miał wpływ na jego decyzje - może „wybrać” pójście ścieżką lub nie.

Na powyższym obrazku, gdy mamy do czynienia z ciągiem „00111”, zauważ, że napotykając pierwsze „1”, są dwa możliwe sposoby postępowania. Można pozostać przy „p” lub przejść do „q”. Gdyby automaty miały przejść do „q”, nie zaakceptowałoby ciągu (ponieważ nie ma krawędzi wychodzących z „q”). Ale ciąg może zostać zaakceptowany przez te automaty, przechodząc do „q” tylko z ostatnim 1, pozostając przy „p” dla wszystkiego innego (i tak się dzieje).

NFA sprawia, że wygląda na to, że automaty „wiedziały”, co nas czeka, i odpowiednio wybiera.

Oczywiście, że nie. DFA i NFA są równoważne pod względem mocy (możesz zredukować NFA do DFA i uprościć DFA (prawdopodobnie) za pomocą NFA), ale NFA jest przydatny, ponieważ pozwala zdefiniować te same języki co DFA przy jednoczesnym zachowaniu wykresów krótszy i bardziej czytelny.

Nie ma tam nic losowego. Część niedeterministyczna kładzie nacisk na fakt, że istnieje pewien „wybór”, ale prawda jest taka, że automaty nie podejmują żadnych decyzji.

MatthewRock
źródło

0

Oto mieszanka niektórych treści z książki [Wprowadzenie do języków formalnych i automatów Petera Linza 4E] i moje zrozumienie.

Rozważmy program do grania, w którym maszyna musi podjąć decyzję o kolejnym ruchu [powiedzmy na kółko i krzyżyk]. Ponieważ możliwych jest wiele ruchów, deterministycznie wybieramy każdy ruch i oceniamy go i wybieramy najlepszy. Mimo że proces selekcji był deterministyczny i istniało wiele możliwych ruchów, ostatni wykonany ruch był pojedynczy i został wybrany jako najlepszy ruch, ukrywając wszystkie wypróbowane obliczenia ruchów przed przeciwnikiem. [Tutaj zakładamy, że proces oceny każdego możliwego ruchu był ukryty przed przeciwnikiem].

Dlatego dokonano tylko jednego wyboru, a przeciwnik ma złudzenie, że ruch był niedeterministyczny.

Cóż, jeśli nie jesteś jeszcze przekonany pytaniem, że najlepszy ruch był wynikiem pewnych deterministycznych obliczeń, musisz rozważyć maszynę, która wykonuje idealnie losowe ruchy (może to być maszyna tracąca, ale jest to NFA).

Madhusoodan P.
źródło

1

Innym sposobem postawienia tego: przeciwnikowi , twój wybór był niedeterministyczny. Podczas modelowania systemu z perspektywy przeciwnika, twój ruch jest wyborem niedeterministycznym, chyba że przeciwnik odkrył za sobą deterministyczny proces.

reinierpost

@reinierpost dokładnie to, co chciałem powiedzieć

Madhusoodan P

Bardziej interesującym przykładem może być gra polegająca na przenoszeniu elementów o ograniczonej ilości informacji (np. W stylu „gliniarzy i rabusiów”). Jeden gracz przesuwa rabusia po labiryncie, podczas gdy drugi gracz przenosi gliniarzy. W dowolnym momencie, gdy gliniarz zobaczy rabusia, stan rabusia będzie jego lokalizacją, ale w każdym zakręcie, gdy żaden gliniarz nie zobaczy rabusia, rabuś może przejść na dowolne kwadraty, które sąsiadują z jego pozycją i że gliny mogą nie widzę w tym momencie.

supercat

@supercat Fajny, ale dokonane przejście jest zawsze pojedynczym stanem, a jeśli ukryjesz obliczenia najlepszego ruchu, wydaje się to niedeterministyczne

Madhusoodan P

Dlaczego NFA nazywany jest niedeterministyczny?

Odpowiedzi: