DFA, NFA i epsilon NFA wszystkie trzy pozwalają nam reprezentować konkretny język. Za pomocą dowolnej z tych reprezentacji możemy dojść do tego samego wyrażenia regularnego, dlaczego więc musimy studiować wszystkie trzy formy reprezentacji automatów skończonych? Można wyjaśnić, co NFA może zrobić, czego DFA nie może zrobić, to znaczy, że NFA może nam pomóc w projektowaniu niepewności. Na przykład przy projektowaniu gry (szachy) mamy wiele opcji przeniesienia określonego elementu z określonego miejsca, które można łatwo przedstawić za pomocą NFA. Ale jaki jest pożytek z epsilon NFA, gdy można to zrobić przy użyciu NFA lub DFA?
automata
finite-automata
education
Bharat Banavalikar
źródło
źródło
Odpowiedzi:
Dodaj regularne gramatyki dla czwartej. Są inni...
Częścią zainteresowania DFA + NFA jest to, że są to proste modele obliczeniowe, z przykładami niedeterminizmu NFA (i -NFA) (kluczowy pomysł na bardziej rozbudowane modele). Aby udowodnić, że DFA i NFA akceptują ten sam zestaw języków, badamy również bardzo ważne zjawisko w prostym, zrozumiałym otoczeniu.ϵ
Wyrażenia regularne (a także gramatyka regularna) to zupełnie inne formalizmy, które opisują ten sam zestaw języków. Ponownie dowód tego faktu bada ważne wzajemne relacje i jest przykładem, że formalizm może wyglądać bardzo różnie, opierać się na radykalnie odmiennych koncepcjach, ale opisywać te same języki. Znów w dość prostym ustawieniu.
Do użytku w „świecie rzeczywistym” możesz zacząć od wyrażenia regularnego i uzyskać minimalną liczbę DFA do wyszukiwania o wysokiej wydajności. Obwody cyfrowe są zasadniczo DFA, ich zrozumienie jest kluczowe w inżynierii komputerowej. Wreszcie, często systemy można modelować jako „bycie w stanie” i „przechodzenie do innego” na bodźcach zewnętrznych, nawet jeśli system jest bardzo daleki od prawdziwego DFA oglądanie go w ten sposób może pomóc w jego zrozumieniu.
Dodano później: Jak zauważył Raphael, bardziej efektywna może być interpretacja NFA bezpośrednio podczas wyszukiwania, ponieważ utworzenie DFA może być kosztowne, a NFA może być znacznie mniejszy.
źródło
istnieje wiele różnych powodów badania różnych form / korespondencji DFA w porównaniu z NFA. Oto kilka wybranych wyróżnień, niektóre z zaawansowanej teorii złożoności.
NFA są interesującym modelem dla „obliczeń równoległych”. postępy stanów za pośrednictwem NFA można uznać za równoległą wersję obliczeń DFA. więc obliczenia DFA vs. NFA odzwierciedlają niektóre różnice między obliczeniami sekwencyjnymi a równoległymi. porównując oba konteksty, pomaga także badać złożoność algorytmiczną problemów.
NFA są często używane w systemach dopasowywania wyrażeń regularnych (dość wszechobecne w różnych językach, zwłaszcza współczesnych pojawiających się w erze Uniksa), które zazwyczaj umożliwiają opisy wyrażeń regularnych, które są konwertowane na NFA, a następnie ewentualnie na DFA, aby pomóc w bardziej wydajnym wyszukiwaniu.
istnieje wiele otwartych problemów, które pozostają w tych obszarach i często są badane na podstawie korespondencji DFA / NFA. patrz np. czy pozostały jakieś otwarte problemy na DFA (cstheory stackexchange). nieco zadziwiające, niektóre z nich są związane z bardzo głębokimi obszarami CS, w tym problemem P vs NP, tj. nieuprzejmością przecięcia DFA . także innym otwartym obszarem jest np. obliczanie minimalnego NFA dla DFA .
także dla niektórych powiązanych wglądów zobacz to pytanie półgłówne / wysoko ocenione na cstheory.se : Jakie oświecenie powinienem osiągnąć po przestudiowaniu automatów skończonych?
istnieją bardzo różnorodne zastosowania DFA w porównaniu z NFA i często wykorzystuje się w nich korespondencję między nimi. dopasowanie wzorca struny jest wspomniane powyżej, ale konstrukcje DFA / NFA są często używane w (automatycznym) rozpoznawaniu mowy. patrz np. ten cytowany artykuł: Ważone przetworniki skończone w rozpoznawaniu mowy / Mohri, Pereira, Riley
źródło
DFA ma łatwiejszą implementację niż NFA, ponieważ ich następny stan jest określany przez funkcję, a NFA pomagają użytkownikowi w łatwym wyrażeniu tego, co chcą jako dane wyjściowe, ponieważ NFA może wybierać spośród wielu ścieżek. a epsilon-NFA jest rozszerzeniem NFA, w którym przejścia można wykonywać bez pobierania jakichkolwiek symboli wejściowych.
źródło
Paskudna jest liczba stanów DFA. Czasami wybucha .
Krótko mówiąc, jeśli liczba stanów jest po prostu zbyt wysoka (wciąż skończona, ale żyjemy w świecie fizycznym), musisz zwiększyć poziom abstrakcji, aby poradzić sobie ze złożonością kosztem pewnego spowolnienia. Inne modele, takie jak NFA i AFA, mają zapewnić bardziej zwięzłe sposoby reprezentowania zwykłych języków.
źródło