- Maszyna skończona służy do rozpoznawania wzorców.
- Automat skończony przyjmuje ciąg symboli jako dane wejściowe i odpowiednio zmienia swój stan. Na wejściu, gdy zostanie znaleziony żądany symbol, następuje przejście.
- Podczas przejścia automaty mogą albo przejść do następnego stanu, albo pozostać w tym samym stanie.
- FA ma dwa stany: stan akceptacji lub stan odrzucenia. Kiedy ciąg wejściowy zostanie pomyślnie przetworzony, a automaty osiągną swój stan końcowy, zaakceptują.
Automat skończony składa się z:
P: skończony zbiór stanów
∑: skończony zbiór symboli wejściowych
q0: stan początkowy
F: stan końcowy
d: Funkcja przejścia
Funkcję przejścia można zdefiniować jako
δ: Q x ∑ →Q
FA charakteryzuje się na dwa sposoby:
- DFA (automaty skończone)
- NDFA (niedeterministyczne automaty skończone)
DFA
DFA oznacza deterministyczne automaty skończone. Determinizm odnosi się do niepowtarzalności obliczeń. W DFA znak wejściowy przechodzi tylko do jednego stanu. DFA nie akceptuje ruchu zerowego, co oznacza, że DFA nie może zmienić stanu bez wprowadzenia żadnego znaku wejściowego.
DFA ma pięć krotek {Q, ∑, q0, F, δ}
P: zbiór wszystkich stanów∑: skończony zbiór symboli wejściowych gdzie δ: Q x ∑ →Q
q0: stan początkowy
F: stan końcowy
d: Funkcja przejścia
Przykład
Zobacz przykład deterministycznych automatów skończonych:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 
NDFA
NDFA odnosi się do niedeterministycznych automatów skończonych. Służy do tranzytu dowolnej liczby stanów dla określonego wejścia. NDFA akceptuje ruch NULL, co oznacza, że może zmienić stan bez czytania symboli.
NDFA ma również pięć stanów, takich samych jak DFA. Ale NDFA ma inną funkcję przejścia.
Funkcję przejścia NDFA można zdefiniować jako:
d: Q x ∑ →2QPrzykład
Zobacz przykład niedeterministycznych automatów skończonych:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3} 