Коначан аутомат — разлика између измена

Садржај обрисан Садржај додат
Autobot (разговор | доприноси)
м Bot: Pretvaranje običnih izvora koristeći ref imena da bi se izbjegli duplikati (pogledaj također FAQ); козметичке измене
Autobot (разговор | доприноси)
м Разне исправке
Ред 1:
'''''Коначни (недетерминистички) аутомат''''' над коначном азбуком Σ се састоји од коначног скупа Q, који се назива '''''скуп стања''''', скупа I ⊂ Q '''''почетних (иницијалних)''''' стања, скупа F ⊂ Q '''''завршних (финалних)''''' стања и скупа Δ ⊂ Q x Σ x Q који се назива '''''релација прелаза'''''. Коначни аутомат се записује као уређена петорка:
A=(&Sigma;,Q,I,F,&Delta;).<ref name="automatski generisano1">Душко М. Витас, Преводиоци и интерпретатори, Математички факултет, Београд, 2006.</ref>
Елемент релације прелаза &Delta; се назива ''лук''. Ако је лук l=(p,a,q) &isin; &Delta;, онда је слово a &isin; &Delta; '''''етикета''''' тог лука.<ref name="automatski generisano2">Душко М. Витас, Преводиоци и интерпретатори, Математички факултет, Београд, 2006.</ref>
 
Под '''''израчунавањем''''' c дужине n у аутимату А подразумева се низ лукова l<sub>1</sub>,...,l<sub>n</sub>, где l<sub>i</sub> = (p<sub>i</sub>,a<sub>i</sub>,q<sub>i</sub>) &isin; &Delta;, тако да је q<sub>i</sub> = p<sub>i+1</sub> за i &isin; [1,n-1] &sub; N. Под '''''етикетом''''' израчунавања c, у ознаци ||c|| се подразумева ниска a<sub>1</sub>...a<sub>n</sub> састављена од етикета лукова израчунавања c. Ако је ниска w=||c|| етикета израчунавања c, онда се то записује на следећи начин:
c: p<sub>1</sub> &rarr; q<sub>n</sub>.<ref name="automatski generisano2" />
За свако стање q, постоји, по договору, празно израчунавање у ознаци &epsilon<sub>q</sub> : q &rarr; q чија је етикета &epsilon; (тј. празна реч као етикета).<ref name="automatski generisano2" />
 
За израчунавање c:p &rarr; q се каже да је ''успешно'' ако важи да је p &isin; I и q &isin: F. За реч w се каже да је ''препозната'' (''прихваћена'') аутоматом А ако је та реч етикета неког успешног израчунавања. '''''Језик препознат (прихваћен) аутоматом А''''' је скуп свих речи препознатих аутоматом А:
L(A)={w &isin; &Sigma;* | &exist;c : i &rarr; f, i &isin; I, f &isin; F, w=||c||}.<ref name="automatski generisano2" />
 
Појам израчунавања се може посматрати и на други начин, као проширење релације прелаза &Delta; са слова на речи. Тако '''''проширена релација прелаза''''', у ознаци &Delta;*, описана је на следећи начин:
Ред 17:
- ако је w=a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub> (a<sub>i</sub> &isin; &Sigma;, n &ge; 1) и ако постоји n+1 стање q<sub>0</sub>,q<sub>1</sub>,...,q<sub>n</sub> такво да за свако i &isin; N: 1 &le; i &le; n, важи да је лук (q<sub>i-1</sub>,a<sub>i</sub>,q<sub>i</sub>) &isin; &Delta;, тада је (q<sub>0</sub>,w,q<sub>n</sub>) &isin; &Delta;*, а w je ''етикета'' пута у аутомату која повезује стање q<sub>0</sub> са стањем q<sub>n</sub>.</br>
Језик препознат коначним аутоматом А је тада
L(A)={w &isin; &Sigma;* | &exist;i &isin; I, &exist;f &isin; F, (i,w,f) &isin; &Delta;*}.<ref name="automatski generisano2" />
 
