Test Flashcards
(39 cards)
Nabroj vrste programskih prevodioca
Asembleri
Makroasembleri
Prevodioci jezika viseg nivoa
Hibridni prevodioci
Multijezicki prevodioci
Sta su asembleri?
Asembleri su programski prevodioci koji se koriste za prevodjenje zapisa sa nivoa asemblerskog jezika na masinski nivo.
Asemblerski jezik je jako sličan mašinskom kodu tako da su asembleri imali zadatak da simboličke oznake pisane u kodu preslikaju u odgovarajuće binarno kodirane reči koje računar razume i može da izvršava.
Sta su makroprocesori I koji su njihovi sastavni delovi?
Makroprocesor prepoznaje definicije makroa u kodu i vrši razvoj makroa u svakoj tački poziva makroa - prepisuje njegovo telo odnosno skup asemblerskih instrukcija i nakon toga asembler vrši dalje prevođenje.
Izvesne sekvence naredbi se često ponavljaju u programu zato se pojavljuju makroasemblerski jezici koji omogućavaju da se definišu makroi, odnosno da se skupovi asemblerskih naredbi zamene jednom instrukcijom - definiše se makro koji će se posle u programu pozivati.
Makroi su preteče potprograma u višim programskim jezicima.
Osnovni delovi su: makroprocesor I asembler.
Navesti razliku izmedju kompilatora I interpretatora.
Kompilator prevodi ceo kod odjednom i formira izvršnu verziju koja može da se poziva na izvršenje proizvoljan broj puta bez ponovnog prevođenja.
Interpretator prevodi deo po deo programa i čim kreira celinu koja može da se izvrši izvršava je i taj deo prevedenog koda se briše iz memorije i prelazi se na sledeći - to je dobro za kratke programe koji se neće više puta pozivati.
Problem - ako imamo neke glomazne petlje za svaku iteraciju bi se program ponovo prevodio i potprogrami isto
Zato se sve više koriste just in time kompilatori - čim se prevede celina koja moze da se izvrši ona se izvršava, ali se prevedeni deo koda ne briše iz memorije.
Sta podrazumevamo pod hibridnim prevodiocima?
Omogućavaju da se isti kod izvršava na različitim platformama - isti međukod može da se distribuira različitim mašinama i posle se različitim interpretatorima prevodi u mašinske jezike odredišnih mašina.
Danas se često umesto interpretatora (jer je spor) stavlja just in time compiler.
Vrše analizu koda kao kompilatori, generišu međukod programa i nakon toga interpretiraju taj međukod.
Objasniti visejezicke prevodioce.
Nastali su da se olakša proces prevoženja.
Svaki jezik za koj se piše prevodilac se prevodi u zajednički identičan međukod. Tako da se prve faze, koje su nezavisne od odredišne mašine, ali su zavisne od izvornog jezika, pišu za svaki jezik ponaosob, a onda se takođe ponaosob vrši prevođenje međukoda za svaku odredišnu mašinu.
Za .NET je karakteristično da se u drugoj fazi umesto interpretatora koriste just in time kompajleri
Nabroj osnovne faze u procesu prevodjenja visih programskih jezika.
Osnovne faze su:
Leksička analiza – leksički analizator analizira znak po znak naredbe i identifikuje leksičke celine (lekseme), pri čemu svaku leksemu zamenjuje odgovarajućim simbolom (tokenom - koj predstavlja njeno jedinstveno značenje u kodu). On izdvaja reči iz ulaznog koda i određuje njihovo značenje
Sintaksna analiza – zadatak sintaksnog analizatora je da utvrdi da li je ulazni kod napisan u skladu sa pravilima jezika. Ta pravila se definišu formalnim gramatikama. Izlaz iz sintaksnog analizatora je sintaksno stablo koje nam kaže kako je kod sagrađen i ključno je, jer se sve ostale faze oslanjaju na njega.
Semantička analiza – sintaksni analizator može da bude obogaćen dodatnim semantičkim procedurama. Proverava da li su prepoznate sintaksne celine međusobno usaglašene.
Kako mogu da ne budu usaglašene?
ako nedostaje deklaracija promenljivih
ako su operacije primenjene na nedozvoljenim tipovima podataka
ako koristimo promenljivu koja nije inicijalizovana
Generisanje međukoda – međukod programa se generiše iz apstraktnog sintaksnog stabla, svaki čvor se preslikava u naredbu, prvo se izvršavaju akcije koje su niže u stablu.
može da se izvršava u dve faze:
prvo prevođenje u međukod visokog nivoa koj je bliži sintaksnom stablu,
pa onda u međukod niskog nivoa koj je bliži asemblerskim jezicima
Pošto sintaksno stablo sadrži čvorove koji nisu bitni za dalji tok prevođenja radi se redukcija na apstraktno sintaksno stablo - izbacuju se čvorovi koji ne definišu nikakvu obradu podataka.
Optimizacija međukoda – mnogo je lakše optimizovati međukod
Generisanje koda – na osnovu međukoda generiše se ciljni kod programa. To može da bude zapis u asemblerskom jeziku ciljne mašine ili direktno mašinski jezik.
Sta se podrazumeva pod apstraktnom (formalnom) azbukom?
Apstraktna (formalna) azbuka, ili samo azbuka, je svaki konačan neprazan skup simbola V.
Simbol (znak ili slovo) je osnovni (nedeljivi) element jezika.
Npr. Azbuku V čine sledeći simboli:
Mala i velika slova abecede A,a,B,b,C,c …
Specijalni znaci +, -,*, :=, …
Reči kao što su if, while, class, …
konstante
identifikatori
operatori…
Formalni jezici se definišu u 2 nivoa:
prvo se definišu leksički elementi - reči
a onda reči predstavljaju azbuku za definisanje sintakse programskog jezika
Formalna definicija reci.
Reč - konačan broj redom napisanih simbola azbuke V.
Niz koji ne sadrži nijedan simbol naziva se prazna reč i označava sa ε.
Reči su uređeni nizovi tako da je ab ≠ ba
Reč se može I formalno definisati sledećim skupom pravila:
ε je reč nad azbukom V
Ako je x reč azbuke V i ako je a element azbuke V tada je i xa reč azbuke V
y je reč nad azbukom V ako i samo ako je dobijen pomoću pravila 1 i 2
Za označavanje reči koriste se obično završna mala slova abecede: u, v, w, x, y, z
| x | je dužina reči x.
| ε | = 0
x | je dužina reči x. | ξ | = 0
Operacije nad recima.
Spajanje (konkatenacija) reči – proizvod - ako su x i y dve reči azbuke V, proizvod ili spajanje reči je operacija kojom se stvara nova reč tako što se na jednu recč nadovezuje druga reč.
X=aA, y=ab, z=xy=aAab ,
εx = xε = x , ε je neutralni element za operaciju množenja reči
Stepen (eksponent)
xxx…x = xn, x0 = ε , x1 = x, x2 = xx …
Delovi reči:
prefiks - Niz koji se dobija kada se izbaci nula ili više simbola na kraju reči x (može da bude i ε),
sufiks - Niz koji se dobija izbacivanjem nula ili više početnih simbola reči x (može da bude i ε),
podniz - reč koja se dobija kada se izbaci neki prefiks i/ili neki sufiks reči x (svaki prefiks i svaki sufiks reči x su podnizovi reči x, ali podniz može da bude i neki središnji deo reči, a i ε),
pravi prefiks, pravi sufiks, pravi podniz - svaki neprazan niz y koji je prefiks, sufiks ili podniz reči x, takav da je x različito od y
podsekvenca - svaki niz koji se dobija izbacivanjem nula ili više sukcesivnih simbola iz reči x
Pojam formalnog jezika.
Formalnim jezikom L nad azbukom V naziva se bilo koji skup reči nad tom azbukom.
Odnosno bilo koj podskup skupa svih mogućih reči kreiranih nad datom azbukom V.
Prema ovoj definiciji formalni jezik je i prazan skup reči kao i skup { ε } koji sadrži samo reč ε i skup koj sadrži sve moguće reči sagrađene od simbola date azbuke.
Ograničenje koje će reči pripadati nekom jeziku definišemo preko formalnih gramatika.
Neka je data azbuka V. Skup svih reči nad azbukom V se označava sa V. Skup V je beskonačan.
Formalni jezik nad azbukom V je bilo koji podskup skupa V. L ⊆ V
Bilo koji podskup reci nad azbukom V, bilo da je konacan ili beskonacan, predstavlja jezik.Kako je V* uvek beskonacan skup, broj njegovih podskupova je takodje beskonacan. Drugim recima, ma koliko da je azbuka siromasna, cak I kada se sastoji samo od jednog simbola, nad njim se moze definisati beskonacan broj razlicitih formalnih jezika.
Osnovne operacije nad jezicima.
Ako je L formalni jezik onda se može definisati i njegov reverzni jezik u oznaci LT, kao skup svih reverznih
(transponovanih) reči jezika L. Ovo je korisno jer neki algoritmi analiziraju kod sa kraja prema početku.
LT ={xT | x∈ L} (xa)T = axT
Ako su L i M formalni jezici, onda je L ∪ M, unija ova dva jezika i obuhvata sve reči koje pripadaju ili jeziku L ili jeziku M.
L ∪ M={x | x ∈ L ∨ x ∈ M}
Ako su L i M formalni jezici, onda je L ∘ M, proizvod ova dva jezika i obuhvata sve reči koje nastaju operacijom nadovezivanja reči jezika M na reči jezika L.
L ∘ M={xy | x ∈ L ∨ y ∈ M}
Potpuno zatvaranje jezika L, koje se označava sa L, je skup svih reči koje nastaju kao proizvodi reči jezika L uključujući i ε . L1 npr. su sve reči dužine 1, L su sve reči proizvolje dužine.
∞
L* = ∪Li
i=0
Pozitivno zatvaranje jezika L, za koje se koristi oznaka L+ (skup svih reči čija je dužina > 0, odnosno ne sadrži ε):
∞
L+ = ∪Li
i=1
V+ = V*\ ε
Definicija formalne gramatike.
Formalna gramatika je sredstvo za opis jezika na konačan način.
Gramatika jezika opisuje kako se generišu reči koje pripadaju određenom jeziku.
Formalna gramatika je uređena četvorka koja sadrži G=(Vt, Vn, S, P) pri čemu važi
P je skup smena oblika: x->y
i važi da se u produkcionim pravilima na levoj strani uvek mora pojaviti bar jedan neterminalni simbol, a na desnoj strani je reč sastavljena iz bilo kojih simbola (neterminalnih i terminalnih).
Elementi gramatike su simboli pomoću kojih se gradi kod:
* Terminalni simboli – Osnovni simboli od kojih se satoje reči jezika. Npr. ključne reči nekog programskog jezika if, then, else su terminalni simboli. reči napisane boldiranim fontom
* Neterminalni simbol – Pomoćni (sintaksni) simboli kojima se označavaju skupovi reči. Neterminali se uvode da bi se lakše definisao jezik koji se generiše gramatikom, kao i da bi se lakše definisala hierahijska struktura jezika. reči napisane malim slovima italik ili između zagrada <>
* Startni simbol – Neterminalni simbol iz kojeg se izvode sve reči jezika koji se definiše. (simbol na levoj strani prve smene)
* Produkciono pravilo (smena) – definiše način na koji se stvaraju nizovi koji mogu da se sastoje od neterminala i terminala. U opštem slučaju pravila su oblika: x ::= y ili x -> y
na levoj strani smene je uvek jedan neterminalni simbol a na desnoj je bilo koja reč sastavljena od terminalnih i neterminalnih simbola pa i ε.
Jezik definisan formalnom gramatikom.
Formalni jezik L definisan gramatikom G je skup reči koje se sastoje od terminalnih simbola a dobijaju se tako što se na starni simbol primene pravila gramatike:
L(G) = {w S ⎯⎯→w, w ∈ V}
Tipovi gramatika po Comskom.
Još u svojim ranim radovima Chomsky je formalne je identifikovao četiri tipa formalnih gramatika i jezika. Gramatike koje zadovoljavaju gore date opšte uslove je nazvao gramatikama tipa nula. praktično svaka formalna gramatika je gramatika tipa nula. ostali tipovi gramatika imaju strože definisane uslove koje treba da zadovolje pravila. To znači da se tim tipovima gramatika može definisati uži skup jezika ali se zato može jednostavnije vršiti analiza i prepoznavanje takvih jezika.
Gramatike tipa jedan ili Konteksne gramatike
Gramatike tipa jedan su formalne gramatike koje pored opštih uslova koje zadovoljavaju gramatike tipa nula imaju pravila x → y koja zadovoljavaju sledeći uslov:
| x | ≤ | y |
To znači da se reči sa leve strane smena mogu preslikavati samo u reči koje su jednake ili veće dužine. Drugim rečima, nisu dozvoljena pravila oblika:
x → ε
Gramatike tipa jedan kao i gramatike tipa nula se obično nazivaju i konteksnim gramatikama. To je zbog toga što se neterminal koji je obavezan na levoj strani smene kod ovih gramatika nalazi u nekom kontekstu i čitav taj kontekst se preslikava u novu reč.
Gramatike tipa dva ili Beskontekne gramtike
Gramatike tipa dva su gramatike kod kojih su pravila definisana tako da se na levoj strani nalazi samo neterminal. Neterminali se preslikavaju u reči. Kako se neterminali prilikom izviđenja posmatraju izolovano od konteksta u kome se nalaze ove gramatike se nazivaju beskonteksnim gramatikama. Znači smene kod ovih gramatika su oblika:
A → y, gde je A∈ Vn i y∈ Vt*
Za opis programskih jezika se obično koriste beskonteksne gramatike. Za ove gramatike se koristi i naziv Bekusova normalna forma BNF i najčešće se koriste za opis sintakse programskih jezika.
Gramatike tipa tri su formalne gramatike koje zadovoljavaju opšte uslove ali su orgraničene na smene
oblika:
A → a B ili , A → a gde je A,B∈ Vn i a∈ Vt
Za ove gramatike se koriste još i nazivi Regularne gramatike, Gramatike sa konačnim brojem stanja i
Automatne gramatike.
Služe za opis leksičkih elemenata jezika.
Naziv regularne gramatike dolazi odatle što su ove gramatikama tipa tri generišu regularni izrazi koji se efikasno mogu prepoznavati konačnim automatima. Regularne gramatike imaju široku primenu u mnogim oblastima u kojima treba vriti prepoznavanje nizova. U kontekstu programskih prevodilaca koriste se za opis leksičkih elemenata jezika (identifikatora, konstanti, literala i sl.) koje prepoznaje leksički analizator, o čemu će biti reči kasnije.
Opsta definicija automata za prepoznavanje jezika.
Problem prepoznavanja jezika, odnosno utvrđivanja da li zadata reč pripada jeziku opisanim određenom gramatikom, rešava se automatima kao uređajima za prepoznavanje jezika.
Niz simbola (reč) koji se prepoznaje zapisan je na ulaznoj traci. Po ulaznoj traci se kreće ulazna glava koja u jednom trenutku čita jedan simbol sa trake, Ova glava se u opštem slučaju može kretati i napred i nazad. Funkcionalni deo automata je njegov najznačajniji deo. Može da se nađe u nizu različitih stanja u zavisnosti od toga kako je opisan jezik koji se prepoznaje. Funkcionalni organ beleži predistoriju prepoznavanja i za to koristi memoriju koja je u ovom opštem modelu predstavljena kao beskonačna memorija. Automat sa beskonačnom memorijom nije praktično izvodljiv tako da se realni automati razlikuju od ovog modela po tome što koriste neki određeni tip memorije.
Proces prepoznavanja reči koja je upisana na ulaznu traku kreće tako što se ulazna glava pozicionira na startni simpol (#), a funkcionalni organ se nalazi u svom početnom stanju. U svakom koraku prepoznavanja, u zavisnosti od toga gde je pozicionirana ulazna glava (koji simbol čita) i stanja funkcionalnog organa, kao i simbola u radnoj memoriji koji čita radna glava događaju se sledeće promene u automatu:
menja se stanje funkcionalnog organa
u radnu memoriju se upisuje jedan ili više simbola
radna glava se pomera napred, nazad ili ostaje na poziciji na kojoj se i nalazi.
Proces prepoznavanja reči je uspešno završen u trenutku kada se ulazna glava pozicionira na krajnji granični simbol (desni #) i funkcionalni organ se nadje u jednom od svojih završnih stanja.
Tjuringova masina.
Za razliku od opšteg modela automata Tjuringova mašina ima radnu memoriju u vidu beskonačne trake.
Operativni organ menja stanje. * Ulazna glava se pomera. * Na radnu traku se upisuje novi simbol. * Pomera se radna glava. 2N Tjuringova mašina se može opisati sledećom entorkom: Tm=(Q, V, S, P, q0, b, F) gde je:
Q – Skup stanja operativnog organa
V – Skup simbola na ulaznoj traci
S – Skup simbola na radnoj traci
F – Skup završnih, krajnjih stanja (Podskup skupa Q) q0 – Početno stanje operativnog organa
b – Oznaka za prazno slovo
P – Preslikavanje definisano sa:
Q×(V∪#) ×S →{Q×(S {b})×{−1,0,+1}×{−1,0,+1}}
odnosno ako je ulazna glava pozicionirana na simbolu a, funkcionalni organ se nalazi u stanju qi, a radna glava iznad simbola A, automat će preći u stanje qj, na radu traku će upisti simbol B i izvršiće pomeranje ulazne glave i radne glave u skladu sa vrednostima d1 i d2. Pri tome važi sledeća notacija: Ako je d=0 nema pomeranja radne glave, za d=1 glava se pomera za jedno mesto u desno, a za d=-1 glava se pomera za jedno mesto u levo (vraća se nazad).
Mašina započinje prepoznavanje tako što je ulazna glava pozicionirana na početnom graničnom simbolu, funkcionalni organ se nalazi u početnom stanju i radna traka je prazna. Prepoznavanje reči se završava uspešno ako se u trenutku kada se ulazna glava pozicionira na krajni granični simbol #, automat nađe u nekom od završnih stanja (elemenata skupa F).
TM je deterministicka ako se svaki element (q,a,X) preslikava u najvise jedan element (P, Y, d1, d2)
Dokazano je da su sve četri klase Tjuringovih mašina, 2N, 1N, 2D, 1D su međusobno ekvivalentne i svaka od njih prepoznaje jezike jezike tipa nula. To u suštini znači da je za prepoznavanje bilo kog jezika tipa nula moguće definisati bilo koji tip Tjuringove mašine, odnosno ako je moguće definisati jedan tip Tjuringove mašine onda je moguće definisati i ekvivalentne mašine ostalih tipova. Jedini problem u svemu ovome je to što model Tjuringove mašine podrazumeva beskonačnu memoriju, što je u praksi praktično nije izvodljivo. Zbog toga Tjuringova mašina ostaje samo teorijski model a u praksi se koriste automati sa konačnim memorijama, što kao posledicu ima ograničenje jezika koji se mogu prepoznavati.
Linearno ograniceni automati I koje jezike prepoznaju
Linearno ograničeni automati su u suštini Tjuringove mašine sa konačnom trakom kao radnom
memorijom. Naime 2N Tjuringova mašina kod koje može da se odredi konstanta k takva da je dužina reči koja se upisuje na radnu traku najviše k puta veća od dužine reči koja se prepoznaje, naziva se Linearno ograničenim automatom.
Odnosno, ako se prepoznaje reč w ∈ V, gde je |w|= n, na radnu traku se upisuje reč dužine r, pri čemu je r ≤ nk
Posledica ovog ograničenja je da Linerano ograničeni automati ne prepoznaju sve jezike tipa nula. Odnosno, postoje jezici tipa nula za koje nije moguće definisati linearno ograničeni automat. Naime dokazana su sledeća tvrđenja:
Klase 2N i 1N Linearno ograničenih automata su međusobno ekvivalentne i svaka od njih prepoznaje jezike tipa jedan. Drugim rečima, za svaki jezik tipa jedan može se definisati
nedeterministički LOA koji ga prepoznaje.
Klase 2D i 1D Linearno ograničenih automatu su međusobno ekvivalentne. To znači da se za svaki 2D LOA može definisati ekvivalentan 1D LOA.
Ekvivalentnost 2N i 2D LOA do sada nije dokazana.
Svaka klasa LOA ne prepoznaje sve jezike tipa jedan.
Magacinski automati.
Magacinski automat kao radnu memoriju koristi memoriju organizovanu u vidu magacina. 2N Magacinski automat je definisan entorkom Ma=(Q, V, S, P, q0, Z0, F) gde je:
Q – Skup stanja operativnog organa
V – Skup simbola na ulaznoj traci
S – Skup magacinskih simbola
F – Skup završnih, krajnjih stanja (Podskup skupa Q)
q0 – Početno stanje operativnog organa
Z0 – Početni simbol na vrhu magacina
P – Preslikavanje definisano sa:
Q ×(V∪#) × S →{Q × S* ×{−1,0,+1}}
1N magacinski automat prepoznaje jezik L ako i samo ako je L beskonteksni jezik tipa 2.
2N i 2D magacinskim automatima mogu se prepoznavati svi beskontesni i neki, ali ne svi, konteksni jezici.
Postoje beskonteksni jezici koji se ne mogu prepoznati 1D magacinskim automatima.
Magacinski automati se koriste u sintaksnoj analizi programskih jezika
Konacni automati.
Konačni automati su uređaji za prepoznavanje regularnih jezika. Za razliku od drugih tipova nemaju radnu memoriju već se predistorija preslikavanja pamti samo preko promene stanja funkcionalnog organa
Kod dvosmernih, Na osnovu stanja operativnog organa i simbola koji čita ulazna glava, menja se stanje automata i ulazna glava pomera za jedno mesto ulevo ili udesno ili ostaje na svom mestu. Kod jednosmernih menja se samo trenutno stanje automata.
Konačan automat je opisan entorkom Ka=(Q, V, P, q0, F), gde je:
Q – Skup stanja operativnog organa
V – Skup simbola na ulaznoj traci
F – Skup završnih, krajnjih stanja (Podskup skupa Q)
q0 – Početno stanje operativnog organa
P – Preslikavanje pravilima oblika: Q × {V ∪ #} → Q
Za ulazni niz w∈ V*, kažemo da je prepoznat automatom ako automat prevodi iz početnog u neko od
njegovih krajnjih stanja, odnosno ako je P(q0, w) ∈ F.
Za predstavljanje automata se koriste grafovi, pri čemu čvorovi grafa odgovaraju stanjima automata, a potezi preslikavanjima. Na Slici 3.5 je predstavljen graf koji odgovara automatu iz primera. Početno stanje automata je označeno strelicom, a krajnje stanje sa dva koncentrična kruga.
Kako se preslikavanje P(qi,a)=qj može tumačiti da se stanje qi automata za ulazno slovo a preslikava u stanje qj, svako takvo preslikavanje se na grafu predstavlja odlaznim potegom od stanja qi do stanja qj na kome je oznaka a.
Razlika izmedju deterministickih I nedeterministickih konacnih automata.
Podela na determinističke i nedeterminističke izvršena je u odnosu na preslikavanje stanja funkcionalnog organa koje se vrši u toku prepoznavanja .
Deterministicki – pod dejstvom istog ulaznog simbola prelazi u jedno stanje.
Nederministicki – pod dejstvom istog ulaznog simbola prelazi u vise stanja.
Ukoliko je stanje u koje prelazi automat za određeni ulazni simbol i određeno zatečeno stanje, jednoznačno definisana onda je to deterministički automat. Ukoliko je ovo preslikavanje višeznačno onda je to nedeterministički automat.
Pojam regularnog izraza I nekoliko primera
Jezici tipa tri koji se prepoznaju konačnim automatima se nazivaju i regularnim jezicima zato što se mogu opisati regularnim izrazima.
Ovde ćemo posvetiti malo više pažnje pojmu regularni izraz. Oni se mogu posmatrati i kao meta jezici za predstavljanje formalnih jezika.
Regularni izrazi u suštini definišu skup reči jezika. Sami regularni izrazi su nizovi formirani od slova neke azbuke V i skupa specijalnih simbola. Regularni izraz obično skraceno definiše skup reči jezika definisanog nad azbukom V. Postoje posebna pravila kako se vrši tumačenje (denotacija) regularnog izraza i generisanje skupa reči jezika koji je opisan regularnim izrazom.
Regularni izrazi su veoma korisni za formalno i koncizno definisanje jezika. Kada je jezik konačan moguće je nabrojati sve reči koje sadrži, ali u slučaju beskonačnih jezika to postaje problem. Zbog toga se
regularni izrazi i koriste u različitim disciplinama kao sredstvo za opis kompleksnih jezika. Na žalost, ne
mogu se svi formalni jezici opisati regularnim izrazima. To je moguće samo u slučaju jezika tipa tri, zbog čega se oni i nazivaju regularnim. Sledeći primer ilustruje moć regularnih izraza da definišu beskonačne i kompleksne jezike.
Pokazati kako se osnovni regularni izrazi preslikavaju u automate.
Za svaki regularni izraz se može definisati konačni automat koji ga prepoznaje.
Formalna definicija regularnog izraza nad azbukom V.
Regularni izraz nad azbukom V definise se sledecim skupom pravila:
Prazan skup je regularni izraz
ε je regularni izraz
Ako je a ∈ V , tada je a regularni izraz
Ako su r1 i r2 regularni izrazi, onda su i (r1|r2) i (r1 ∘ r2) regularni izrazi
Ako je r regularni izraz onda je I r* takodje regularni izraz
Nema drugih regularnih izraza nad azbukom V
