Детерминистички коначни аутомат

У теорији израчунљивости, детерминистички коначни аутомат (ДКА) је коначни аутомат у којем за сваки пар стања и улазног знака постоји један и само један пријелаз у сљедеће стање. Детерминистички коначни аутомати препознају скуп регуларних језика.

ДКА прима низ улазних знакова, и за сваки улазни знак обавља пријелаз у стање које одређује функција пријелаза. Када је прочитан цијели улазни низ, прихватит ће или одбити низ знакова овисно о томе је ли ДКА у прихватљивом или неприхватљивом стању.

ДКА се формално дефинира уређеном петорком, ${\displaystyle \left(Q,\Sigma ,\delta ,q_{0},F\right)}$, која се састоји од

• коначног скупа стања (${\displaystyle Q}$)
• коначног скупа улазних знакова званог улазна абецеда (${\displaystyle \Sigma }$)
• функције пријелаза (${\displaystyle \delta :Q\times \Sigma \rightarrow Q}$)
• почетног (иницијалног) стања (${\displaystyle q_{0}\in Q}$)
• скупа прихватљивих стања (${\displaystyle F\subseteq Q}$)

Нека је M ДКА такав да M = ${\displaystyle \left(Q,\Sigma ,\delta ,q_{0},F\right)}$, и ${\displaystyle X=x_{0}x_{1}...x_{n}}$ низ знакова над абецедом ${\displaystyle \Sigma }$. M прихваћа низ знакова ${\displaystyle X}$ ако слијед стања ${\displaystyle r_{0},r_{1},...,r_{n}}$, постоји у ${\displaystyle Q}$ уз сљедеће увјете:

1. ${\displaystyle r_{0}=q_{0}}$
2. ${\displaystyle r_{i+1}=\delta (r_{i},x_{i})}$ за ${\displaystyle i=0,...,n-1}$
3. ${\displaystyle r_{n}\in F}$

Као што је показано у првом увјету, строј започиње рад у почетном стању с. Други увјет каже да ће за сваки знак улазног низа X строј прећи из тренутног стања у стање управљано функцијом пријелаза ${\displaystyle \delta }$. Посљедњи увјет каже да строј прихваћа улазни низ ако посљедњи знак улазног низа X узрокује пријелаз у једно од прихватљивих стања. Иначе кажемо да строј не прихваћа (одбија) улазни низ. Скуп низова знакова које ДКА прихваћа је облик формалног језика, и представља облик језика којег ДКА препознаје.

Слиједи примјер ДКА M над бинарном абецедом који одређује садржи ли улазни низ паран број знаменки 0.

M = ${\displaystyle \left(Q,\Sigma ,\delta ,q_{0},F\right)}$ гдје је

• ${\displaystyle Q=\left\{{S_{1},S_{2}}\right\}}$
• ${\displaystyle \Sigma =\left\{{0,1}\right\}}$
• ${\displaystyle q_{0}=S_{1}}$
• ${\displaystyle F=\left\{{S_{1}}\right\}}$, те
• ${\displaystyle \delta }$ је дефинирана сљедећом таблицом пријелаза:

	0	1
С1	С2	С1
С2	С1	С2

Кратко речено, стање С₁ представља догађај да се у улазном низу досад појавио паран број знаменки 0, док стање С₂ представља догађај да се појавио непаран број. Знаменка 1 у улазном низу не мијења стање аутомата. Када се заврши читање улазног низа, тренутно стање ће показати да ли је улазни низ садржавао паран број знаменки 0 или не.

Језик ДКА M је регуларни језик описан сљедећим регуларним изразом:

${\displaystyle (1^{*}01^{*}01^{*})^{*}\,\!}$

ДКАи су једни од најпрактичнијих модела израчунљивости, с обзиром да постоји тривијалан онлине алгоритам који их симулира у линеарном времену и константном простору над током улазних симбола. За два дана ДКАа постоје учинковити алгоритми за проналажење ДКА који препознаје унију, пресјек те комплемент језика које они препознају. Такођер постоје учинковити алгоритми за одређивање да ли ДКА прихваћа било који низ знакова, да ли ДКА прихваћа све низове знакова, да ли два ДКА прихваћају исти језик, те за проналажење ДКА са минималним бројем стања за задани језик.

ДКАи су модели израчунљивости једнаке моћи као НКАи (недетерминистички коначни аутомати).

У другу руку, ДКАи су строго ограничене моћи над језицима које могу препознати — многи једноставни језици, укључујући било који проблем чије рјешење захтијева више него константан простор, не могу бити препознати од стране ДКА. Канонски примјер језика којег ниједан ДКА не може препознати јест језик који се састоји од низова знакова облика а^нб^н — коначан број знакова а након којег слиједи једнаки број знакова б. Може се показати да ниједан ДКА не може имати довољан број стања да препозна такав језик.