铜川深度打造“互联网+检察”“两法衔接”平台

百度 　　然而，各地在线办事程度发展并不平衡。

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

     A=(Σ,Q,I,F,Δ).

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

Под израчунава?ем 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.

За свако ста?е q, посто?и, по договору, празно израчунава?е у ознаци ε_q : q → q чи?а ?е етикета ε (т?. празна реч као етикета).

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

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

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

     Δ* ⊆ 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) ∈ Δ*}.

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

Начин на ко?и се уводи коначан аутомат упу?у?е на графичку репрезентаци?у коначног аутомата. Таква репрезентаци?а се обично назива ди?аграм ста?а: у ?о? су ста?а аутомата представ?ена чворовима графа, а лук аутомата (p,a,q) ?е представ?ен луком из чвора p ка чвору q ко?и ?е обележен етикетом a. Израчунава?е ?е пут у графу, а обележ?а лукова ко?и чине ?едан пут у графу, су слова етикете израчунава?а. У графичком приказу аутомата, почетна и завршна ста?а (елементи скупова I и F) се обележава?у на посебан начин. Почетно ста?е ?е обележено стрелицом ко?а показу?е на ?ега,док ?е завршно ста?е двоструко заокружено. Више лукова ко?и има?у за?еднички излазни чвор p и за?еднички улазни чвор q обележава?у се само ?едним луком са скупом одговара?у?их етикета. Посебно, ако за свако слово a ∈ Σ посто?и лук (p,a,q), уводи се ?единствени лук са етикетом Σ.

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

Опис релаци?е Δ се може задати дводимензионом матрицом ко?а се назива матрица прелаза. Врсте матрице прелаза Т су индексиране елементима p скупа ста?а Q, а колоне елементима a азбуке Σ, тако да:

     q ∈ T[p,a] ⇔ (p,a,q) ∈ Δ.

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

Ста?е q ∈ Q аутомата A=(Σ,Q,I,F,Δ) ?е доступно ако посто?и израчунава?е c: i → q, где ?е i ∈ I. Ста?е q ∈ Q ?е судоступно ако посто?и израчунава?е c: q → f где ?е f ∈ F. Ако су сва ста?а?едног аутомата доступна, кажемо да ?е аутомат доступан, а ако су сва ста?а аутомата доступна и судоступна, кажемо да ?е аутомат скресан.

Коначни аутомат А=(Σ,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}.
     

Коначни аутомат А=(Σ,Q,I,F,Δ) je стандардан ако ?е I={i} ⊆ Q и ако

     за свако a ∈ Σ, q ∈ Q, (q,a,i) ∉ Δ

(т?. у почетном ста?у се не завршава ни?едан лук аутомата).

Коначни аутомат А=(Σ,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 ∈ Σ.
Сваки коначан аутомат се може трансформисати у детерминистички коначни аутомат, што показу?е следе?а:
Теорема. За сваки коначан аутомат А, посто?и потпун детерминистички коначан аутомат B такав да ?е

      L(A)=L(B).

Види ?ош

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