4. UVOD U TEORIJU AUTOMATA

Osim gramatika, uvodimo automate kao važnu klasu generatora jezika, posebno pogodnih za implementaciju na racunalima.

4.1 UVOD

Teorija je konacnih automata koristan instrument za razvoj sustava s konacnim brojem stanja cije mnogobrojne primjene nalazimo i u informatici. Programi, kao što je npr. tekstovni editor, cesto su nacinjeni kao sustavi s konacnim brojem stanja. Na primjer, racunalo se zasebno takoder može promatrati kao sustav s konacno mnogo stanja. Upravljačka jedinica, memorija i vanjska memorija nalaze se teoretski u svakom trenutku u jednom od vrlo velikog broja stanja, ali jos uvijek u konacnom skupu stanja.

Iz svakodnevnog je života upravljacki mehanizam dizala još jedan dobar primjer sustava s konacno mnogo stanja. Prirodnost koncepta sustava s konacno mnogo stanja je razlog primjene tih sustava u razlicitim podrucjima, pa je i to vjerojatno najvažniji razlog njihova proucavanja.

I mi cemo prouciti jos jednu njihovu primjenu, a to je u programima za postupke sintaksne analize jezika ili u tzv. "prepoznavacima" jezika. Opci model automata dan je na sljedecem crtežu. Automat koji sadrži sve navedene 'dijelove' naziva se pretvarac , automat bez ulazne vrpce je generator, a automat bez izlazne vrpce je prepoznavac .

Sl. 4.1- Opci model automata.

U našim ce razmatranjima automati najcešce imati ulogu prepoznavaca. Ovisno o jeziku koji se prepoznaje, odnosno o tipu gramatike, postoje i vrste prepoznavaca dane na sljedecem crtežu.

SI. 4.2 - Chomskyjeva hijerarhija gramatika, njihovi odgovarajuci jezici i

prepoznavaci.

S obzirom da su regularni i beskontekstni jezici predmet našeg bavljenja, u nastavku cemo detaljnije opisati konacne i stogovne automate.

4.2 KONACNI AUTOMAT

Konacni automat nema pomocne memorije. To je matematicki model sustava koji se nalazi u jednom od mnogih konacnih stanja. Stanje sustava sadrži obavijesti koje su dobivene na temelju dotadašnjih podataka i koje su potrebne da bi se odredila reakcija sustava iz iducih podataka. Drugim rijecima, radi se o prijelaznim stanjima koje izvodi dani ulazni znak iz danog alfabeta S pod utjecajem funkcije prijelaza. Svaki se ulazni znak može nalaziti samo u jednom prijelaznom stanju, pri cemu je dopušten povratak na prethodno stanje.

Definicija 4.1

Konacni automat je uredena petorka

M =( Q , S , d , q 0 , F )

gdje su:

Q konacni skup stanja

S alfabet

d funkcija prijelaza, definirna kao d : Q ´ P ( Q ) gdje je P ( Q ) particija od Q

q 0 pocetno stanje, q 0 Î Q

F skup završnih stanja , FQ

Primjer 4.1

Q={1, 2, 3, 4} S ={a, b, c, d} q 0 =1 F ={4}

d (1, a)={1} d (1, b)={2} d (1, c)={3}

d (2, c)={4} d (3, d)={4} d (4, a)={4}

Funkcija prijelaza može se prikazati tablicno. Tada se kaže da je to tablica prijelaza. Redovi tablice predstavljaju stanja , a stupci su oznaceni znakovima iz alfabeta i predstavljaju prijelaze . Na mjestu u redu oznacenom s q , q Î Q i stupcu oznacenom s x, x Î S , upisan je skup narednih stanja (bez viticastih zagrada) ako je funkcija d ( q , x) definirana, odnosno nije ništa upisano ako d ( q , x) nije definirano.

Primjer 4.2

Funkcija prijelaza iz primjera 4.1 može se prikazati kao tablica prijelaza:

