Конечен автомат

Конечен автомат — апстрактна машина која претставува модел на однесување составен од конечен број на состојби, преодни состојби и дејства. Во една состојба се зачувува информација за претходната, т.е го прикажува влезните промени од почетокот до моменталната состојба. Преодот всушност е промена на една состојба во друга и е опишана од услов што треба да биде исполнет за да се изврши преодот. Под дејство се подразбира функција на системот што треба да ја изврши во дадениот момент. Постојат повеќе видови на дејства:

• Влезно дејство: Се изведува кога влегуваме во состојба
• Излезно дејство: Се изведува кога се излегува од состојба
• Вносно дејство: Се изведува во зависност од моменталната сосојба и правилата на влез
• Преодно дејство: Се изведува при преминување од една во друга состојба

За да се прикаже еден конечен автомат може да се претстави со дијаграм или табели. Најчесто се прикажува како примерот подолу комбинација од моменталната сосотојба (B) и условот (Y) ја покажува следната состојба (C).

Освен нивната примена во реактивни системи искористени за да се објаснат конечните автомати тие се искористени и наоѓаат голема примена и во електроинжинерството, лингвистиката, информатиката, филозофија, билологија, математика. Во информатиката конечните автомати наоѓаат огромна примена во однесување на програмите, дизајн на хардверски дигитални системи, софтвер, компајлери, мрежни протоколи, и во науката за програмските јазици.

Прифаќачи и препознавачи (секвенцијални детектори) даваат бинарен излез, односно одговор ДА или НЕ во зависност од тоа дали влезот е прифатен од машината или не. Сите состојби на автоматот се или прифатливи или неприфатливи. Доколку по завршувањето на влезот автоматот се наоѓа во прифатлива состојба тогаш се прифаќа влезот во спротивно се одбива.Како правило влезот се состои од симболи (знаци); дејства не се користат. Примерот 2 покажува конечен автомат што го пригаќа зборот "nice", во овој автомат има само една прифатлива состојба , а тоа е состојбата број 7. Машината исто така може да означува дефиниран јазик кој ќе ги соодржи сите зборови кои поминале низ прифатливата состојба,додека оние одбиените нема; и велиме дека јазикот е прифатен од машината. По дефиниција јазиците прифатени од конечниот автомат се наречени регуларни изрази, односно јазикот е регуларен ако е прифатен од конечен автомат (Теорема на Клини).

Почетна состојба Почетната состојба обично се означува со стрелка која покажува накај неа

Прифатлива состојба Оваа состојба обично се означува со двојно заокружување,а означува дека зборот е прифатен, односно дека дејството е успешно завршено. Примеров покажува детерминистички конечен автомат (ДКА) што на излез прифака зборови со еднаков број на 0 во нив,може да се забележи дека почетната состојба S1 воедно е и крајна.

Математички модел

Во зависност од типот постојат повеќе дефиниции. Автоматот кој прифака конечна состојба $M$, каде:

$M=(Q,\Sigma ,q_{0},\delta ,F)\!\,$

• $Q\,\!$ е конечно, но не и празно множество од состојби.
• $\Sigma \,\!$ е влезната азбука (конечно, но не и празно множество од симболи).
• $q_{0}\in S$ е почетна состојба која припаѓа на Q. Во недетерминистичките конечни автомати (НКА), $s_{0}$ е множество од почетни состојби.
• $\delta :Q\times \Sigma \rightarrow Q$ е множество од преминувачки состојби.
• $F\subseteq Q$ е множество од конечни состојби, подмножество на Q (може да биде и празно).

Примери

1. Да се конструира конечен детерминистички автомат кој ќе ги прифаќа зборовите што го содржат подстрингот abab.
   
2. Да се конструира конечен недетерминистички автомат кој ќе ги прифаќа сите стрингови кои ги содржат само подстринговите ab ,aba 0 или повеќепати.
   
3. Да се конструира конечен недетерминистички автомат кој ќе ги препознава стринговите 0101,101,011,а потоа да се трансформира во конечен детерминистички автомат.