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

Коначни (недетерминистички) аутомат над коначном азбуком Σ се састоји од коначног скупа 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: p1 → qn.[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]

Види још

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