Finite automata

Question 1

Definicija KSS (končni sistem stanja)

Answer 1

KSS je objekt, ki prebere diskretne vhode in je lahko v katerem koli izmed končnih mnogo stanj

Question 2

Definicija končnega avtomata

Answer 2

Končni avtomat je matematični model KSS

Question 3

Iz česa je sestavljen DKA (Deterministični Končni Avtomat)

Answer 3

Sestavljen je iz:

1. končne zbirke stanj in
2. končne množice prehodov iz stanja do stanja, ki se zgodijo pri branju simbolov iz vhoda abecede (Σ)

Question 4

Kaj so pravila DKA (Deterministični Končni Avtomat)

Answer 4

1. Za vsak vhodni simbol obstaja točno en prehod iz vsakega stanja
2. q0 je začetno stanje
3. nekatera stanja so končna stanja

Question 5

Kdaj DKA (Deterministični Končni Avtomat) sprejme besedo x?

Answer 5

DKA sprejme besedo x, če je sekvenca prehodov, ki ustreza simbolom x, vodi iz začetnega stanja q0 do poljubnega končnega stanja.

Question 6

Definicija DKA (Deterministični Končni Avtomat)

Answer 6

DFA - (Q, Σ, δ, q0, F) kjer,

1. Q je množica stanj
2. Σ je končna vhodna abeceda
3. (q0 je element Q) je začetno stanje
4. (F je podmnožica Q) je množica končnih stanj
5. δ je prehodna funkcija => Q x Σ => Q

Question 7

Definicija jezika L(M)

Answer 7

Jezik L je regularna množica v primeru, da katerikoli DKA sprejme jezik L

Question 8

Kako dobimo NKA (Nedeterministični Končni Avtomat)?

Answer 8

NKA dobimo iz DKA, tako da dovolimo 0, 1 ali več prehodov iz stanja na enakem vhodnem simbolu.

Question 9

Kdaj NKA (Nedeterministični Končni Avtoma) sprejme besedo a1,a2,…,an?

Answer 9

NKA sprejme besedo, če obstaja sekvenca prehodov , ki ustreza besedi, ki vodi iz začetnega stanje v neko končno stanje.

Question 10

Definicija NKA (Nedeterministični Končni Avtomat)

Answer 10

NKA - (Q, Σ, δ, q0, F) kjer,

1. Q je končna množica stanj
2. Σ je končni vhod abecede
3. (q0 je element Q) je začetno stanje
4. (F je podmnožica Q) je množica končnih stanj
5. δ je prehodna funkcija => Q x Σ => 2naQ

Question 11

Kaj je NKA (Nedeterministični Končni Avtomat) z ε?

Answer 11

NKAε je razširjen model NKA, za vključevanje spontanih prehodov, ki so prehodi za prazen vhod ε.

Question 12

Definicija NKAε (Nedeterministični Končni Avtomat)

Answer 12

NKAε - (Q,Σ,δ,q0,F) kjer,

1. Q je končna množica stanj
2. Σ je končni vhod abecede
3. (q0 je element Q) je začetno stanje
4. (F je podmnožica Q) je množica končnih stanj
5. δ je prehodna funkcija, δ: Q x (Σ U {ε}) => 2naQ

Question 13

Kaj so regularni izrazi?

Answer 13

Regularni izrazi so enostavno opisani jeziki, ki jih sprejemajo končni avtomati.

Question 14

Definicija stika dveh regularnih izrazov L1 in L2

Answer 14

L1L2 = {xy | x ∈ L1 in y ∈ L2}

primer: L1 = {1, 10} in L2 = {11,01}
L1L2 = {111,101,1011,1001}

Question 15

Definicija kleenove ovojnice

Answer 15

L* = U(od i = 0 pa do infinty) Lnai

Question 16

Naštej primere praktičnih uporab končnih avtomatov!

Answer 16

Leksikonski analizatorji, tekstovni urejevalniki, podatkovni kompresorji…