Czy możemy powiedzieć, że DFA jest bardziej wydajny niż NFA?

13

Właśnie zacząłem czytać o teorii obliczeń. Jeśli porównamy, który ma większą moc (w przyjmowaniu ciągów), oba są takie same. Ale co z wydajnością? DFA będzie szybki w porównaniu do NFA, ponieważ ma tylko jedną przewagę wychodzącą i nie będzie dwuznaczności. Ale w przypadku NFA musimy sprawdzić wszystkie możliwe przypadki i to z pewnością wymaga czasu. Czy możemy więc powiedzieć, że DFA jest bardziej wydajny niż NFA?

Ale moja druga część mózgu również myśli, że NFA istnieje tylko w teorii, więc nie możemy porównać jego wydajności z DFA.

finite-automata efficiency nondeterminism avi
źródło

16

Istnieją dwie odpowiedzi, w zależności od sposobu definiowania wydajności.

Zwartość reprezentacji

Mówiąc więcej za mniej : NFA są bardziej wydajne.

Konwersja DFA na NFA jest prosta i nie zwiększa rozmiaru reprezentacji.

Istnieją jednak zwykłe języki, dla których najmniejszy DFA jest wykładniczo większy niż najmniejszy NFA. Typowym przykładem jest dla stałej. $(a|b)^*b(a|b)^k$ $k$

Obliczenie

Szybkie działanie : DFA są bardziej wydajne.

Komputery, których używamy dzisiaj, mają charakter deterministyczny. To czyni ich złymi w radzeniu sobie z niedeterminizmem. Istnieją dwa typowe sposoby deterministycznego traktowania NFA: cofanie się po jednej stronie, co jest dość kosztowne, lub śledzenie stanów aktywnych, co oznacza, że każde przejście zajmie razy dłużej (gdzie jest rozmiarem NFA) . $N$ $N$

Khaur
źródło

Jeśli chodzi o zwartość, NFA nie zawsze są bardziej wydajne! To prawda, że istnieją języki, dla których minimalna DFA jest wykładniczo większa niż najbardziej kompaktowa NFA, ale jaka jest część takich języków w zestawie wszystkich języków?

saadtaame

2

@saadtaame To może wydawać się dziwne, ale w najściślejszym sensie, NFA nie muszą być niedeterministyczne. DFA to specjalny rodzaj NFA, tj. NFA z singletonem jako zestawem początkowym, a funkcja przejścia jest taka, że tylko jeden stan jest aktywny w danym momencie.

Khaur

2

O (N)

$O(N)$

O (2^{N})

$O(2^N)$

O (N)

$O(N)$

Dziękuję za tę odpowiedź, ponieważ w moich badaniach argumentowałem, że NFA są lepsze do oceny i teraz widzę, że sprawa jest bardziej subtelna. Ogólnie rzecz biorąc, NFA są zdecydowanie lepsze dla ustalonego języka, ponieważ każdy inteligentny algorytm oceny NFA będzie pasował do złożoności oceny DFA w szczególnym przypadku, że NFA jest DFA, i ponieważ NFA może być bardziej zwięzły. Jeśli jednak wybór polega na wytworzeniu wysoce niedeterministycznego NFA lub znalezieniu sprytnego sposobu uzyskania DFA o tej samej wielkości , to w przypadku niektórych zastosowań DFA jest lepszy.

6005

4

$n$ $2^n$

Dopasowywanie DFA jest liniowe pod względem wielkości ciągu wejściowego. Dopasowywanie NFA obejmuje cofanie, więc NFA wykonują więcej pracy. Dzięki temu DFA są bardziej wydajne.

saadtaame
źródło

Ale czy możemy powiedzieć, że DFA jest bardziej wydajny?

avi

1

@avi Zredagowałem pytanie! Nawiasem

saadtaame

@avi Problem polega na tym, że DFA, który jest równoważny NFA, będzie (często) znacznie większy. Więc nawet jeśli możesz sprawdzić DFA znacznie szybciej, zwykle będziesz musiał sprawdzić większy DFA.

Peter

@Peter, że DFA jest większy, nie ma znaczenia: oznacza to po prostu, że tablica dająca funkcję przejścia jest większa.

vonbrand

1

@ Khaur, prawda. Ale jeśli wpadniesz w tego rodzaju problem, masz ogromny DFA.

vonbrand

2

Właśnie dodając do powyższych odpowiedzi:

NFA mogą być obliczeniowo wydajniejsze niż DFA, w tym sensie, że można je symulować na równoległym procesorze.

