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

Од Википедија, слободна енциклопедија

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

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

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

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

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

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

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

Слика:avtomat1.jpg

[уреди] Математички модел

Во зависност од типот постојат повеќе дефиниции. Автоматот кој прифака конечна состојба (Σ,S,s0,δ,F), каде:

  • Σ е влезната азбука (конечно,но не и празно множество од симболи).
  • S е конечно,но не и празно множество од состојби
  • s0 е почетна состојба која припаѓа на S . Во недетерминистичките конечни автомати (НКА), s0 е множество од почетни состојби.
  • δ е множество од преминувачки состојби: .
  • F е множество од конечни состојби, подмножество на S (може да биде и празно).

Примери

1.Да се конструира конечен детерминистички автомат кој ќе ги прифаќа зборовите што го содржат подстрингот abab. Слика:avtomat2.jpg


2. Да се конструира конечен недетерминистички автомат кој ќе ги прифаќа сите стрингови кои ги содржат само подстринговите ab ,aba 0 или повеќе пати.

Слика:tabela1.jpg Слика:avtomat3.jpg


3. Да се конструира конечен недетерминистички автомат кој ќе ги препознава стринговите 0101,101,011,а потоа да се трансформира во конечен детерминистички автомат.

Слика:avtomat4.jpg

Слика:tabela2.jpg

Слика:avtomat5.jpg