Konačan automat

Konačni (nedeterministički) automat nad konačnom azbukom Σ se sastoji od konačnog skupa Q, koji se naziva skup stanja, skupa I ⊂ Q početnih (inicijalnih) stanja, skupa F ⊂ Q završnih (finalnih) stanja i skupa Δ ⊂ Q x Σ x Q koji se naziva relacija prelaza. Konačni automat se zapisuje kao uređena petorka:

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

Element relacije prelaza Δ se naziva luk. Ako je luk l=(p,a,q) ∈ Δ, onda je slovo a ∈ Δ etiketa tog luka.^[2]

Pod izračunavanjem c dužine n u automatu A podrazumeva se niz lukova l₁,...,l_n, gde l_i = (p_i,a_i,q_i) ∈ Δ, tako da je q_i = p_i+1 za i ∈ [1,n-1] ⊂ N. Pod etiketom izračunavanja c, u oznaci ||c|| se podrazumeva niska a₁...a_n sastavljena od etiketa lukova izračunavanja c. Ako je niska w=||c|| etiketa izračunavanja c, onda se to zapisuje na sledeći način:

      c: p₁ → q_n.^[2]

Za svako stanje q, postoji, po dogovoru, prazno izračunavanje u oznaci ε_q : q → q čija je etiketa ε (tj. prazna reč kao etiketa).^[2]

Za izračunavanje c:p → q se kaže da je uspešno ako važi da je p ∈ I i q ∈ F. Za reč w se kaže da je prepoznata (prihvaćena) automatom A ako je ta reč etiketa nekog uspešnog izračunavanja. Jezik prepoznat (prihvaćen) automatom A je skup svih reči prepoznatih automatom A:

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

Pojam izračunavanja se može posmatrati i na drugi način, kao proširenje relacije prelaza Δ sa slova na reči. Tako proširena relacija prelaza, u oznaci Δ*, opisana je na sledeći način:

     Δ* ⊆ Q x Σ* x Q

uz uslove:
- za svako q ∈ Q, (q,ε,q) ∈ Δ*;
- ako je w=a₁a₂...a_n (a_i ∈ Σ, n ≥ 1) i ako postoji n+1 stanje q₀,q₁,...,q_n takvo da za svako i ∈ N: 1 ≤ i ≤ n, važi da je luk (q_i-1,a_i,q_i) ∈ Δ, tada je (q₀,w,q_n) ∈ Δ*, a w je etiketa puta u automatu koja povezuje stanje q₀ sa stanjem q_n.
Jezik prepoznat konačnim automatom A je tada

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

Graf prelaza konačnog automata

Način na koji se uvodi konačan automat upućuje na grafičku reprezentaciju konačnog automata. Takva reprezentacija se obično naziva dijagram stanja: u njoj su stanja automata predstavljena čvorovima grafa, a luk automata (p,a,q) je predstavljen lukom iz čvora p ka čvoru q koji je obeležen etiketom a. Izračunavanje je put u grafu, a obeležja lukova koji čine jedan put u grafu, su slova etikete izračunavanja. U grafičkom prikazu automata, početna i završna stanja (elementi skupova I i F) se obeležavaju na poseban način. Početno stanje je obeleženo strelicom koja pokazuje na njega,dok je završno stanje dvostruko zaokruženo. Više lukova koji imaju zajednički izlazni čvor p i zajednički ulazni čvor q obeležavaju se samo jednim lukom sa skupom odgovarajućih etiketa. Posebno, ako za svako slovo a ∈ Σ postoji luk (p,a,q), uvodi se jedinstveni luk sa etiketom Σ.^[2]

Matrica prelaza

Opis relacije Δ se može zadati dvodimenzionom matricom koja se naziva matrica prelaza. Vrste matrice prelaza T su indeksirane elementima p skupa stanja Q, a kolone elementima a azbuke Σ, tako da:

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

Deterministički automat

Stanje q ∈ Q automata A=(Σ,Q,I,F,Δ) je dostupno ako postoji izračunavanje c: i → q, gde je i ∈ I. Stanje q ∈ Q je sudostupno ako postoji izračunavanje c: q → f gde je f ∈ F. Ako su sva stanjajednog automata dostupna, kažemo da je automat dostupan, a ako su sva stanja automata dostupna i sudostupna, kažemo da je automat skresan.^[2]

Konačni automat A=(Σ,Q,I,F,Δ) je deterministički ako skup I početnih stanja ima tačno jedan element i ako važi

     (p,a,q),(p,a,r) ∈ Δ ⇒ q = r.

Dakle, za svako stanje p ∈ Q i svako a ∈ Σ, postoji najviše jedno stanje q ∈ Q takvo da važi (p,a,q) ∈ Δ. Prema ovoj definiciji, relacija prelaska se svodi na parcijalno preslikavanje

     δ: Q x Σ → Q

koje tada nazivamo funkcija prelaza determinističkog konačnog automata. Funkcija prelaza se prirodno proširuje u funkciju δ* nad rečima iz Σ*:

     δ* : Q x Σ* → Q

na sledeći način:

                ∀p ∈ Q, δ*(p,ε)=p
     ∀p ∈ Q, ∀w ∈ Σ, δ*(p,wa)=δ(δ*(p,w),a).

U ovoj notaciji, ako je I={i}, jezik prepoznat determinističkim konačnim automatom A je:

     L(A)={w ∈ Σ* | δ*(i,w)∈ F}.^[1]

Konačni automat A=(Σ,Q,I,F,Δ) je standardan ako je I={i} ⊆ Q i ako

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

(tj. u početnom stanju se ne završava nijedan luk automata).^[1]

Konačni automat A=(Σ,Q,I,F,Δ) je potpun(kompletan) ako za svako stanje p ∈ Q i svako slovo a ∈ Σ, postoji bar jedno stanje q ∈ Q takvo da je (p,a,q) ∈ Δ. Ako neki konačan automat A nije potpun, onda se takav automat može dopuniti do potpunog automata koji prepoznaje isti jezik kao i automat A. Postupak kompletiranja se sastoji u uvođenju novog stanja w ∈ Q, takvog da w ∉ F. Tada, za svaki par (p,a) za koji ne postoji nijedno q ∈ Q takvo da je (p,a,q) ∈ Δ dodajemo luk (p,a,w), (w,a,w) ∈ Δ za svako a ∈ Σ.^[2]
Svaki konačan automat se može transformisati u deterministički konačni automat, što pokazuje sledeća:
Teorema. Za svaki konačan automat A, postoji potpun deterministički konačan automat B takav da je

      L(A)=L(B).^[2]

Vidi još

Reference

^ ^a ^b ^v Duško M. Vitas, Prevodioci i interpretatori, Matematički fakultet, Beograd, 2006.
^ ^a ^b ^v ^g ^d ^đ ^e ^ž ^z ⁱ Duško M. Vitas, Prevodioci i interpretatori, Matematički fakultet, Beograd, 2006.

Spoljašnje veze

Napomene i reference

[automatski_generisano1-1] v Duško M. Vitas, Prevodioci i interpretatori, Matematički fakultet, Beograd, 2006.

[automatski_generisano2-2] v ^g ^d ^đ ^e ^ž ^z ⁱ Duško M. Vitas, Prevodioci i interpretatori, Matematički fakultet, Beograd, 2006.

[1]

[2]