1. DFA: DFA odnosi się do deterministycznego automatu skończonego. Mówi się, że automat skończony (FA) jest deterministyczny, jeśli odpowiada symbolowi wejściowemu i istnieje jeden stan wypadkowy, tj. istnieje tylko jedno przejście. Deterministyczny automat skończony to zbiór pięciu krotek reprezentowanych jako:
Gdzie,
P: Niepusty, skończony zbiór stanów w skończonym sterowaniu (qo, q1, q2, …).
Σ: Niepusty, skończony zbiór symboli wejściowych.
δ: Jest to funkcja przejścia, która przyjmuje dwa argumenty, stan i symbol wejściowy, zwraca pojedynczy stan.
qo: Jest to stan początkowy, jeden ze stanów w Q.
F: Jest to niepusty zbiór stanów końcowych/akceptujący stany ze zbioru należącego do Q.
2. PRZYCZYNY:
NFA odnosi się do niedeterministycznego automatu skończonego. Mówi się, że automat skończony (FA) jest niedeterministyczny, jeśli istnieje więcej niż jedno możliwe przejście z jednego stanu na tym samym symbolu wejściowym.
Niedeterministyczny automat skończony jest również zbiorem pięciu krotek i jest reprezentowany jako:
Gdzie,
P: Zbiór niepustych stanów skończonych.
Σ: Zbiór niepustych, skończonych symboli wejściowych.
δ: Jest to funkcja przejścia, która pobiera stan z Q i symbol wejściowy z i zwraca podzbiór Q.
qo: Stan początkowy NFA i członek Q.
F: Niepusty zbiór stanów końcowych i element Q.
Warunek wstępny – Zakończono automatycznie
Różnica między DFA i NFA:
| DFA | NFA |
|---|---|
| DFA oznacza deterministyczne automaty skończone. | NFA oznacza niedeterministyczne automaty skończone. |
| Dla każdej symbolicznej reprezentacji alfabetu istnieje tylko jedno przejście stanu w DFA. | Nie ma potrzeby określać, jak NFA reaguje według jakiegoś symbolu. |
| DFA nie może używać przejścia z pustym ciągiem. | NFA może używać przejścia z pustym ciągiem. |
| DFA można rozumieć jako jedną maszynę. | NFA można rozumieć jako wiele małych maszyn pracujących jednocześnie. |
| W DFA następny możliwy stan jest wyraźnie ustawiony. | W NFA każda para stanu i symbolu wejściowego może mieć wiele możliwych kolejnych stanów. |
| DFA jest trudniejsze do skonstruowania. | NFA jest łatwiejszy do skonstruowania. |
| DFA odrzuca ciąg znaków, jeśli kończy się on w stanie innym niż stan akceptujący. | NFA odrzuca ciąg w przypadku, gdy wszystkie gałęzie umierają lub odrzucają ciąg. |
| Czas potrzebny na wykonanie ciągu wejściowego jest krótszy. | Czas potrzebny na wykonanie ciągu wejściowego jest dłuższy. |
| Wszystkie DFA są NFA. | Nie wszystkie NFA to DFA. |
| DFA wymaga więcej miejsca. | NFA wymaga mniej miejsca niż DFA. |
| Martwa konfiguracja jest niedozwolona. np.: jeśli podajemy dane wejściowe jako 0 w stanie q0, musimy podać 1 jako dane wejściowe dla q0 jako pętla własna. | Dozwolona jest martwa konfiguracja. np.: jeśli podamy stan q0 na wejściu jako 0, to będziemy mogli podać kolejne wejście na q1, które przejdzie do następnego stanu. |
| δ: QxΣ -> Q, czyli następny możliwy stan należy do Q. | δ: Qx(Σ U ε) -> 2^Q tj. następny możliwy stan należy do zbioru potęg Q. |
| Wycofywanie jest dozwolone w DFA. | Wycofywanie się nie zawsze jest możliwe w NFA. |
| Konwersja wyrażenia regularnego na DFA jest trudna. | Konwersja wyrażeń regularnych na NFA jest prostsza w porównaniu do DFA. |
| Ruch Epsilon nie jest dozwolony w DFA | Ruch Epsilon jest dozwolony w NFA |
| DFA pozwala tylko na jeden ruch dla pojedynczego alfabetu wejściowego. | Można wybrać (więcej niż jeden ruch) alfabetu z pojedynczym wprowadzeniem. |