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

Формальне визначення FA

Скінченний автомат – це сукупність 5-ти (Q, ∑, δ, q0, F), де:

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function 

Модель кінцевих автоматів:

Скінченні автомати можуть бути представлені вхідною стрічкою та кінцевим керуванням.

Вхідна стрічка: Це лінійна стрічка, що має деяку кількість осередків. Кожен вхідний символ розміщується в кожній клітинці.

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

Типи автоматів:

Існує два типи кінцевих автоматів:

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

1. DFA

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

2. НФА

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

Деякі важливі моменти щодо DFA та NFA:

1. Кожен DFA є NFA, але NFA не є DFA.
2. У NFA і DFA може бути кілька кінцевих станів.
3. DFA використовується в лексичному аналізі в компіляторі.
4. NFA – це більше теоретична концепція.