Iz definicije funkcije prijelaza zakljucujemo da je to oznaceni, usmjereni graf ciji cvorovi odgovaraju stanjima automata, a grane su oznacene znakovima iz alfabeta. Ako, dakle, funkciju prijelaza prikažemo kao graf, dobivamo dijagram prijelaza . Oznacimo li u tom dijagramu pocetno stanje i skup završnih stanja, dobivamo konacni automat prikazan graficki. Pocetno stanje se oznacuje s:

a završno s:

Ako za znak a iz alfabeta postoji prijelaz iz stanja q u stanje p , tada ce grana u dijagramu prijelaza koja spaja q i p , s pocetkom u q i zavrsetkom u p , biti oznacena s a.

Primjer 4.3

Konacni automat iz primjera 4.1 sada se može prikazati dijagramom prijelaza:

Pocetno stanje je 1, a završno 4.

Dakle, konacni automat operira cineci niz pomicanja. Ako se radi o prepoznavacu, pomicanje je odredeno tekucim stanjem kontrole konacnog stanja i tekucim znakom na koji je postavljen citac ulazne vrpce. Prelaskom u iduce stanje pomice se i citac udesno za jedan znak.

Da bismo znali daljnje "ponašanje" konacnog automata, moramo znati tekuce stanje kontrole konacnog stanja i preostali niz znakova koji se sastoji od tekuceg znakana koji je pozicioniran citac i niza znakova na ulaznoj vrpci desno od tekuceg znaka. Te dvije obavijesti predstavljaju konfiguracij automata, preciznije danu sljedecom definicijom:

Definicija 4.2

Ako je M =( Q , S , d , q 0 , F ) konacni automat, par ( q , w) Î Q ´ S * naziva se konfiguracija automata M . ( q 0 , w) je pocetna konfiguracija , a ( q , e ), q Î F, jest završna (prihvatljiva) konfiguracija .

Pomak u M prikazan je binarnom relacijom na konfiguracijama. Ako d ( q , a) sadrži q ', tada vrijedi:

