• Кінцевий автомат використовується для розпізнавання шаблонів.
• Скінченний автомат приймає рядок символів як вхідні дані та відповідно змінює свій стан. У вхідних даних, коли потрібний символ знайдено, відбувається перехід.
• Під час переходу автомати можуть переходити до наступного стану або залишатися в тому самому стані.
• FA має два стани: стан прийняття або стан відхилення. Коли вхідний рядок буде успішно оброблено і автомат досягне свого кінцевого стану, він прийме.

Скінченний автомат складається з:

Q: кінцева множина станів
∑: кінцева множина вхідних символів
q0: початковий стан
F: кінцевий стан
d: функція переходу

Функцію переходу можна визначити як

 δ: Q x ∑ →Q  

ФА характеризується двома способами:

1. DFA (кінцеві автомати)
2. NDFA (недетерміновані кінцеві автомати)

DFA

DFA означає Deterministic Finite Automata. Детермінований стосується унікальності обчислення. У DFA вхідний символ переходить лише в один стан. DFA не приймає нульове переміщення, що означає, що DFA не може змінити стан без жодного введеного символу.

DFA має п’ять кортежів {Q, ∑, q0, F, δ}

приклад

Дивіться приклад детермінованих кінцевих автоматів:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3}  

НДФА

NDFA відноситься до недетермінованих кінцевих автоматів. Він використовується для проходження будь-якої кількості станів для певного входу. NDFA приймає переміщення NULL, що означає, що він може змінювати стан без читання символів.

NDFA також має п’ять станів, як і DFA. Але NDFA має іншу функцію переходу.

Перехідну функцію NDFA можна визначити як:

приклад

Дивіться приклад недетермінованих кінцевих автоматів:

 Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q3}