NFA i DFA

NFA a DFA

Teoria obliczeń jest gałęzią informatyki, która zajmuje się rozwiązywaniem problemów za pomocą algorytmów. Ma trzy gałęzie, a mianowicie; teoria złożoności obliczeniowej, teoria obliczalności i teoria automatu.

Teoria automatów lub automatów jest nauką abstrakcyjnych maszyn lub systemów matematycznych, które mogą być używane do rozwiązywania problemów obliczeniowych. Automat składa się ze stanów i przejść, a gdy widzi symbol lub literę wejścia, przechodzi do innego stanu, przyjmując bieżący stan i symbol jako dane wejściowe.

Teoria automatu lub automatu ma kilka klas, które obejmują Deterministyczne Automaty Finalne (DFA) i Niedeterministyczne Automaty Skończone (NFA). Te dwie klasy są przejściowymi funkcjami automatów lub automatów.

Podczas przejścia DFA nie może użyć n pustego ciągu i może być rozumiany jako jeden komputer. Jeśli ciąg kończy się w stanie, który nie jest dopuszczalny, usługa DFA go odrzuci. Maszyna DFA może być zbudowana z każdym wejściem i wyjściem.

DFA zawiera tylko jedno przejście stanu dla każdego symbolu alfabetu i istnieje tylko jeden stan końcowy dla jego przejścia, co oznacza, że ​​dla każdego odczytywanego znaku istnieje jeden odpowiedni stan w DFA. Łatwiej jest sprawdzić członkostwo w DFA, ale jest trudniej je skonstruować. Powracanie w DFA jest dozwolone i wymaga więcej miejsca niż NFA.

Wycofywanie nie zawsze jest dozwolone w NFA. Choć jest to możliwe w niektórych przypadkach, w innych nie. Łatwiej jest skonstruować NFA, a także wymaga to mniej miejsca, ale nie jest możliwe zbudowanie maszyny NFA dla każdego wejścia i wyjścia.

Jest to rozumiane jako kilka maleńkich maszyn, które obliczają jednocześnie, a członkostwo może być trudniejsze do sprawdzenia. Używa Pustego Przejścia Ciągów i istnieje wiele możliwych kolejnych stanów dla każdej pary stanu i symbolu wejściowego. Zaczyna się w określonym stanie i odczytuje symbole, a następnie automat określa następny stan, który zależy od bieżącego wejścia i innych wypadkowych zdarzeń. W stanie akceptującym NFA akceptuje ciąg znaków i odrzuca go w inny sposób.

Streszczenie:

1. "DFA" oznacza "Deterministic Finite Automata", a "NFA" oznacza "niedeterministyczne Finite Automata". 2. Zwykle są to funkcje przejściowe automatów. W DFA kolejny możliwy stan jest wyraźnie ustawiony, podczas gdy w NFA każda para stanu i symbolu wejściowego może mieć wiele możliwych następnych stanów. 3.NFA może używać pustego ciągu znaków, podczas gdy DFA nie może używać pustego przejścia tekstowego. 4.NFA jest łatwiejsza do zbudowania, podczas gdy trudniej jest skonstruować DFA. 5. Prześladowanie jest dozwolone w DFA, podczas gdy w NFA może być dozwolone lub nie. 6.DFA wymaga więcej miejsca, podczas gdy NFA wymaga mniej miejsca. 7.Dlaczego DFA może być rozumiane jako jedna maszyna, a maszyna DFA może być zbudowana dla każdego wejścia i wyjścia, 8.NFA może być rozumiana jako kilka małych maszyn, które są obliczane razem, i nie ma możliwości skonstruowania maszyny NFA dla każdego wejścia i wyjście.