( q , aw) ( q ', w) za sve w Î S *

Ako postoje konfiguracije C 0 , C 1 , C 2 , ..., C k , tako da je

C i |— C i+1 0 £ i<k,

tada je

C 0 |— k C k

niz pomaka duljine k. Ako nije bitan broj pomaka, pišemo:

C |— * C'

što ima znacenje

C |— k C' k ³ 0

a ako je postojao najmanje jedan pomak

C |— + C' k>0

Deflnicija 4.3

Kaže se da je ulazni niz w prihvatljiv s M ako

( q 0 *w) |— * (q, e ), za neki q Î F

Jezik definiran (generiran) s M , L ( M ), jest skup nizova prihvatljivih s M , tj.

L ( M )={w: w Î S *, ( q 0 , w) |— * (q, e ), q Î F }

Konacni automati generiraju i prihvacaju regularne jezike.

Izvodenje regularnih gramatika

Ako konacni automati generiraju regularne jezike, onda postoji ekvivalentnost konacnih automata i gramatika tipa 3, tj. za konacni automat M postoji bar jedna gramatika tipa 3 tako da je L ( M )= L ( G ), i obrnuto, za danu gramatiku g tipa 3 postoji konacni automat M tako da je L ( G )= L ( M ).U oba cemo slucaja reci da su G i M ekvivalentni . Pojednostavljeno, tada ce postojati ekvivalentnost izmedu produkcija gramatike i funkcije (tablice ili dijagrama) prijelaza konacnog automata.

Ako su zadane produkcije regularne gramatike, problem izvodenja tablice (dijagrama) prijelaza ekvivalentnog konacnog automata dan je s nekoliko trivijalnih pravila:

(1) A ® aB|a

(2) A ® aA | a (rekurzija)

(3) A ® a

(4) A ® aB ç bC

Primjer 4.4

Regularnoj gramatici s produkcijama:

C ® n|nF|.I F ® .I|eS I ® n|nX

X ® eS S ® n|+U|-U U ® n

ekvivalentan je konacni automat definiran dijagramom prijelaza:

Pretpostavimo sada da trebamo izvesti gramatiku regularnog jezika L nad alfabetom A ={a 1 ,a 2 ..., a n }, znajuci svojstva njegovih recenica. Definirat cemo konacni automat dijagramom (tablicom) prijelaza u kojem ce prijelazi (terminali) biti oznaceni znakovima alfabeta jezika L , a 1 , a 2 , ..., a n , a stanja (neterminali) velikim slovima engleskog alfabeta, S 0 , S 1 ,..., S k :

Simbol ® oznacuje pocetno stanje, a simbol Ä završno stanje. Pravila izvodenja regularne gramatike iz ove tablice su sljedeca:

(1) Pocetni simbol oznacenje sa S 0 .

(2) Alternative produkcije koja zapocinje pocetnim simbolom bit ce:

S 0 ® a j d (S 0 , a j )

za sve parove (S 0 , a j )za koje je definiran prijelaz u naredno stanje.

(3) Napisati ostale produkcije za stanja (neterminali u produkcijama gramatike) S 1 do S k . Ako je S i konacno stanje, produkijama za S i dodati praznu alternativu.

U nastavku dajemo nekoliko primjera izvodenja gramatika jezika prirodnih brojeva i podskupa prirodnih brojeva s odredenim svojstvima.

Primjer 4.5 Jezik prirodnih brojeva

Tablica prijelaza konacnog automata koji prepoznaje jezik prirodnih

brojeva dana je s:

iz cega slijede produkcije ekvivalentne regularne gramatike:

N ® 1A| 2A| 3A| 4A| 5A| 6A| 7A| 8A| 9A

A ® 0A| 1A| 2A| 3A| 4A| 5A| 6A| 7A| 8A| 9A| e

što se može transformirati u ekvivalentnu beskontektnu gramatiku:

N ® XA

A ® 0A | N | e

X ® l | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Primjer 4.6 Jezik prirodnih brojeva djeljivih s 4

Promatrajuci prirodne brojeve djeljive s 4, a to su 4, 8, 12, ..., 96, 100, 104, 108, 112, 116, zakljucit cemo da su 4 i 8 djeljivi s 4, a ako je broj veci od 10, djeljiv je s 4 ako je broj sacinjen od dvije posljednje znamenke djeljiv s 4 ili ako su dvije posljednje znamenke 00. Dalje cemo zakljuciti, promatrajuci dvoznamenkaste brojeve djeljive s 4, da ako je pretposljednja znamenka parna ili 0, posljednja mora biti 0, 4 ili 8, a ako je pretposljednja znamenka neparna, posljednja mora biti 2 ili 6. Jezik prirodnih brojeva djeljivih s 4 definiran je konacnim automatom u kojem je tablica prijelaza dana s:

Sada nije problem izvesti produkcije gramatike jezika prirodnih brojeva djeljivih s 4:

A ® 1C|2D|3C|4B|5C|6D|7C|8B|9C

B ® 0B|1C|2D|3C|4B|5C|6D|7C|8B|9C| e

C ® 0D|1C|2B|3C|4D|5C|6B|7C|8D|9C

D ® 0B|1C|2D|3C|4B|5C|6D|7C|8B|9C

Poslije faktorizacija i supstitucija na kraju dobivamo pregledniju ekvivalentnu gramatiku:

A ® XC | YD | ZB

X ® 1 | 3 | 5 | 7 | 9

Y ® 2 | 6

Z ® 4 | 8

B ® 0B | A | e

C ® 0D | XC | YB | ZD

D ® 0B | A

Primjer 4.7 Jezik prirodnih brojeva djeljivih s 3 i 6

Prirodni je broj djeljiv s 3 (v. primjer 3.5) ako mu je zbroj znamenaka djeljiv s 3. I ovaj, na prvi pogled kontekstni aspekt, moze biti riješen izvodenjem regularne gramatike, odnosno najprije definiranjem tablice prijelaza konacnog automata. Ako promatramo brojeve djeljive s tri, 3, 6 i 9 su prva tri broja koja su djeljiva s 3. Potom može slijediti 0, 3 , 6 ili 9. Ali, što ako broj pocinje s 1 ili 2, ili ako pocinje s 3, 6 ili 9, a potom slijedi 1, 2 ili mozda 8? Pažljivom analizom svih brojeva djeljivih s 3 zakljucit cemo da, na primjer, ako broj sadrži brojku 1, 4 ili 7, mora sadržavati ili još dvaput brojku 1, 4 ili 7 ili brojku 2, 5 ili 8, tako da se ukupnim zbrojem tih znamenki dobije broj koji je djeljiv s 3. Pritom eventualno umetnute 0 ne utjecu na ukupni zbroj. Sada nije problem definirati tablicu prijelaza koja sve to obuhvaca:

Na primjer, za ulazni niz w=2220 imamo niz pomaka:

(A, 2220) |— (D, 220) |— (C, 20) |— (B, 0) |— (B, e )

Sada se iz tablice prijelaza dobiju produkcije ekvivalentne gramatike:

A ® 1C|2D|3B|4C|5D|6B|7C|8D|9B

B ® 0B|lC|2D|3B|4C|5D|6B|7C|8D|9B| e

C ® 0C|1D|2B|3C|4D|5B|6C|7D|8B|9C

D ® 0D|1E|2C|3D|4E|5C|6D|7E|8C|9D

E ® 0E|1C|2D|3E|4C|5D|6E|7C|8D|9E| e

Poslije nekoliko faktorizacija i supstitucija, ova se regularna gramatika može transformirati u ekvivalentnu beskontekstnu gramatiku:

A ® XC | YD | ZB B ® 0B | A | e

C ® 0C | XD | YB | ZC D ® 0D | XE | YC | ZD

E ® 0E | XC | YD | ZE | e X ® 1 | 4 | 7

Y ® 2 | 5 | 8 Z ® 3 | 6 | 9

Ako bismo sada iz ove gramatike pokušali izvesti gramatiku prirodnih brojeva djeljivih sa 6, a znamo da su to parni brojevi djeljivi s tri, prilicno bismo se namucili. Vratimo li se konacnom automatu, problem ima jednostavno rješenje: treba umjesto završnih stanja B i E uvesti dva nova završna stanja, npr. F i G, kojima ce se osigurati da je broj djeljiv s tri i da je paran (tj. završava s 0, 2, 4, 6 ili 8):

Q ={A, B, 0, D, E, F, G} S={0, l, 2, 3, 4, 5, 6, 7, 8, 9} q 0 =A F ={F, G}

Evo tablice prijelaza konacnog automata koji generira prirodne brojeve djeljive sa 6:

pa sada nije problem napisati produkcije gramatike jezika prirodnih brojeva djeljivih sa 6, a potom ih transformirati u konacan oblik (beskontekstnu gramatiku):

A ® XC | YD | ZB | 6F B ® 0B | A

C ® 0C | XD | YB | ZC D ® 0D | XE | YC | ZD

E ® 0G | XC | YD | ZE | 6G F ® 0F | A | e

Nedeterministicki konacni automat

Iz definicije konacnog automata i funkcije prijelaza slijedi da je moguce d ( q , a)={ q ', q "}, gdje su q , q ' i q " iz F , a Î S , tj. moguc je pomak iz konfiguracije ( q , a w ) u stanje q ' ili q ", pa se kaže da je, opcenito konacni automat nedeterministicki .

Definicija 4.4

Ako je M = (Q, S , d , q 0 , F ) konacni automat, kažemo da je M deterministicki ako za d ( q , a) = q ' i d ( q , a) = q " slijedi da je q ' = q ".

Svi su konacni automati iz dosadašnjih primjera deterministicki.

Primjer 4.8

Primjer nedeterministickog konacnog automata:

4.3 STOGOVNI AUTOMAT

Automat koji ima pomocnu memoriju sa strukturom stoga (stack) naziva se stogovni automat , odnosno stogovni prepoznavac ako je bez izlazne vrpce, sl. 4.3.

Sl. 4.3 - Stogovni prepoznavac .

Definicija 4.5

Stogovni automat je uredena sedmorka P =(Q, S , G , d , q 0 , Z 0 , F ), gdje su:

Q konacan skup stanja (kontrole konacnog stanja)

S ulazni alfabet

G alfabet znakova stoga (potisne liste)

d funkcija prijelaza, definirana kao

d : Q ´ ( S È { e }) ´ G ® Q ´ G *

q 0 pocetno stanje, q 0 Î Q,

Z 0 pocetni znak potisne liste, Z0 Î G

F skup završnih stanja, F Í Q,

Definicija 4.6

Konfiguracija stogovnog automata P jest ( q , w, a ) iz Q ´ S ,* ´ G *, gdje su:

q tekuce stanje

w preostali dio ulaznog niza

a niz znakova koji predstavlja sadržaj potisne liste; vrh je prvi znak niza

Pocetna konfiguracija je ( q 0 , w, Z 0 ), a završna konfiguracija ( q , e , a), q Î F , a Î G *.

Definicija 4.7

Pomak stogovnog automata P jest relacija |— p (ili samo |— ako se P podrazumijeva):

(q, aw, Z a ) |— { q ', w, g a )

ako d ( q , a, Z) sadrži ( q ', g ) za q Î Q, a Î S È { e },w Î S *, Z Î G . Kaže se da je ulazni niz w prihvatljiv s P ako

( q 0 , w , Z 0 ) |—* ( q , e , a )

Definicija 4.8

Jezik definiran s P , oznacen s L ( P ), jest skup nizova w prihvatljivih s P . To je opcenito beskontekstni jezik:

L ( P )={ w : w Î S * Ù ( q 0 , w , Z 0 ) |—*(q, e , a ), q Î F, a Î G *}

Primjer 4.9

Stogovni automat koji prepoznaje beskontekstni jezik L ={0 n l n : n ³ l} jest P =({q 0 , q 1 , q 2 }, {0, l}, {$, 0}, d , q 0 , $, {q 0 }), gdje je funkcija prijelaza d definirana sa:

d (q 0 , 0, $) = {(q 1 , 0$)} d (q 1 , 0, 0) = {(q 1 , 00)}

d (q l , l, 0) = {(q 2 , e )} d (q 2 , l, 0) = {(q 2 , e )}

d (q 2 , e , $) = { (q 0 , e ) }

Provjerimo je li ulazni niz w =000111 prihvatljiv:

(q 0 , 000111, $) |— (q 1 , 00111, 0$)

|— (q 1 , 0111, 00$)

|— (q 1 , lll, 000$)

|— (q 2 , ll, 00$)

|— (q 2 , 1, 0$)

|— (q 2 , e , $)

|— (q 0 , e , e )

Dakle, niz 000111 je prihvatljiv.

Opcenito je stogovni automat nedeterministicki. U tom slucaju, da bi automat prihvatio ulazni niz, mora proci kroz sve moguce prijelaze dok ne dosegne završno stanje. Na primjer, konstruirajmo automat koji ce prepoznavati beskontekstni jezik L ={ww R : w Î {a,b} + }.To ce biti stogovni automat P =({q 0 , q 1 , q 2 }{a, b}{Z, a, b}, d , q 0 , Z, {q 2 }), gdje je:

•  d (q 0 , a, Z)={(q 0 , aZ)}

•  d (q 0 , b, Z)={(q 0 , bZ)}

•  d (q 0 , a, a)={(q 0 , aa), (q 1 , e )}

•  d (q 0 , a, b)={(q 0 , ab)}

•  d (q 0 , b, a)={(q 0 , ba)}

•  d (q 0 , b, b)={(q 0 , bb), (q 1 , e )}

•  d (q 1 , a, a)={(q 0 , e )}

•  d (q 1 , b, b)={(q 1 , e )}

•  d (q 1 , e , Z)={(q 2 , e )}

P ce inicijalno prenijeti dio svog ulaza u stog, prema pravilima (1), (2), (4) i (5) i prvim alternativama pravila (3) i (6). Nedeterminizam je u pravilima (3) i (6). Na primjer, ako je ulazni niz abba, P može naciniti sljedece nizove premještanja:

(1) (q 0 , abba, Z) |— (q 0 , bba, aZ)

|— (q 0 , ba, baZ)

|— (q 0 , a, bbaZ)

|— (q 0 , e , abbaZ)

(2) (q 0 , abba, Z) |— (q 0 , bba, aZ)

|— (q 0 , ba, baZ)

|— (q 1 , a, aZ)

|— (q 1 , e , Z)

|— (q 2 , e , e )

Buduci da niz premještanja (2) okoncava u završnoj konfiguraciji, odnosno u završnom stanju q 2 , P prihvaca ulazni niz abba.

Definicija 4.9

Prošireni stogovni automat je uredena sedmorka P =(Q, S , G , d , q 0 , Z 0 , F), gdje je funkcija prijelaza definirana kao d : Q ´ ( S È { e }) ´ G * ® Q ´ G *. Znacenje ostalih simbola je nepromijenjeno.

Primjer 4.10

Definirajmo prošireni stogovni automat jezika L ={ww R : w Î {a,b}*}. To ce biti P =({p, q}{a, b}{a, b, S, Z}, d , q, Z, {p}), gdje je funkcija prijelaza:

(1) d (q, a, e ) = {(q, a)}

(2) d (q, b, e ) = {(q, b)}

(3) d (q, e , e ) = {(q, S)}

(4) d (q, e , aSa) = {(q, S)}

(5) d (q, e , bSb) = {(q, S)}

(6) d (q, e , SZ) = {(p, e )}

Za ulazni niz aabbaa P ce naciniti sljedeci niz premještanja:

(q, aabbaa, Z) |— (q, abbaa, aZ)

|— (q, bbaa, aaZ)

|— (q, baa, baaZ)

|— (q, baa, SbaaZ)

|— (q, aa, bSbaaZ)

|— (q, aa, SaaZ)

|— (q, a, aSaaZ)

|— (q, a, SaZ)

|— (q, e , aSaZ)

|— (q, e , SZ)

|— (q, e , e )

Najprije se prednji dio ulaznog niza premješta u stog. Potom se oznaka sredine, S, postavlja na vrh stoga. P zatim smješta sljedeci simbol ulaznog niza u stog i zamjenjuje aSa ili bSb sa S u listi. P nastavlja na isti nacin sve dok se ne iskoristi cijeli ulazni niz. Ako je SZ ostalo u listi, P briše SZ i unosi završno stanje.

Definicija 4.10

Neka je P =(Q, S , G , d , q 0 , Z 0 , F) stogovni ili prošireni stogovni automat. Kaže se da je niz w Î S * prihvatljiv automatom P s praznom potisnom listom ako je (q 0 , w , Z 0 ) + |— (q, e , e ) za neki q Î Q. Skup prihvatljivih nizova oznacujemo s L e ( P ).

Teorem 4.1

Neka je G =( N , T , P , S ) beskontekstna gramatika. Iz G se može defmirati stogovni automat R tako da je L e ( R ) = L ( G ).

Dakako, važno je upamtiti što teorem 4.1 tvrdi, dok nas njegov dokaz ne zanima. Dalje, valja primijetiti da za automat s praznom stogovnom listom ne trebamo imati nijedno završno stanje, jer su prazna potisna lista i prazan neprihvaceni dio ulaznog niza uvjeti okoncanja postupka prihvacanja, bez obzira u kojem se stanju kontrola završnog stanja zatekla.

Primjer 4.11

Definirajmo stogovni automat R tako da je L e ( R ) = L ( R ), gdje je G gramatika aritmetickih izraza:

E ® T | T+E

T ® F | T*F

F ® (E) | a

Stogovni automat ce biti R =({q}, S , G , d , q, Z, Æ ), gdje je skup završnih stanja prazan, a funkcija je prijelaza 5 definirana sa:

(1) d (q, e , E) = {(q, E+T), (q, T)}

(2) d (q, e , T) = {(q, T*F), (q, F)}

(3) d (q, e , F) = {(q, (E)), (q, a)}

(4) d (q, a, a) = {(q, e )}

(5) d (q, +, +) = {(q, e )}

(6) d (q, *, *) = {(q, e )}

(7) d (q, (, () = {(q, e )}

(8) d (q, ), )) = {(q, e )}

Na primjer, za ulazni niz a+a*a R ce, izmedu ostalog, naciniti sljedeca premještanja:

(q, a+a*a, E) |— (q, a+a*a, E+T)

|— (q, a+a*a, T+T)

|— (q, a+a*a, F+T)

|— (q, a+a*a, a+T)

|— (q, +a*a, +T)

|— (q, a*a, T)

|— (q, a*a, T*F)

|— (q, a*a, F*F)

|— (q, a*a, a*F)

|— (q, *a, *F)

|— (q, a, F)

|— (q, a, a)

|— (q, e , e )

U prethodnom je primjeru niz premještanja koje je nacinio stogovni automat prihvacajuci ulazni niz ekvivalentan krajnjem izvodenju slijeva recenice a+a*a pocevši s pocetnim simbolom E. Takva vrsta analize naziva se "silazna (top-down) sintaksna analiza" ili "predikatna analiza". Detaljnije o sintaksnoj analizi napisano je u sljedeca tri poglavlja.

Pitanja i zadaci

• 1) Definirajte konacni automat ekvivalentan sljedecim regularnim izrazima:
  • a) (0.) + ( (1+2+3+4+5+6+7+8+9) (0+1+2+3+4+5+6+7+8+9)*.) (0+1+2+3+4+5+6+7+8+9) +
  • b) (11+a)* ( e +0 + 00)
  • c) (1+2 + 3 + 4 + 5 + 6+7 + 8 + 9) (0 + 1+2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)*
  • d) (a+b) *aa(a+b) *
  • e) {0,1}* bez podniza 101


