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