Коначан аутомат

Коначни (недетерминистички) аутомат над коначном азбуком Σしぐま се састоји од коначног скупа Q, који се назива скуп стања, скупа I ⊂ Q почетних (иницијалних) стања, скупа F ⊂ Q завршних (финалних) стања и скупа Δでるた ⊂ Q x Σしぐま x Q који се назива релација прелаза. Коначни аутомат се записује као уређена петорка:

     A=(Σしぐま,Q,I,F,Δでるた).^[1]

Елемент релације прелаза Δでるた се назива лук. Ако је лук l=(p,a,q) ∈ Δでるた, онда је слово a ∈ Δでるた етикета тог лука.^[2]

Под израчунавањем c дужине n у аутомату А подразумева се низ лукова l₁,...,l_n, где l_i = (p_i,a_i,q_i) ∈ Δでるた, тако да је q_i = p_i+1 за i ∈ [1,n-1] ⊂ N. Под етикетом израчунавања c, у ознаци ||c|| се подразумева ниска a₁...a_n састављена од етикета лукова израчунавања c. Ако је ниска w=||c|| етикета израчунавања c, онда се то записује на следећи начин:

      c: p₁ → q_n.^[2]

За свако стање q, постоји, по договору, празно израчунавање у ознаци εいぷしろん_q : q → q чија је етикета εいぷしろん (тј. празна реч као етикета).^[2]

За израчунавање c:p → q се каже да је успешно ако важи да је p ∈ I и q ∈ F. За реч w се каже да је препозната (прихваћена) аутоматом А ако је та реч етикета неког успешног израчунавања. Језик препознат (прихваћен) аутоматом А је скуп свих речи препознатих аутоматом А:

      L(A)={w ∈ Σしぐま* | ∃c : i → f, i ∈ I, f ∈ F, w=||c||}.^[2]

Појам израчунавања се може посматрати и на други начин, као проширење релације прелаза Δでるた са слова на речи. Тако проширена релација прелаза, у ознаци Δでるた*, описана је на следећи начин:

     Δでるた* ⊆ Q x Σしぐま* x Q

уз услове:
- за свако q ∈ Q, (q,εいぷしろん,q) ∈ Δでるた*;
- ако је w=a₁a₂...a_n (a_i ∈ Σしぐま, n ≥ 1) и ако постоји n+1 стање q₀,q₁,...,q_n такво да за свако i ∈ N: 1 ≤ i ≤ n, важи да је лук (q_i-1,a_i,q_i) ∈ Δでるた, тада је (q₀,w,q_n) ∈ Δでるた*, а w je етикета пута у аутомату која повезује стање q₀ са стањем q_n.
Језик препознат коначним аутоматом А је тада

     L(A)={w ∈ Σしぐま* | ∃i ∈ I, ∃f ∈ F, (i,w,f) ∈ Δでるた*}.^[2]

Граф прелаза коначног аутомата

Начин на који се уводи коначан аутомат упућује на графичку репрезентацију коначног аутомата. Таква репрезентација се обично назива дијаграм стања: у њој су стања аутомата представљена чворовима графа, а лук аутомата (p,a,q) је представљен луком из чвора p ка чвору q који је обележен етикетом a. Израчунавање је пут у графу, а обележја лукова који чине један пут у графу, су слова етикете израчунавања. У графичком приказу аутомата, почетна и завршна стања (елементи скупова I и F) се обележавају на посебан начин. Почетно стање је обележено стрелицом која показује на њега,док је завршно стање двоструко заокружено. Више лукова који имају заједнички излазни чвор p и заједнички улазни чвор q обележавају се само једним луком са скупом одговарајућих етикета. Посебно, ако за свако слово a ∈ Σしぐま постоји лук (p,a,q), уводи се јединствени лук са етикетом Σしぐま.^[2]

Матрица прелаза

Опис релације Δでるた се може задати дводимензионом матрицом која се назива матрица прелаза. Врсте матрице прелаза Т су индексиране елементима p скупа стања Q, а колоне елементима a азбуке Σしぐま, тако да:

     q ∈ T[p,a] ⇔ (p,a,q) ∈ Δでるた.^[2]

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

Стање q ∈ Q аутомата A=(Σしぐま,Q,I,F,Δでるた) је доступно ако постоји израчунавање c: i → q, где је i ∈ I. Стање q ∈ Q је судоступно ако постоји израчунавање c: q → f где је f ∈ F. Ако су сва стањаједног аутомата доступна, кажемо да је аутомат доступан, а ако су сва стања аутомата доступна и судоступна, кажемо да је аутомат скресан.^[2]

Коначни аутомат А=(Σしぐま,Q,I,F,Δでるた) је детерминистички ако скуп I почетних стања има тачно један елемент и ако важи

     (p,a,q),(p,a,r) ∈ Δでるた ⇒ q = r.

Дакле, за свако стање p ∈ Q и свако a ∈ Σしぐま, постоји највише једно стање q ∈ Q такво да важи (p,a,q) ∈ Δでるた. Према овој дефиницији, релација преласка се своди на парцијално пресликавање

     δでるた: Q x Σしぐま → Q

које тада називамо функција прелаза детерминистичког коначног аутомата. Функција прелаза се природно проширује у функцију δでるた* над речима из Σしぐま*:

     δでるた* : Q x Σしぐま* → Q

на следећи начин:

                ∀p ∈ Q, δでるた*(p,εいぷしろん)=p
     ∀p ∈ Q, ∀w ∈ Σしぐま, δでるた*(p,wa)=δでるた(δでるた*(p,w),a).

У овој нотацији, ако је I={i}, језик препознат детерминистичким коначним аутоматом А је:

     L(A)={w ∈ Σしぐま* | δでるた*(i,w)∈ F}.^[1]

Коначни аутомат А=(Σしぐま,Q,I,F,Δでるた) je стандардан ако је I={i} ⊆ Q и ако

     за свако a ∈ Σしぐま, q ∈ Q, (q,a,i) ∉ Δでるた

(тј. у почетном стању се не завршава ниједан лук аутомата).^[1]

Коначни аутомат А=(Σしぐま,Q,I,F,Δでるた) je потпун(комплетан) ако за свако стање p ∈ Q и свако слово a ∈ Σしぐま, постоји бар једно стање q ∈ Q такво да је (p,a,q) ∈ Δでるた. Ако неки коначан аутомат А није потпун, онда се такав аутомат може допунити до потпуног аутомата који препознаје исти језик као и аутомат А. Поступак комплетирања се састоји у увођењу новог стања w ∈ Q, таквог да w ∉ F. Тада, за сваки пар (p,a) за који не постоји ниједно q ∈ Q такво да је (p,a,q) ∈ Δでるた додајемо лук (p,a,w), (w,a,w) ∈ Δでるた за свако a ∈ Σしぐま.^[2]
Сваки коначан аутомат се може трансформисати у детерминистички коначни аутомат, што показује следећа:
Теорема. За сваки коначан аутомат А, постоји потпун детерминистички коначан аутомат B такав да је

      L(A)=L(B).^[2]

Види још

Референце

^ ^а ^б ^в Душко М. Витас, Преводиоци и интерпретатори, Математички факултет, Београд, 2006.
^ ^а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и Душко М. Витас, Преводиоци и интерпретатори, Математички факултет, Београд, 2006.

Спољашње везе

Напомене и референце

[automatski_generisano1-1] а ^б ^в Душко М. Витас, Преводиоци и интерпретатори, Математички факултет, Београд, 2006.

[automatski_generisano2-2] а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и Душко М. Витас, Преводиоци и интерпретатори, Математички факултет, Београд, 2006.

[1]

[2]