Wikipedija

Deterministički konačni automat: razlika između inačica

Pregledaj povijest
← Starija izmjenaNovija izmjena →
Izbrisani sadržaj Dodani sadržaj
VizualnoWikitekst
m + predložak tablice Chomskyjeve hijerarhije
konverzija u LaTeX + Ullman/Srbljić znakovlje
Redak 1:
U [[teorija izračunljivosti|teoriji izračunljivosti]], '''deterministički konačni automat''' (DKA) je [[konačni automat]] u kojem za svaki par stanja i ulaznog znaka postoji jedan i samo jedan prijelaz u sljedeće stanje. DKAiDeterministički konačni automati prepoznaju skup [[regularni jezik|regularnih jezika]].
 
DKA prima niz ulaznih znakova, i za svaki ulazni znak obavlja prijelaz u stanje koje određuje funkcija prijelaza. Kada je pročitan cijeli ulazni niz, prihvatit će ili odbiti niz znakova ovisno o tome je li DKA u prihvatljivom ili neprihvatljivom stanju.
Redak 5:
==Formalna definicija==
 
DKA se formalno definira uređenom petorkom, <math>\left(''S'' Q, &\Sigma;, ''T''\delta, ''s''q_0, ''A''F \right)</math>, koja se sastoji od
* konačnog skupa stanja (''S''<math>Q</math>)
* konačnog skupa ulaznih znakova zvanog ''ulazna [[abeceda (računarstvo)|abeceda]]'' (&<math>\Sigma;</math>)
* funkcije prijelaza (''T''<math>\delta : ''S''Q &\times; &\Sigma; &rarr;\rightarrow ''S''Q</math>)
* početnog (inicijalnog) stanja (''s''<math>q_0 &isin;\in ''S''Q </math>)
* skupa prihvatljivih stanja (''A''<math>F &sube;\subseteq ''S''Q</math>)
 
Neka je '''M''' DKA takav da '''M''' = <math>\left(''S'' Q, &\Sigma;, ''T''\delta, ''s''q_0, ''A''F \right)</math>, i ''<math>X = x<sub>0</sub>x<sub>1</sub>x_0x_1 ... x<sub>nx_n</submath>'' niz znakova nad abecedom &<math>\Sigma;</math>. '''M''' prihvaća niz znakova ''<math>X''</math> ako slijed stanja ''r<sub>0</submath>r_0 ,r<sub>1</sub>r_1 , ..., r<sub>nr_n</submath>'', postoji u ''S''<math>Q</math> uz sljedeće uvjete:
 
# ''r<submath>0</sub>''r_0 = ''s''q_0</math>
# ''r<submath>r_{i + 1</sub>''} = ''T''\delta (''r<sub>i</sub>''r_i ,x_i ''x<sub>i)</submath>''), forza ''<math>i'' = ''0, ..., n - 1''</math>
# <math>r_n \in F</math>
# ''r<sub>n</sub>'' &isin; ''A''.
 
Kao što je pokazano u prvom uvjetu, stroj započinje rad u početnom stanju ''s''.
Drugi uvjet kaže da će za svaki znak ulaznog niza ''X'' stroj preći iz trenutnog stanja u stanje upravljano funkcijom prijelaza ''T''<math>\delta</math>.
Posljednji uvjet kaže da stroj prihvaća ulazni niz ako posljednji znak ulaznog niza ''X'' uzrokuje prijelaz u jedno od prihvatljivih stanja. Inače kažemo da stroj ne prihvaća (odbija) ulazni niz. Skup nizova znakova koje DKA prihvaća je oblik [[formalni jezik|formalnog jezika]], i predstavlja oblik jezika kojeg DKA prepoznaje.
 
Redak 27:
 
[[Slika:DFAexample.svg|right|frame|[[dijagram stanja]] za ''M'']]
''M'' = <math>\left(''S'' Q, &\Sigma;, ''T''\delta, ''s''q_0, ''A''F \right)</math> gdje je
*<math>Q = \left\{ {S_1 ,S_2 } \right\}</math>
*''S'' = {''S''<sub>1</sub>, ''S''<sub>2</sub>},
*&<math>\Sigma; = \left\{ {0, 1}, \right\}</math>
*''s''<math>q_0 = ''S''<sub>1S_1</submath>,
*''A''<math>F = \left\{''S''<sub>1 {S_1 } \right\}</submath>}, andte
*''T''<math>\delta</math> je definirandefinirana sljedećom [[tablica prijelaza|tablicom prijelaza]]:
:{| border="0" cellpadding="1"
| || <center>'''0'''</center> || <center>'''1'''</center>
Dobavljeno iz "https://hr.wikipedia.org/wiki/Deterministički_konačni_automat"