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

Из Википедије, слободне енциклопедије
(преусмерено са Машина коначних стања)

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

     A=(Σ,Q,I,F,Δ).[1]

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

Под израчунавањем c дужине n у аутимату А подразумева се низ лукова l1,...,ln, где li = (pi,ai,qi) ∈ Δ, тако да је qi = pi+1 за i ∈ [1,n-1] ⊂ N. Под етикетом израчунавања c, у ознаци ||c|| се подразумева ниска a1...an састављена од етикета лукова израчунавања c. Ако је ниска w=||c|| етикета израчунавања c, онда се то записује на следећи начин:

      c: p1 → qn.[2]

За свако стање q, постоји, по договору, празно израчунавање у ознаци &epsilonq : q → q чија је етикета ε (тј. празна реч као етикета).[2]

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

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

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

     Δ* ⊆ Q x Σ* x Q

уз услове:
- за свако q ∈ Q, (q,ε,q) ∈ Δ*;
- ако је w=a1a2...an (ai ∈ Σ, n ≥ 1) и ако постоји n+1 стање q0,q1,...,qn такво да за свако i ∈ N: 1 ≤ i ≤ n, важи да је лук (qi-1,ai,qi) ∈ Δ, тада је (q0,w,qn) ∈ Δ*, а w je етикета пута у аутомату која повезује стање q0 са стањем qn.
Језик препознат коначним аутоматом А је тада

     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]

Види још[уреди]

Референце[уреди]

  1. 1,0 1,1 1,2 Душко М. Витас, Преводиоци и интерпретатори, Математички факултет, Београд, 2006.
  2. 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 2,8 2,9 Душко М. Витас, Преводиоци и интерпретатори, Математички факултет, Београд, 2006.

Спољашње везе[уреди]

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.


Напомене и референце[уреди]