Теорија аутомата

У теоретском рачунарству, теорија аутомата је дисциплина која се бави проучавањем апстрактних машина и проблема које они могу решити. Теорија аутомата је уско повезана са теоријом формалних језика, с обзиром да су сами аутомати често класификовани класом формалних језика које могу препознати.

Основни опис

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

Улаз се чита знак по знак, све док није у потпуности прочитан (ово можемо представити као траку са написаном речи коју чита глава за читање аутомата; глава се помиче надесно читајући један по један знак). Једном кад је улазна реч у целости прочитана, кажемо да аутомат стаје.

Зависно од стања у којем се аутомат налази у тренутку стајања, кажемо да аутомат или прихвата или не прихвата (одбија) улазну реч. Уколико је стао у прихватљивом стању, тада аутомат прихвата реч. Иначе се налази у неприхватљивом стању и реч је одбијена. Скуп свих речи које аутомат прихвата зовемо језик који аутомат прихвата.

Формални опис

Дефиниције

За почетак дефинишемо неке основне концепте универзалне за све класе аутомата:

Знак (симбол)

Арбитрарна ознака која има неко значење или утиче на рад машине.

Реч

Коначни низ знакова (стринг) обликован надовезивањем (конкатенацијом) неког броја знакова.

Абецеда

Коначан скуп знакова.

Језик

Скуп речи, обликован знаковима у датој абецеди. Може али не мора бити бесконачан.

Аутомат

формално, аутомат је представљен уређеном петорком $\langle Q,\Sigma ,\delta ,q_{0},F\rangle$ гдје је:

• Q је коначан скуп стања.
• ∑ је коначан скуп знакова, којег зовемо абецеда језика којег аутомат прихвата.
• δ је функција прелаза:

$\delta :Q\times \Sigma \rightarrow Q.$

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

${\hat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q.$

...где је ∑^* Клеенеов оператор примењен над скупом ∑.

Дефиниција δ је нешто сложенија за недетерминистичке и неконачне аутомате.

• q₀ је почетно (иницијално) стање, тј. стање у којем се аутомат налази у тренутку кад још ниједан знак није обрађен (Очигледно је q₀∈ Q).
• Ф је подскуп скупа стања Q (тј. Ф⊆Q), којег зовемо скуп прихватљивих стања

Узимајући у обзир ове дефиниције, можемо сад рећи да језик $L$ којег прихвата детерминистички коначни аутомат $M=\langle Q,\Sigma ,\delta ,q_{0},F\rangle$ је:

$L=\{w\in \Sigma ^{\star }|{\hat {\delta }}(q_{0},w)\in F\}$

Тј. скуп свих речи w над абецедом $\Sigma$, које дате као улаз аутомата M ће га натерати да се заустави у неком од стања из скупа Ф.

Класе аутомата

Три су основне врсте коначних аутомата:

Детерминистички коначни аутомат (ДКА)

Свако стање овог аутомата има дефинисан прелаз за сваки знак улазне абецеде.

Недетерминистички коначни аутомат (НКА)

Стања овог аутомата не морају имати дефинисан прелаз за сваки знак улазне абецеде, или могу имати дефинисан прелаз у скуп стања. Другим речима, функција прелаза дефинише прелаз у скуп стања који може бити празан. Аутомат прихвата реч уколико постоји барем један след прелаза из почетног стања С₀ у неко од стања у скупу Ф лабелирано са улазном речи. Ако је прелаз недефинисан, на начин да аутомат не зна како да настави да чита улазни низ знакова, реч се одбија.

Недетерминистички коначни аутомат са ε-прелазима (ε-НКА)

Осим што могу скочити у једно или више стања за било који улазни знак, ови аутомати могу скочити не читајући ниједан улазни знак. Тј. ако стање има прелаз означен са $\epsilon$, тада НКА може бити у било којем од стања достижних са $\epsilon$-пријелазима, било непосредно било посредно преко других стања са дефинисаним $\epsilon$-прелазима. Скуп свих стања достижних на овај начин из стања q се зове $\epsilon$-окружење од q.

Може се формално показати да све три врсте аутомата могу прихватити исти језик и у том смислу представљају истоветне моделе израчунљивости, једнаке експресивне моћи. За сваки НКА M може бити конструисан ДКА M' који прихвата исти језик.

Проширења коначних аутомата

Фамилија језика које прихватају горе описани аутомати се зове фамилија регуларних језика. Моћнији аутомати могу прихватити сложеније класе језика. Такви аутомати су:

Потисни аутомати (ПА)

Таква машина је идентична са ДКА (односно НКА), осим што је опремљена и са меморијом у облику (потисног) стога. Функција прелаза $\delta$ такође зависи од знака на врху стога, те одређује начин на који ће садржај стога бити измењен за сваки прелаз. ПАи прихватају класу контекстно независних језика.

Линеарно ограничен аутомат (ЛОА)

ЛОА је ограничена верзија Турингове машине; уместо бесконачне траке, трака има доступно простора пропорционално дужини улазне речи. ЛОАи прихватју контекстно зависне језике.

Тјурингове машине

Ово су најмоћније рачунарске машине. Поседују бесконачну меморију у облику траке, и главу која може читати и писати по траци, и помицати се у оба смера дуж траке. Турингове машине су као модел израчунљивости еквивалентни алгоритмима, и представљају теоретску основу модерних рачунара. Турингове машине одлучују рекурзивне језике и препознају рекурзивно пребројиве језике.