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

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.

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 k 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 N jest rozmiarem NFA) .$N$$N$

$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.

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.

$\epsilon$

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$

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.

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