BTW: Widzę ludzi mówiących, że NFA nie mogą istnieć w rzeczywistości. Pozwolę sobie być innego zdania. Komputer z dużą liczbą procesorów może wykonywać wiele zadań równolegle i może być uważany za maszynę niedeterministyczną. Można przypisać każdą gałąź obliczeń do nowego procesora i zatrzymać je wszystkie, gdy tylko jedno z nich zaakceptuje.

Nieuprawny
źródło

1

W rzeczywistości nie istnieją ani DFA, ani NFA, oba są jedynie relacjami matematycznymi i oba mogą być symulowane za pomocą algorytmów.

jmite

1

$\epsilon$

vonbrand
źródło

ϵ

$\epsilon$

1

ϵ

$\epsilon$

ale czy DFA nie jest wolne od przejść trans?

avi

@avi, tak. Edytuj odpowiedź, jeśli nie jest tam jasna.

vonbrand

nie, pytam cię Nie jestem tego pewien

avi

1

Jak zauważyli inni, musisz zdefiniować, co oznacza „wydajność”. Aby to zilustrować, podaję rozsądny model z inną odpowiedzią.

Patrząc tylko na modele automatów, które ignorują w szczególności sposób ich implementacji na rzeczywistych maszynach, oczywistym miernikiem wydajności jest „liczba przejść wykonanych w (najkrótszym) przebiegu akceptującym”.

$\varepsilon$

Raphael
źródło

1

Technicznie rzecz biorąc, NFA jest bardziej ogólną koncepcją niż DFA, ponieważ nie jest wymagane stosowanie niedeterminizmu. Innymi słowy: każdy DFA jest NFA. Z tej perspektywy dla każdego języka istnieje NFA, który jest co najmniej tak samo wydajny, jak najbardziej wydajny DFA, niezależnie od tego, jaki preferujesz miernik wydajności.

Poza tym zgadzam się z Raphaelem, że bardzo zależy od tego, co masz na myśli pod względem wydajności i wdrożenia.

A.Schulz
źródło

-4

Jak wiemy o automatach, tj. Maszynie, która może wykonywać dowolne czynności bez żadnej siły ludzkiej lub bez bezpośredniego udziału człowieka. np .: pralka. Automaty skończone oznaczają, że znamy stan wykonywania zadania przez maszynę, np. 1 naciśnij WŁ. 2 naciśnij WYŁ., Więc istnieją tylko 2 stany, tj. Zwane automatami skończonymi. Teraz przejdź do DFA, czyli deterministycznych automatów skończonych. formalnie oznacza to, że możemy łatwo określić stany, w których nie ma dwuznaczności i nieformalnie potrzeba tylko 1 przejścia na 1 symbol. NFA: niedeterministyczne automaty skończone. potrzeba więcej czasu na obliczenie stanu rzeczywistego i niejednoznaczność, a nieformalnie mówi, że istnieje wiele dozwolonych przejść na 1 symbol. w przypadku czasu dotarcia do miejsca docelowego NFA zajmuje więcej czasu niż DFA, ale NFA może załadować więcej danych niż DFA. * DFA i NFA mają taką samą moc rozpoznawania ciągu. dziękuję .. Deepali kaushik

deepali kaushik
źródło

1

Automaty skończone nie mają nic wspólnego z pralkami.

David Richerby

2

@DavidRicherby. Być może wyrażenie „nic” jest trochę mocne. W końcu możemy powiedzieć, że pralka ma gotowe stany , myje , płucze i wiruje z odpowiednimi przejściami między stanami. Lepszą metaforą byłby jednak automat z napojami na monety.

Rick Decker

1

@RickDecker Zgodził się, ale poświęcanie czasu na omawianie drobiazgów byłoby przykładem tego, co Wikipedia nazywa „ nadmierną wagą ”. W każdym razie część odpowiedzi, o której mówię, dotyczy automatów jako maszyn samozasilających się, a nie urządzeń obliczeniowych.

David Richerby

1

Nie sądzę, aby ta odpowiedź dodała coś wartościowego do pytania. W szczególności nie jesteś pewien swojej wydajności i wydajesz się mieszać kilka obaw.

Raphael

Inne odpowiedzi prawie wyczerpują wszystko, co trzeba powiedzieć, i niestety twoja odpowiedź jest nieco myląca.

Zły

Czy możemy powiedzieć, że DFA jest bardziej wydajny niż NFA?

Odpowiedzi:

Zwartość reprezentacji

Obliczenie