- Крайните автомати се използват за разпознаване на модели.
- Той приема низа от символи като вход и съответно променя състоянието си. Когато се намери желаният символ, тогава се извършва преходът.
- По време на прехода автоматите могат или да преминат към следващото състояние, или да останат в същото състояние.
- Крайните автомати имат две състояния, Приемете състояние или Състояние на отхвърляне . Когато входният низ се обработи успешно и автоматът достигне крайното си състояние, тогава той ще приеме.
Официално определение на ФА
Краен автомат е набор от 5-кортеж (Q, ∑, δ, q0, F), където:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Модел на крайни автомати:
Крайните автомати могат да бъдат представени чрез входна лента и крайно управление.
Входна лента: Това е линейна лента с определен брой клетки. Всеки входен символ се поставя във всяка клетка.
Краен контрол: Крайният контрол решава следващото състояние при получаване на конкретен вход от входна лента. Четецът на лента чете клетките една по една отляво надясно и наведнъж се чете само един входен символ.
Видове автомати:
Има два вида крайни автомати:
- DFA (детерминистични крайни автомати)
- NFA (недетерминирани крайни автомати)
1. DFA
DFA се отнася до детерминирани крайни автомати. Детерминистичното се отнася до уникалността на изчислението. В DFA машината преминава в едно състояние само за определен входен знак. DFA не приема нулевия ход.
2. НФА
NFA означава недетерминирани крайни автомати. Използва се за предаване на произволен брой състояния за определен вход. Може да приеме нулевия ход.
Някои важни точки относно DFA и NFA:
- Всеки DFA е NFA, но NFA не е DFA.
- Може да има множество крайни състояния както в NFA, така и в DFA.
- DFA се използва в лексикален анализ в компилатора.
- NFA е по-скоро теоретична концепция.