• 2) Dana je regularna G gramatika s produkcijama:
  • S ® 0A | 1S | e
  • A ® 0B | 1A
  • B ® 0S | 1B
• Definirajte:
  • a) Regularni izraz koji oznacuje skup nizova ekvivalentan jeziku L ( G ).
  • b) Konacni automat M koji ce prepoznavati taj jezik


• 3) Imena konstanti, varijabli, funkcija i procedura u Turbo Pascalu pišu se tako da moraju poceti slovom (velikim ili malim) engleskog alfabeta ili podcrtom (znak _), potom, ako je duljina imena veca od 1, može slijediti slovo, brojka ili podcrta. Definirajte prvo gramatiku imena Turbo Pascala i iz nje izvedite konacni automat koji ce ih prepoznavati.


• 4) Koristeci se primjerom 4.6 i 4.7 napišite regularne izraze koji ce oznacivati nizove znakova koji predstavljaju prirodne brojeve djeljive s 3, 4 i 6.


• 5) Definirajte generator i regularnu gramatiku jezika:
  • a) Parnih prirodnih brojeva
  • b) Neparnih prirodnih brojeva
  • c) Prirodnih brojeva djeljivih s 5 ,7, 8, 9 i l3


• 6) U primjeru 4.5 izvedena je beskontekstna gramatika koja generira prirodne brojeve djeljive s 3. Iz primjera 4.5 slijedi da je jezik prirodnih brojeva djeljivih s 3 regularan. Izvedite regularnu gramatiku jezika prirodnih brojeva djeljivih s 3 iz tablice prijelaza primjera 4.5.


• 7) Definirajte stogovni automat gramatike:
  • E ® E+E | E*E | (E) | a

Sadržaj