automati

Question 1

konacni automati su:

Answer 1

▪DKA
deterministički konačni automat
▪NKA nedeterministički konačni automat
▪E-NKA – nedeterm. konačni automat s  prijelazima
▪konačni automati s izlazom
–Mooreov automat
–Mealyev automat

Question 2

sekvencijski automat nije konačan

Answer 2

točno

Question 3

jezik je regularan kada?

Answer 3

postoji konačni automat koji ga prihvaća

Question 4

kako su regularni jezici nastali?

Answer 4

nastali 50-tih godina kao formalizam za opis sintakse programskih jezika

Question 5

upisi izraz koji potraži nijednog ili više izraza koji odgovaraju prethodnome

Answer 5

*

Question 6

upiši izraz koji potraži nijedan ili jedan cjelobrojni
višeznamenkasti

Answer 6

?

Question 7

Deterministički konačni automat
je mehanizam, koji radi u diskretnim koracima,

Answer 7

točno

Question 8

DKA ima

Answer 8

▪ konačan skup stanja,
▪ konačan skup ulaznih znakova (signala),
▪ funkciju prijelaza koja za znak na ulazu definira prijelaz iz stanje u novo stanje,
▪ početno stanje
▪ i skup prihvatljivih stanja.

Question 9

kada automat prihvaća neki niz?

Answer 9

▪ automat prihvaća ulazne nizove koji odgovaraju putevima od početnog do nekog prihvatljivog stanja

Question 10

koje nizove DKA prihvaća

Answer 10

DKA, prihvaća sve nizove nula i jedinica koje sadrže podniz 01
▪ prihvaća niz ako završi u prihvatljivom stanju

Question 11

kako nazivamo skup svih nizova (riječi) koje automat prihvaća

Answer 11

jezik konačnog automata

Question 12

kako DKA dijeli skup *

Answer 12

▪ na skup koji prihvaća prijelazom u jedno od
prihvatljivih stanja,
▪ te na skup koji ne prihvaća jer se DKA nakon posljednjeg pročitanog znaka ne nalazi u prihvatljivu stanju

Question 13

sto je minimizacija DKA

Answer 13

za svaki DKA je moguće izgraditi beskonačno mnogo drugih DKA koji prihvaćaju isti jezik,
tražimo automat s najmanjim brojem stanja

Question 14

sto je nedeterminizam

Answer 14

izvođenje paralelnih procesa
▪ ako jedan od procesa dođe do prihvatljivog
stanja svi se procesi prihvate
stablo mogućnosti, grananja
▪ počinjemo u korijenu, grananje na svakom koraku
▪ ako je jedna od grana u prihvatljivom stanju onda se prihvaća rad automata

Question 15

koja je osnovna razlika između determinističkog i nedeterminističkog konačnog automata

Answer 15

▪ kod nedeterminističkog: postoji više mogućih puteva između dva stanja za isti ulazni niz
▪ kod determinističkog: samo jedan put

Question 16

za bilo koji MoDKA moguće je izgraditi istovjetni MeDKA i obrnuto

Answer 16

točno

Question 17

Mooreov automat

Answer 17

izlaz je funkcija stanja automata

Question 18

Mealyev automat

Answer 18

izlaz je funkcija prijelaza (stanja automata i ulaznog znaka):

Question 19

Mooreov i Mealyev automat su istovjetni ukoliko
za bilo koji ulazni niz daju jednake izlazne nizove

Answer 19

tocno

Question 20

kako se naziva nedeterministički konačni automat s -
prijelazima

Answer 20

3NKA

Question 21

koi je problèm s 3NKA

Answer 21

prijelaz iz početnog u prihvatljivo stanje samo 3-prijelazima

Question 22

gdje i kako se automati koriste

Answer 22

▪ za modeliranje naprava
▪ za modeliranje protokola
▪ za računalne postupke
▪ u računalnoj lingvistici
▪ kod digitalnih sklopova

Question 23

u primejnri, regularni izraz se može zapisat
kao 3nka

Answer 23

točno

Question 24

koliko ima pravila za pretvaranje
regularnih izraza u v 3-NKA

Answer 24

7

Question 25

sto 3nka prikazuje

Answer 25

pokazuje vezu regularnih izraza i konačnih automata (-NKA)

Question 26

kako provjeriti e-adresu?

Answer 26

-svi znakovi
-bez početnih, završnih ili uzastopnih točaka
-glavna domena 2-6 znakova
-i zatim sve to CASE SENSITIVE

Question 27

RI u praksi

Answer 27

-provjeravanje formata datuma -provjeravanje formata IP adrese -provjeravanje unosa “govoreće” šifre
-provjera formata računa ili kartice

Question 28

za što se koriste formalne gramatike

Answer 28

za generiranje i analizu nizova znakova (formalnoga) jezika

Question 29

gramatika je opisana s produkcijama ▪produkcija: A → B
▪A producira B

Answer 29

točno

Question 30

koja je upotreba generativne gramatike

Answer 30

generiranje nizova koji odgovaraju sintaksi

Question 31

upotreba gramatike

Answer 31

-određivanje sintakse programskih jezika
-parsiranje: provjeravanje odgovara li program strukturi (sintaksi) programskog jezika
-određivanje struktura rečenica u računalnoj ligvistici