automati Flashcards
konacni automati su:
▪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
sekvencijski automat nije konačan
točno
jezik je regularan kada?
postoji konačni automat koji ga prihvaća
kako su regularni jezici nastali?
nastali 50-tih godina kao formalizam za opis sintakse programskih jezika
upisi izraz koji potraži nijednog ili više izraza koji odgovaraju prethodnome
*
upiši izraz koji potraži nijedan ili jedan cjelobrojni
višeznamenkasti
?
Deterministički konačni automat
je mehanizam, koji radi u diskretnim koracima,
točno
DKA ima
▪ 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.
kada automat prihvaća neki niz?
▪ automat prihvaća ulazne nizove koji odgovaraju putevima od početnog do nekog prihvatljivog stanja
koje nizove DKA prihvaća
DKA, prihvaća sve nizove nula i jedinica koje sadrže podniz 01
▪ prihvaća niz ako završi u prihvatljivom stanju
kako nazivamo skup svih nizova (riječi) koje automat prihvaća
jezik konačnog automata
kako DKA dijeli skup *
▪ 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
sto je minimizacija DKA
za svaki DKA je moguće izgraditi beskonačno mnogo drugih DKA koji prihvaćaju isti jezik,
tražimo automat s najmanjim brojem stanja
sto je nedeterminizam
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
koja je osnovna razlika između determinističkog i nedeterminističkog konačnog automata
▪ kod nedeterminističkog: postoji više mogućih puteva između dva stanja za isti ulazni niz
▪ kod determinističkog: samo jedan put
za bilo koji MoDKA moguće je izgraditi istovjetni MeDKA i obrnuto
točno
Mooreov automat
izlaz je funkcija stanja automata
Mealyev automat
izlaz je funkcija prijelaza (stanja automata i ulaznog znaka):
Mooreov i Mealyev automat su istovjetni ukoliko
za bilo koji ulazni niz daju jednake izlazne nizove
tocno
kako se naziva nedeterministički konačni automat s -
prijelazima
3NKA
koi je problèm s 3NKA
prijelaz iz početnog u prihvatljivo stanje samo 3-prijelazima
gdje i kako se automati koriste
▪ za modeliranje naprava
▪ za modeliranje protokola
▪ za računalne postupke
▪ u računalnoj lingvistici
▪ kod digitalnih sklopova
u primejnri, regularni izraz se može zapisat
kao 3nka
točno
koliko ima pravila za pretvaranje
regularnih izraza u v 3-NKA
7
sto 3nka prikazuje
pokazuje vezu regularnih izraza i konačnih automata (-NKA)
kako provjeriti e-adresu?
-svi znakovi
-bez početnih, završnih ili uzastopnih točaka
-glavna domena 2-6 znakova
-i zatim sve to CASE SENSITIVE
RI u praksi
-provjeravanje formata datuma -provjeravanje formata IP adrese -provjeravanje unosa “govoreće” šifre
-provjera formata računa ili kartice
za što se koriste formalne gramatike
za generiranje i analizu nizova znakova (formalnoga) jezika
gramatika je opisana s produkcijama ▪produkcija: A → B
▪A producira B
točno
koja je upotreba generativne gramatike
generiranje nizova koji odgovaraju sintaksi
upotreba gramatike
-određivanje sintakse programskih jezika
-parsiranje: provjeravanje odgovara li program strukturi (sintaksi) programskog jezika
-određivanje struktura rečenica u računalnoj ligvistici
