Коначан аутомат
From Wikipedia, the free encyclopedia
Коначни (недетерминистички) аутомат над коначном азбуком Σ се састоји од коначног скупа 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, постоји, по договору, празно израчунавање у ознаци ε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=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]