Коначан аутомат — разлика између измена
Садржај обрисан Садржај додат
м Бот: уклоњен шаблон: Link GA |
Нема описа измене |
||
Ред 1:
'''''Коначни (недетерминистички) аутомат''''' над коначном азбуком Σ се састоји од коначног скупа Q, који се назива '''''скуп стања''''', скупа I ⊂ Q '''''почетних (иницијалних)''''' стања, скупа F ⊂ Q '''''завршних (финалних)''''' стања и скупа Δ ⊂ Q x Σ x Q који се назива '''''релација прелаза'''''. Коначни аутомат се записује као уређена петорка:
A=(Σ,Q,I,F,Δ).
Елемент релације прелаза Δ се назива ''лук''. Ако је лук l=(p,a,q) ∈ Δ, онда је слово a ∈ Δ '''''етикета''''' тог лука.
Под '''''израчунавањем''''' c дужине n у аутимату А подразумева се низ лукова l<sub>1</sub>,...,l<sub>n</sub>, где l<sub>i</sub> = (p<sub>i</sub>,a<sub>i</sub>,q<sub>i</sub>) ∈ Δ, тако да је q<sub>i</sub> = p<sub>i+1</sub> за i ∈ [1,n-1] ⊂ N. Под '''''етикетом''''' израчунавања c, у ознаци ||c|| се подразумева ниска a<sub>1</sub>...a<sub>n</sub> састављена од етикета лукова израчунавања c. Ако је ниска w=||c|| етикета израчунавања c, онда се то записује на следећи начин:
c: p<sub>1</sub> → q<sub>n</sub>.
За свако стање q, постоји, по договору, празно израчунавање у ознаци &epsilon<sub>q</sub> : q → q чија је етикета ε (тј. празна реч као етикета).
За израчунавање c:p → q се каже да је ''успешно'' ако важи да је p ∈ I и q &isin: F. За реч w се каже да је ''препозната'' (''прихваћена'') аутоматом А ако је та реч етикета неког успешног израчунавања. '''''Језик препознат (прихваћен) аутоматом А''''' је скуп свих речи препознатих аутоматом А:
L(A)={w ∈ Σ* | ∃c : i → f, i ∈ I, f ∈ F, w=||c||}.
Појам израчунавања се може посматрати и на други начин, као проширење релације прелаза Δ са слова на речи. Тако '''''проширена релација прелаза''''', у ознаци Δ*, описана је на следећи начин:
Δ* ⊆ Q x Σ* x Q
уз услове:</br>
- за свако q ∈ Q, (q,ε,q) ∈ Δ*;</br>
- ако је w=a<sub>1</sub>a<sub>2</sub>...a<sub>n</sub> (a<sub>i</sub> ∈ Σ, n ≥ 1) и ако постоји n+1 стање q<sub>0</sub>,q<sub>1</sub>,...,q<sub>n</sub> такво да за свако i ∈ N: 1 ≤ i ≤ n, важи да је лук (q<sub>i-1</sub>,a<sub>i</sub>,q<sub>i</sub>) ∈ Δ, тада је (q<sub>0</sub>,w,q<sub>n</sub>) ∈ Δ*, а w je ''етикета'' пута у аутомату која повезује стање q<sub>0</sub> са стањем q<sub>n</sub>.</br>
Језик препознат коначним аутоматом А је тада
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 ∈ Σ.</br>
Сваки коначан аутомат се може трансформисати у детерминистички коначни аутомат, што показује следећа:</br>
'''Теорема.''' ''За сваки коначан аутомат А, постоји потпун детерминистички коначан аутомат B такав да је''</br>
L(A)=L(B).
== Види још ==
| |||