2 - Leksička analiza

Question 1

Koja je uloga skenera?

Answer 1

1) Isporučuje parseru terminalne simbole (tokene)
2) Ignoriše neke delove ulaznog teksta:
- razmake
- tabulatore
- znake za kraj linije (CR, LF)
- komentare

Question 2

Šta su tokeni?

Answer 2

Terminalni simboli

Question 3

Šta podrazumeva oblik tokena: (IF,-) (LP,-) (ID, “x”) (EQ,-) (NUM,3) …?

Answer 3

(klasa, vrednost)

Question 4

Čime je opisan deterministički konačni automat?

Answer 4

Uređenom petorkom (S, U, δ, St, P)

Question 5

Šta je azbuka automata?

Answer 5

Skup ulaznih simbola

Question 6

Šta je δ u determinističkim konačnim automatima?

Answer 6

Funkcija prelaza, δ: S × U → S

Question 7

Kako glasi algoritam rada DKA?

Answer 7

U svesci pitanje 7

Question 8

Kako se obeležava jezik konačnog automata?

Answer 8

L(K)

Question 9

Šta je jezik konačnog automata?

Answer 9

Jezik L(K) automata K je skup svih sekvenci ulaznih simbola koje automat prihvata

Question 10

Šta je ε?

Answer 10

Prazna sekvenca - prelazak iz jednog stanja u drugi bez konzumiranja simbola

Question 11

Koje su specifičnosti NKA?

Answer 11

• automat može da pređe iz jednog stanja u drugo a da pritom ne konzumira nijedan simbol sa ulaza (ε = prazna sekvenca)
• jedno stanje može da ima više različitih prelaza za neki simbol

Question 12

Čime je opisan nedeterministički konačni automat?

Answer 12

Uređenom petorkom (S, U, δ, St, P)

Question 13

Šta je δ u nedeterminističkim konačnim automatima?

Answer 13

Funkcija prelaza δ: S × (U ∪ {ε}) → P(S) partitivni skup

Question 14

Kako se predstavlja skup stanja prihvatanja?

Answer 14

P

Question 15

Kako se predstavlja skup stanja odbijanja?

Answer 15

S-P

Question 16

Kada NKA prihvata ulaznu sekvencu?

Answer 16

Ako i samo ako za tu ulaznu sekvencu postoji scenario promene stanja iz nekog od startnih stanja do nekog od stanja prihvatanja

Question 17

Za šta služi funkcija ε-zatvaranja (ε-closure(s))?

Answer 17

Daje skup stanja dostižnih iz s po ε
(s je uključeno u skup)

Question 18

Kako izgleda algoritam za funkciju ε-zatvaranja (ε-closure(s))?

Answer 18

U svesci pitanje 18

Question 19

Kako glasi algoritam rada NKA?

Answer 19

U svesci pitanje 19

Question 20

Šta znači ekvivalentnost u konačnim automatima?

Answer 20

Prepoznavanje istog jezika

Question 21

Kako se uvek može konstruisati DKA koji je ekvivalentan (prepoznaje isti jezik) kao zadati NKA?

Answer 21

Svako stanje DKA je skup mogućih stanja NKA do kojih NKA može doći u toku rada.

Question 22

Prilikom pretvaranja NKA u DKA, koji je najgori slučaj što se tiče broja stanja?

Answer 22

Moguće je eksponencijalno povećanje broja stanja, u najgorem slučaju 2^n

Question 23

U jednoj rečenici, kakav je odnos NKA i DKA?

Answer 23

DKA je specijalan slučaj NKA

Question 24

Kakve su razlike NKA i DKA?

Answer 24

• DKA ima tačno jedno startno stanje
• DKA nema ε prelaze
• funkcija prelaza DKA ima jedinstvenu vrednost
• uvek se može konstruisati DKA koji je ekvivalentan kao zadati NKA
• moguće eksponencijalno povećanje broja stanja DKA u odnosu na NKA prilikom konstruisanja DKA iz NKA