- Do rozpoznawania wzorców służą automaty skończone.
- Jako dane wejściowe pobiera ciąg symboli i odpowiednio zmienia swój stan. Po znalezieniu żądanego symbolu następuje przejście.
- W momencie przejścia automaty mogą albo przejść do następnego stanu, albo pozostać w tym samym stanie.
- Automaty skończone mają dwa stany, Zaakceptuj stan Lub Stan odrzucenia . Kiedy ciąg wejściowy zostanie pomyślnie przetworzony, a automaty osiągną swój stan końcowy, zaakceptują.
Formalna definicja FA
Automat skończony to zbiór 5-krotek (Q, ∑, δ, q0, F), gdzie:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Model automatu skończonego:
Automaty skończone można przedstawić za pomocą taśmy wejściowej i skończonej kontroli.
Taśma wejściowa: Jest to taśma liniowa posiadająca pewną liczbę komórek. Każdy symbol wejściowy jest umieszczany w każdej komórce.
Kontrola skończona: Sterowanie skończone decyduje o następnym stanie po odebraniu określonego sygnału wejściowego z taśmy wejściowej. Czytnik taśmy odczytuje komórki jedna po drugiej od lewej do prawej i jednocześnie odczytywany jest tylko jeden symbol wejściowy.
Rodzaje automatów:
Istnieją dwa rodzaje automatów skończonych:
- DFA(deterministyczne automaty skończone)
- NFA (niedeterministyczne automaty skończone)
1. DFA
DFA odnosi się do deterministycznych automatów skończonych. Determinizm odnosi się do niepowtarzalności obliczeń. W DFA maszyna przechodzi do jednego stanu tylko dla określonego znaku wejściowego. DFA nie akceptuje ruchu zerowego.
2. NFA
NFA oznacza niedeterministyczne automaty skończone. Służy do przesyłania dowolnej liczby stanów dla danego wejścia. Może zaakceptować ruch zerowy.
Kilka ważnych punktów na temat DFA i NFA:
- Każde DFA to NFA, ale NFA to nie DFA.
- Może istnieć wiele stanów końcowych zarówno w NFA, jak i DFA.
- DFA jest używany w analizie leksykalnej w kompilatorze.
- NFA to bardziej koncepcja teoretyczna.