== Граф прелаза коначног аутомата ==
Начин на који се уводи коначан аутомат упућује на графичку репрезентацију коначног аутомата. Таква репрезентација се обично назива ''дијаграм стања'': у њој су стања аутомата представљена чворовима графа, а лук аутомата (p,a,q) је представљен луком из чвора ''p'' ка чвору ''q'' који је обележен етикетом ''a''.
Израчунавање је пут у графу, а обележја лукова који чине један пут у графу, су слова етикете израчунавања.
У графичком приказу аутомата, почетна и завршна стања (елементи скупова I и F) се обележавају на посебан начин. Почетно стање је обележено стрелицом која показује на њега,док је завршно стање двоструко заокружено. Више лукова који имају заједнички излазни чвор ''p'' и заједнички улазни чвор ''q'' обележавају се само једним луком са скупом одговарајућих етикета. Посебно, ако за свако слово a &isin; &Sigma; постоји лук (p,a,q), уводи се јединствени лук са етикетом &Sigma;.<ref name="automatski generisano2" />
 
== Матрица прелаза ==
Опис релације &Delta; се може задати дводимензионом матрицом која се назива '''''матрица прелаза'''''. Врсте матрице прелаза Т су индексиране елементима p скупа стања Q, а колоне елементима a азбуке &Sigma;, тако да:
q &isin; T[p,a] &hArr; (p,a,q) &isin; &Delta;. <ref name="automatski generisano2" />
 
== Детерминистички аутомат ==
Стање q &isin; Q аутомата A=(&Sigma;,Q,I,F,&Delta;) је '''''доступно''''' ако постоји израчунавање c: i &rarr; q, где је i &isin; I. Стање q &isin; Q је '''''судоступно''''' ако постоји израчунавање c: q &rarr; f где је f &isin; F. Ако су сва стањаједног аутомата доступна, кажемо да је аутомат '''''доступан''''', а ако су сва стања аутомата доступна и судоступна, кажемо да је аутомат '''''скресан'''''.<ref name="automatski generisano2" />
 
Коначни аутомат А=(&Sigma;,Q,I,F,&Delta;) је '''''детерминистички''''' ако скуп I почетних стања има тачно један елемент и ако важи
Ред 42:
&forall;p &isin; Q, &forall;w &isin; &Sigma;, &delta;*(p,wa)=&delta;(&delta;*(p,w),a).
У овој нотацији, ако је I={i}, језик препознат детерминистичким коначним аутоматом А је:
L(A)={w &isin; &Sigma;* | &delta;*(i,w)&isin; F}.<ref name="automatski generisano1" />
Коначни аутомат А=(&Sigma;,Q,I,F,&Delta;) je '''''стандардан''''' ако је I={i} &sube; Q и ако
за свако a &isin; &Sigma;, q &isin; Q, (q,a,i) &notin; &Delta;
(тј. у почетном стању се не завршава ниједан лук аутомата).<ref name="automatski generisano1" />
 
Коначни аутомат А=(&Sigma;,Q,I,F,&Delta;) je '''''потпун(комплетан)''''' ако за свако стање p &isin; Q и свако слово a &isin; &Sigma;, постоји бар једно стање q &isin; Q такво да је (p,a,q) &isin; &Delta;.
Ако неки коначан аутомат А није потпун, онда се такав аутомат може допунити до потпуног аутомата који препознаје исти језик као и аутомат А. Поступак '''''комплетирања''''' се састоји у увођењу новог стања w &isin; Q, таквог да w &notin; F. Тада, за сваки пар (p,a) за који не постоји ниједно q &isin; Q такво да је (p,a,q) &isin; &Delta; додајемо лук (p,a,w), (w,a,w) &isin; &Delta; за свако a &isin; &Sigma;.<ref name="automatski generisano2" /></br>
Сваки коначан аутомат се може трансформисати у детерминистички коначни аутомат, што показује следећа:</br>
'''Теорема.''' ''За сваки коначан аутомат А, постоји потпун детерминистички коначан аутомат B такав да је''</br>
L(A)=L(B).<ref name="automatski generisano2" />
 
== Види још ==