Diskretne Matematicke Strukture

SADRŽAJ 1. UVOD...................................................................................................................................................................2 1.1. RELACIJA. OPERACIJA. FUNKCIJA.........................................................................................................................2 1.2. OSNOVNI POJMOVI LOGIKE...................................................................................................................................4 2. MATEMATIČKA LOGIKA..............................................................................................................................5 2.1. ISKAZNI RAČUN..................................................................................................................................................5 2.1.1. Iskazna algebra.....................................................................................................................................5 2.1.2. Iskazna formula i njena vrijednost........................................................................................................6 2.1.3. Prekidačke mreže..................................................................................................................................8 2.1.4. Bool-ove funkcije...................................................................................................................................9 2.1.5. Izvođenje zaključaka...........................................................................................................................11 2.5. PREDIKATSKI RAČUN (KVANTIFIKATORSKI RAČUN).................................................................................................12 2.5.1. Predikatske formule.............................................................................................................................12 2.5.2. Pojavljivanje promjenjivih u predikatskoj formuli..............................................................................13 2.5.3. Interpretacija predikatske formule......................................................................................................14 2.5.4. Istinitosna vrijednost predikatske formule..........................................................................................15 3. ALGEBARSKE STRUKTURE.......................................................................................................................16 3.1. GRUPA...........................................................................................................................................................17 3.1. PRSTEN. TIJELO. POLJE. BOOL-OVA ALGEBRA......................................................................................................18 4. RELACIJSKE STRUKTURE.........................................................................................................................19 4.1 PARCIJALNO UREĐENI SKUP.................................................................................................................................19 4.2 SUPREMUM. INFIMUM. REŠETKA..........................................................................................................................20 5. OSNOVI TEORIJE GRAFOVA.....................................................................................................................20 5.1 DEFINICIJA GRAFA.............................................................................................................................................20 Elementi skupa X su čvorovi , a elementi skupa ρ grane (ivice) grafa.....................................................21 5.2. MATRIČNA INTERPRETACIJA GRAFA.....................................................................................................................23 5.3 PUTEVI U GRAFU ..............................................................................................................................................23 5.4 NEKI SPECIJALNI GRAFOVI...................................................................................................................................25 5.5 STABLO (DRVO)................................................................................................................................................26 6. TEORIJA KONAČNIH AUTOMATA..........................................................................................................28 6.1 KONAČNA MAŠINA............................................................................................................................................28 6.2 KONAČNI AUTOMAT...........................................................................................................................................32 7. FORMALNI JEZICI. GRAMATIKE.............................................................................................................34 7.1 FORMALNI JEZICI...............................................................................................................................................34 7.2 GRAMATIKE.....................................................................................................................................................35 7.3 VEZA IZMEĐU AUTOMATA I REGULARNIH GRAMATIKA..............................................................................................37

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

1. Uvod 1.1. Relacija. Operacija. Funkcija Def. Uređena n-torka (x1, x2,..., xn) je niz elemenata čiji se redoslijed tačno zna. Primjer: (a, b) je uređena dvojka.

Def. (x1, x2,..., xn) = (y1, y2,..., yn) ako je x1 = y1, x2 = y2,..., xn = yn. Def. Dekartov (direktni) proizvod skupova A1, A2,...,An je skup A1 × A2 × ...× An = {( a1 ,a2 , ,an ) ai ∈ Ai , i = 1,2,...,n}.

n Specijalno, A × A × ... × A = A = {( a1 , a 2 ,  , a n ) a i ∈ A, i = 1,2,..., n}. 2 Primjeri: R = {( x, y) x, y∈R} - realna ravan R3 = {( a,b,c) a,b,c ∈R} - realni prostor

Def. f je binarna relacija nad skupovima A i B, ako je

f ⊆ A× B .

Ako je

A = B, tada je f binarna relacija nad A. Ako ( x, y) ∈ f , kaže se "x u relaciji f sa y", a piše se x f y. Primjeri:

{

} - krug u ravni sa centrom (0,0)

f = ( x, y ) ∈R 2 x 2 + y 2 < 1

f = {( x, y) ∈ R

2

x < y} - poluravan iznad prave y = x.

Def. f je relacija dužine n nad skupovima A1, A2,...,An ako je f ⊆ A1 × A2 × ...× An . Ako je A1 = A2 = ...= An = A , tada je f relacija dužine n

nad Ako Ako Ako

A. / , to je prazna relacija. je f = 0 je f = A1 × A2 × ...× An , to je univerzalna relacija. je n = 1 tj. f ⊆ A , to je unarna relacija nad A.

Def. Neka su A i B neprazni skupovi. Ako se po nekom pravilu f svakom elementu iz A pridružuje neki element iz B, tada se kaže da je f funkcija koja preslikava A u B.

A

B f

a

U oznaci:

b f : A → B, b = f ( a) ,

a - original, b - slika. A je domen, a f ( A) = { f ( a) a ∈ A} je kodomen. 2

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

y , z ∈B , y = f ( x ) z = f ( x ) ako i , onda y = z. Jednoznačna funkcija f se naziva

Def. f je jednoznačna funkcija ako važi da, za svako x ∈ A i preslikavanje.

Def. Preslikavanje

je "na", ako je f ( A) = B tj. za svako b ∈ B postoji a ∈ A tako da je f ( a ) = b . Preslikavanje f : A → B je "1-1", ako važi: za svako x, y ∈A , ako je f ( x ) = f ( y ) , onda je x = y . Ako je f : A → B i "na" i "1-1", naziva se bijekcija ili uzajamno jednoznačno preslikavanje. A

f : A →B

B

Primjeri: f : N → N , f ( x ) = x +1

nije "na", jeste "1-1" Za f : N → N \ { 1 } , jeste bijekcija -

f ( x) = x 2

f : R →R ,

f : R → { x∈ R x ≥ 0 }

nije "na", nije "1-1"

, jeste "na", nije "1-1"

f : N →N

, jeste "na", jeste "1-1"

Def.

f je binarna operacija nad skupovima A, B, C ako je f preslikavanje A × B u skup C. 3

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE f je operacija dužine n nad skupovima preslikavanje A1 × A2 × × An u B.

FAKULTET A1 , A2 ,  , An , B

ako je f

Za n = 1 , f je unarna operacija. Primjeri:

z =x+y

+ : R2 → R z = x∪ y ∪ : PA × PA → PA

z = −x

operacija promene znaka je unarna.

1.2. Osnovni pojmovi logike Def. Iskaz je rečenica koja ima smisla i koja je ili istinita ili neistinita (ne može biti i jedno i drugo ili ni jedno ni drugo). Iskaz obilježavamo sa P, Q, R, S. Svakom iskazu pridružujemo istinitosnu vrijednost, u oznaci v (P ) ,

 1 ,a k j oeP i s t i n i(t ioTl i ) v( P ) =   0 ,a k j oeP l a`n o ( i ⊥l ,i L ) Primjeri: − Za svaki realni broj x, x 2 = 9 . (iskaz koji je lažan) − Kroz tačku A van prave p prolaze bar dvije različite prave koje ne sijeku pravu p. (aksiom – dogovoreno tačan iskaz u geom. Lobačevskog) − Ova rečenica je lažna (semantički paradoks – circulus vitiosus – nije iskaz)

Def.

Predikat je rečenica koja ima smisla, sadrži jednu ili više promjenjivih i njena istinitost zavisi od konkretnih vrijednosti tih promjenjivih. Primjeri: − x i y su realni brojevi i x 2 + y 2 ≤ 1 (predikat istinit za x = y = 0 , a za x = y =1 je lažan). − Za svaki prirodni broj x, x > y (za y <1 , predikat je istinit, a za y ≥1 je lažno). Od rečenica (iskaza i predikata) se formiraju složenije rečenice upotrebom tzv. logičkih operacija. Istinitosna vrijednost novih rečenica zavisi od istinitosnih vrijednosti rečenica koje ih obrazuju i utvrđuju se na osnovu ovih vrijednosti.

4

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Negacija – "ne P" – negacija tačnog iskaza je netačan iskaz, i obrnuto. Konjukcija – "P i Q" – istinita samo ako su i P i Q istinite. Disjunkcija – "P ili Q" – istinita ako je bar jedan od iskaya tačan. Implikacija – "Ako P, onda Q", - lažna je ako je P istinito, a Q lažno, u svim ostalim slučajevima je istinito. "Iz P slijedi Q", "P povlači Q", "P je dovoljan uslov za Q", "Q je neophodan uslov za P", itd. P je pretpostavka, premisa, Q je poslijedica, zaključak. Ekvivalencija – "P ako i samo ako Q" – tačno ako su P i Q oba tačna ili oba netačna. "P je ekvivalentno sa Q", "P akko Q", "P je neophodno i dovoljno za Q". v (P )

v (Q )

1 1 0 0

1 0 1 0

v (neP )

v( P i Q )

0 0 1 1

v ( P ili Q ) v ( ako P onda Q ) v ( P akko Q)

1 0 0 0

1 1 1 0

1 0 1 1

1 0 0 1

2. Matematička logika − Formalizuje postupke dobijanja složenih rečenica od prostih, utvrđivanje istinitosne vrijednosti ovih rečenica u skladu sa pravilima ispravnog logičkog zaključivanja. − Dijeli se na iskazni račun i predikatski račun.

2.1. Iskazni račun − formalizuje pravilno zapisivanje iskaza, građenje novih složenih iskaza, kao i utvrđivanje istinitosne vrijednosti ovih iskaza u zavisnosti od istinitosti iskaza koji ih čine. Da bi se ova formalizacija uspešno izvela, uvodi se pojam iskazne algebre. 2.1.1. Iskazna algebra

Def. Dat je skup { tablicama elmenat

{

0, 1

}

iz

1 0

} i operacije ¬, ∧, ∨, ⇒, ⇔ definisane sljedećim

¬

0 1

elemenat

{

0, 1

0, 1

}

(1, 1)

iz

∧

∨

⇒

⇔

1

1

1

1

2

5

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE (1, 0) (0, 1) (0, 0)

0 0 0

1 1 0

0 1 1

FAKULTET 0 0 1

Skup { 0, 1 } snabdjeven operacijama ¬, ∧, ∨, ⇒, ⇔ je iskazna algebra. Operacije iskazne algebre mogu, u opštem slučaju, biti bilo koje operacije sa prethodnim tablicama. One ovde nose oznake logičkih operacija, jer logičke operacije imaju iste tablice nad skupom {istinito, neistinito}. Uobičajene oznake za operacije: 1 ∧1 = 1 , 1 ⇒ 0 = 0 2.1.2. Iskazna formula i njena vrijednost Simboli iskazne algebre: − − −

promjenjive iskazne algebre: p, q, r, p1 , q1 , r1 ,  , p n , q n , rn ,  simboli operacija: ¬, ∧, ∨, ⇒, ⇔ pomoćni simboli: (, ).

Def.

Iskazna formula je niz sastavljen od iskaznih slova, simbola operacija i zagrada koji je formiran prema sljedećim konvencijama formalnog zapisivanja: 1. Iskazna slova su formule 2. Ako su A i B iskazne formule, tada su i ¬A, ( A ∧ B ), ( A ∨ B ), ( A ⇒B ), ( A ⇔B ) iskazne formule. 3. Iskazne formule se jedino obrazuju konačnom primjenom 1. i 2. Primjeri: p, ¬p, ( p ∨q ), (( ¬p ⇒q ) ∧¬( r ∨q )) - pravilno p¬, ) p ∨q, p ⇒∨q - nepravilno

−

spoljašnje zagrade mogu se izostaviti

−

unutrašnje zagrade mogu se izostaviti u skladu sa sljedećim

prioritetima operacija: ¬( p ∧ q) ∨ r ⇒ q .

1)

¬

, 2)

∨,∧ ,

3)

⇒ , 4)

⇔ . Npr.

n

−

( A1 ∧ A2 ∧  ∧ An − 1 ) ∧ An = A1 ∧ A2 ∧  ∧ An = ∧ Ai

−

( A1 ∨ A2 ∨  ∨ An −1 ) ∨ An = A1 ∨ A2 ∨  ∨ An = ∨ Ai

i=1 n

i =1

Iskazna formula za iskaznu algebru predstavlja ono što predstavlja algebarski izraz za algebru brojeva.

6

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Vrijednost iskazne formule A, v ( A) , dobija se kada u A svaku promjenjivu zamjenimo sa nekom vrednošću iz { 0,1 } i izvršimo sve naznačene operacije. Kao rezultat se dobije 1 ili 0 koje predstavlja vrijednost formule A za odgovarajuće vrijednosti promjenjivih. Primjer: (( ¬p ⇒ q ) ∧ ¬( r ∨ q )) za p = q = 1, r = 0 v (( ¬p ⇒ q ) ∧ ¬( r ∨ q )) = (( ¬1 ⇒ 1) ∧ ¬( 0 ∨ 1)) = ( 0 ⇒ 1) ∧ ¬1 = 1 ∧ 0 = 0

Ovakva formalizacija omogućava istinitosnih vrijednosti složenih iskaza:

jednoznačno

izračunavanje

Ako sada u iskaznoj algebri promjenjive p, q, r smatramo iskazima, operacije ¬, ∧, ∨, ⇒, ⇔ označavaju odgovarajuće logičke operacije, a 0 znači “lažno“ i 1 znači “istinito“, tada iskazne formule predstavljaju pravilno zapisane složene iskaze. Istinitosna vrijednost ovakvog složenog iskaza se dobija kao vrijednost njemu odgovarajuće iskazne formule na sljedeći način: Svaki se iskaz u formuli zamjeni svojom istinitosnom vrednošću pa se izračuna vrijednost formule kao u iskaznoj algebri. Vrijednost formule predstavlja istinitosnu vrijednost iskaza. Tako se izračunavanje istinitosnih vrijednosti složenih iskaza svodi na izračunavanje u iskaznoj algebri. Primjer: Data su dva trougla ∆ ABC i ∆ A1B1C1. Ako je α = α 1 i AB = A1B1, tada su trouglovi ∆ ABC i ∆ A1B1C1 podudarni ako i samo ako je β = β1 . Formalizacija: p: α = α 1 , q: AB = A1B1, r: ∆ ABC ≅ ∆ A1B1C1, s: β = β1 Odgovarajuća formula iskazne algebre: ( p ∧ q ) ⇒ ( r ⇔ s) za p = q = r = s = 1 , v (( p ∧ q ) ⇒ ( r ⇔ s)) = (1 ∧ 1) ⇒ (1 ⇔ 1) = 1 ⇒ 1 = 1 za p = q = 1, r = 1, s = 0 , v(( p ∧ q ) ⇒ ( r ⇔ s )) = (1 ∧ 1) ⇒ (1 ⇔ 0) = 1 ⇒ 0 = 0

Def. Tautologija je iskazna formula koja za sve moguće vrijednosti

svojih promjenjivih ima vrijednost 1. (Tautologija predstavlja zakone pravilnog formalnog zaključivanja.) Neke poznate tautologija 1.

p⇒ p

2.

p ∨ ¬p

(isključenje trećeg)

3.

¬( p ∧¬p )

(neprotivurečnost)

4.

¬¬p ⇔ p

(dvojna negacija)

(refleksivnost)

7

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

5.

( p ⇒ q) ∧ ( q ⇒ r ) ⇒ ( p ⇒ r )

(tranzitivnost za ⇒ )

6.

( p ⇒ q ) ⇔ ( ¬q ⇒ ¬p )

(kontrapozicija)

7.

( p ⇔ q ) ∧ (q ⇔ r ) ⇒ ( p ⇔ r )

8.

p∨ p ⇔ p, p∧ p ⇔ p

(tranzitivnost za ⇔ ) (idempotencija za ∨, ∧)

9.

p∨ q ⇔ q∨ p, p∧ q ⇔ q∧ p

(komutativnost za ∨, ∧)

10.

( p ∨ q) ∨ r ⇔ p ∨ (q ∨ r ) ( p ∧ q ) ∧ r ⇔ p ∧ (q ∧ r )

(asiocijativnost za ∨, ∧)

p ∨ ( p ∧ q) ⇔ p , p ∧ ( p ∨ q) ⇔ p 11. prema ∨ )

12. 13.

14. 15.

(apsorpcija

p ∨ (q ∧ r ) ⇔ ( p ∨ q ) ∧ ( p ∨ r )

∨

prema

∧, tj.

∧

(distributivnost)

p ∧ (q ∨ r ) ⇔( p ∧ q) ∨ ( p ∧ r )

p ⇒ q ⇔ ¬p ∨ q ¬( p ∨ q ) ⇔¬p ∧¬q

(De Morganovi obrasci)

¬( p ∧ q ) ⇔¬p ∨¬q

( p ⇔ q) ⇔ ( p ⇒ q) ∧ ( q ⇒ p)

Def. Dvije iskazne formule A i B su semantički ekvivalentne ako je A ⇔ B tautologija tj. ako A i B imaju uvijek iste vrijednosti za iste vrijednosti promjenjivih. Piše se A = B.

Sada se u svim tautologijama iz 1. - 15. koje sadrže ⇔, znak ⇔ može zamjeniti sa =. 2.1.3. Prekidačke mreže

¬

¬

Samo one iskazne formule koje sadrže ∨, ∧ i , gdje se javlja neposredno ispred iskaznog slova, mogu se interpretirati kao tzv. prekidačke mreže: Iskazna slova i njihove negacije se interpretiraju kao dvopolni prekidači koji mogu biti otvoreni (kada ne provode struju) i zatvoreni kada provode struju. Ako iskazno slovo ima vrijednost 1, prekidač je zatvoren, a ako je 0, on je otvoren. Ako su A i B formule koje su već prikazane kao prekidačke mreže, tada je - Za A mreža - Za A mreža

∧

B,

∨

B,

A

B A

redna veza paralelna veza

B 8

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Prekidačka mreža sadrži redno ili paralelno vezane prekidače, pri čemu su svi prekidači označeni istim slovom istovremeno uključeni ili isključeni. Prekidač sa oznakom p je uključen akko je prekidač sa p isključen i obrnuto.

¬

Prekidačka mreža provodi struju ako odgovarajuća formula ima za odgovarajuće vrijednosti slova (tj. stanje prekidača) vrijednost 1. Tautologijama odgovara prekidačka mreža koja provodi uvijek struju bez obzira na stanje svojih prekidača. Ako je A = B, tada su odgovarajuće prekidačke mreže ekvivalentne tj. za iste položaje svojih jednako označenih prekidača obe provode ili ne provode struju. Primjeri. p ∧ (¬p ∨ q) = p ∧ q

a)

¬p

p

p q b)

q

(( ¬p ∨ q) ∧ (¬p ∨ ¬q )) ∨ p = p ∨ ¬p - tautologija

p

p

¬p

¬p

q

¬q

¬p 2.1.4. Bool-ove funkcije

Def. Svako preslikavanje {

0,1

}

n

→ { 0,1

} , n ∈ N , je Bool-ova funkcija.

Svaka iskazna formula je jedna Bool-ova funkcija čiji je broj promjenjivih jednak broju različitih iskaznih slova koje formula sadrži, tj. svakoj iskaznoj formuli F odgovara Bool-ova funkcija f tako da je v ( F ) = f ( p1 , p 2 , , p n ) za sve vrijednosti iskaznih slova p1 , p2 , , p n iz formule F. Bool-ove funkcije jedne promjenjive p α α α α α 3 odgovara negaciji 1 2 3 4 1 1 1 0 0 0 1 0 1 0

¬

Bool-ove funkcije dvije promjenjive (ima ih 2 2 = 16 ) 2

9

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE p 1 1 0 0

q 1 0 1 0

β

β

β

β

β

1

2

5

1

1

0

6

1 1 1 1

1 1 1 0

1 0 1 1

0 1 1 0

0 0 0 0

FAKULTET

Za svaku Bool-ovu funkciju f postoji iskazna formula F tako da je v ( F ) = f ( p1 , p 2 , , p n ) . O tome govori sljedeći stav:

10

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Teorema. Neka je f ( p1 , p2 , , p n ) proizvoljna Bool-ova funkcija i B = { ( e , e ,  , e ) ∈{ 0,1 } f ( e , e , , e ) = 1 } i n

1

1

2

n

B2 = { ( e1 , e2 , , en ) ∈{ 0,1

Tada je 1.

}

1

n

2

n

f ( e1 , e2 , , en ) = 0

},i

p i0 = ¬p i , pi1 = pi .

∨ ∧

  e1 e1 en   B1 ≠ 0/ , f ( p1 , p2 , , pn ) = v ( p1 ∧ p 2 ∧ ∧ pn )  ( e1 ,e2 ,,en )∈ B1 

Za

- savršena disjunktivna normalna forma 2.

  B2 ≠ 0/ , f ( p1 , p 2 ,  , p n ) = v ( p1¬ e1 ∨ p 2¬ e1 ∨  ∨ p n¬ en )   ( e ,e ,,e )∈ B   12 n 2 

Za

- savršena konjuktivna normalna forma. Primjer: p

q

β

β 5 je implikacija

5

1 1 0 0

1 0 1 0

1 0 1 1

B1 = { (11 , ), ( 0,1), ( 0,0),

B2 = { (1,0 )

}

}

β 5 = ( p 1 ∧ q1 ) ∨ ( p 0 ∧ q 1 ) ∨ ( p 0 ∧ q 0 ) β 5 = ( p ∧ q ) ∨ ( ¬p ∧ q ) ∨ ( ¬p ∧ ¬q )

β 5 = p ¬1 ∨ q ¬ 0 = p 0 ∨ q 1 = ¬ p ∨ q

Na taj način se svaka Bool-ova funkcija može predstaviti pomoću formule sa , ∨, ∧, pa i pomoću prekidačke mreže.

¬

2.1.5. Izvođenje zaključaka

Def. Formula F je semantička poslijedica skupa formula F ako važi: Za

sve vrijednosti iskaznih slova za koje je v ( H ) =1 za svako H ∈ F , važi da je i v ( F ) =1 . Elementi skupa F su hipoteze formule F, u oznaci F |= F. Za konačan skup F = {F1, F2, ..., Fn}, F1, F2, ..., Fn |= F.

Teorema. F1, F2, ..., Fn |= F ako i samo ako je ( F1 ∧ F2 ∧∧Fn ) ⇒ F tautologija.

Neka pravila zaključivanja: 11

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

p, p ⇒ q |= q 1. - modus ponens (direktni dokaz) Primjer: p: 1988 je deljivo sa 4 p ⇒ q : Ako je N deljivo sa 4, tada je godina N prestupna |= q : 1988 je prestupna godina.

2.

p ⇒ q, q ⇒ r |= p ⇒ r

- hipotetički silogizam

Primjer: p ⇒ q : Ako je a = 2 , tada je a 2 = 4 q ⇒ r : Ako je a 2 = 4 , tada je a 3 = 4a |= p ⇒ r : Ako je a = 2 , tada je a 3 = 4a p, ¬q ⇒ ¬p |= q - modus tolens (indirektni dokaz) - svođenje na 3. apsurd Primjer: p: U sobi ima 13 ljudi ¬q ⇒ ¬p : Ako sve osobe imaju rođendan različitih meseci, tada u sobi ima ne više od 12 osoba |= q : Dvije ili više osobe imaju rođendan istog meseca

4. p⇒ q ,  q⇒ p |= p ⇔ q - ekvivalencija Primjer: Trougao je jednakostraničan akko su mu svi uglovi jednaki

2.5. Predikatski račun (kvantifikatorski račun) − formalizuje pravilni način zapisivanja predikata nekog matematičkog ili drugog jezika, određivanje istinitosne vrijednosti predikata. Pri tome se ulazi u sadržaj rečenica koje ulaze u sastav predikata. 2.5.1. Predikatske formule Osnovni simboli kvantitativnog računa: 1. 2. 3. 4.

promjenjive: x, y , z, x1 , y 1 , z1 ,  , x n , y n , z n ,  konstante: a , b, c, a1 , b1 , c1 ,  , a n , bn , c n ,  operacijski simboli: f , g , h, f 1 , g 1 , h1 ,  , f n , g n , hn ,  relacijski simboli: α, β , γ , α1 , β1 , γ 1 ,  i

5.

simboli logičkih operacija i kvantifikatori:

6.

pomoćni simboli: male zagrade i zarezi.

¬ , ∧ ,∨ ,⇒ , ∀ , ∃ .

∀ : univerzalni kvantifikator, “bilo koji“, “svaki“, “ma koji“ 12

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

∃: egzistencijalni kvantifikator, “postoji bar jedan“, “postoji neki“. Formalizacija pravilnog zapisivanja predikata

Def. Izraz je niz promjenjivih, konstanti, operacijskih simbola, zagrada i zareza koji se formira prema sljedećim konvencijama: 1. Konstante i promjenjive su izrazi (termi) 2. Ako su t1 , t 2 , , t n izrazi, a f operacijski simbol dužine n, tada je f ( t1 , t 2 , , t n ) izraz 3. Izrazi se dobijaju samo pomoću konačno mnogo primjena 1. i 2. Primjeri: x , a, f ( x ), g ( x , y ), g( g( x , a )), f ( g ( x ), g ( h ( x , y ))) Ako je f operacijski simbol dužine 1, tada se, umesto f ( x ) , može pisati f x, a ako je f operacijski simbol dužine 2, tada se, umesto f ( x , y ) , može pisati x f y.

Def. Ako su t1 , t 2 , , t n izrazi i α relacijski simbol dužine n, tada je α( t1 , t 2 , , t n ) elementarna formula.

Ako je α relacijski simbol dužine 2, tada se, umesto α( x , y ) , može pisati x α y. Primjeri: α( x , y ), α( f ( x , y )), α( f ( x , y ), a ), α( x , y , f ( x ), z )

Def. Predikatska formula se definiše prema sljedećim konvencijama: 1. 2.

Elementarna formula je predikatska formula Ako su A i B predikatske formule i x promjenjiva, tada su

( ¬A), ( A ∨ B ), ( A ∧ B ) ,

( A ⇒ B),( A ⇔ B),(∀ x ) A,( ∃ x ) A

predikatske

formule 3. Predikatske formule se dobijaju samo pomoću konačno mnogo primjena 1. i 2. U predikatskoj formuli mogu se izostaviti spoljašnje zagrade, a i neke unutrašnje prema prioritetu logičkih operacija. Primjeri: (a)

( ∀x )( ∀y )( α( x , y ) ⇒α( f ( x ), f ( y ))

(b)

( ∀x )α( x , y ) ⇒ ( ∃y )α( x , y )

(c)

α( x , y ) ⇒( ∃z )β( y , f ( x , z ))

2.5.2. Pojavljivanje promjenjivih u predikatskoj formuli

13

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Def. Pojavljivanje promjenjive x u formuli F je vezano, ako je oblika

( ∀x ) ili ( ∃x ) ili ako se x pojavljuje u nekoj formuli A, pri čemu je ( ∀x ) A ili ( ∃x ) A podformula formule F.

Ako pojavljivanje x nije vezano ono je slobodno.

Def.

Slobodna promjenjiva formule F je promjenjiva koja ima bar jedno slobodno pojavljivanje u toj formuli. Vezana promjenjiva formule F je promjenjiva čija su sva pojavljivanja u toj formuli vezana. Primjeri: − − −

Sve promjenjive u formuli (a) su vezane. x, y, iz formule (b) su slobodne promjenjive. x, y su slobodne, a z vezana u formuli (c).

Ako su sve promjenjive u jednoj formuli vezane, tada se ova formula zove zatvorena formula. Takve formule predstavljaju rečenice kojima se može direktno odrediti istinitosna vrijednost, pa one, u stvari, predstavljaju iskaze. Ako su x1 , x 2 , , x n slobodne promjenjive formule F, tada se piše F ( x1 , x 2 , , x n ) . 2.5.3. Interpretacija predikatske formule

Def. Uređen par

( D, ϕ) je interpretacija formule F, ako je

− D neprazan skup koji predstavlja oblast definisanosti svih promjenjivih i konstanti iz formule F, a ϕ preslikavanje koje: − svakoj konstanti iz formule F dodeljuje određen element iz D, − svakom operacijskom simbolu dužine n dodeljuje konkretnu narnu operaciju nad D, − svakom relacijskom simbolu dužine n dodeljuje konkretnu n-arnu relaciju u D. D se naziva domen interpretacije formule F. Primjeri:

( ∀x )( ∀y )α( f ( x , y ), f ( y , x ))

1.

D = R, ϕ : f → +, α →=

( ∀x )( ∀y ) x + y = y + x

2.

D = PA, ϕ : f →∪, α →=

( ∀x )( ∀y ) x ∪ y = y ∪ x

14

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE D = { 0,1

FAKULTET

},ϕ :

f →∧, α →= (∀x )( ∀y ) x ∧ y = y ∧x

3.

Predikat predstavlja predikatsku formulu koja je interpretirana.

Def. Broj slobodnih promjenjivih u jednom predikatu predstavlja dužinu tog predikata. Predikat dužine 0 predstavlja iskaz. 2.5.4. Istinitosna vrijednost predikatske formule Istinitosna vrijednost predikatske formule može se odrediti samo ako je ta formula interpretirana tj. istinitosna vrijednost formule zavisi od njene interpretacije i vrijednosti njenih slobodnih promjenjivih. Formalizovani postupak utvrđivanja istinitosne vrijednosti: 1. Ako interpretirana formula ima dužinu 0, njena istinitosna vrijednost se određuje direktno ulaženjem u sadržaj rečenice. 2. Ako je dužina interpretirane formule veća od 0, treba fiksirati vrijednosti svih slobodnih promjenjivih formule. 3. Za fiksirane vrijednosti slobodnih promjenjivih izračunati vrijednosti svih izraza koji ulaze u formulu (tj. izvršiti naznačene operacije nad konstantama iz D i dobiti kao rezultat konstantu iz D). 4. Odrediti za tako dobijene vrijednosti izraza, vrijednosti elementarnih formula iz formule kao:

 1 v,(t1 ) v,(t2 ) ,, v(tn ) ∈) α . v ( α ( t1 , t 2 , , t n ) =   0 ,d r eu g a c i j

5. Nad vrijednostima elementarnih formula (1 ili 0) izvršiti logičke operacije ¬, ∧, ∨, ⇒, ⇔ ( u domenu iskazne algebre). 6. U slučaju da se u podformulama javljaju kvantifikatori, tada −

v ((∀ x ) A) = v ( A) ,

promjenjivu v (( ∃x ) A) = v ( A) , − promjenjivu − v( (

−

∀ x ) A( x ) )

ako A ne sadrži x kao slobodnu ako

A

ne

sadrži

1 , a k o j e  =  0 , d r u g a c i j 

x

kao

slobodnu

v ( A) = 1z e

 1 , a k v(oA) = j1 ez a db nax ∈ro D j e v( ∃(x ) A( x ) )=   0 , d r ue g a c i j 15

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Primjeri: α( f ( x , y ), z )) ∧α( y , f ( x , z )) ⇒β( y , z ) Interpretacija:

f :+,

α:< , β:=

x+ y< z∧ y< x+z⇒ y = z

Za x = 1, y = 3, z = 2: 1 + 3 < 2 ∧ 3 < 3 ⇒ 3 = 2

v (1 + 3 < 2 ∧ 3 < 3 ⇒ 3 = 2) = v ( 4 < 2 ∧ 3 < 3 ⇒ 3 = 2) = 0 ∧ 0 ⇒ 0 = 0 ⇒ 0 = 1

Za x = 1, y = 2, z = 4: 1 + 2 < 4 ∧ 2 < 1 + 4 ⇒ 2 = 4 v(3 < 4 ∧ 2 < 5 ⇒ 2 = 4 ) = 1 ∧ 1 ⇒ 0 = 1 ⇒ 0 = 0

Def. Formula je tačna pri interpretaciji

( d , ϕ) ako za sve vrijednosti

slobodnih promjenjivih ima vrijednost 1 pri toj interpretaciji.

Def. Formula koja je tačna pri svakoj interpretaciji je valjana formula. 1. Ako se u nekoj tautologiji svaka promjenjiva zamjeni sa nekom predikatskom formulom (istoj promjenjivoj odgovara ista formula), dobija se predikatska formula koja je valjana. Primjeri: F ∨ ¬F , F1 ⇒ F2 = ¬F1 ∨ F2 , F1 ⇒ F2 = ¬F2 ⇒ ¬F1 , itd. 2.

¬ (∀ x ) A( x ) ⇔ (∃ x )¬ A( x )

¬ (∃ x ) A( x ) ⇔ (∀ x )¬ A( x )

(∀ x) ( ∀ y ) A( x , y ) ⇔ (∀ y) ( (∀ x) ( A( x ) ∧ B( x ) ) (∃ x) ( A( x ) ∨ B( x ) )

⇔ (∀ x

⇔ (∃ x

valjane formule

Def.. Formule A i B su semantički ekvivalentne, ako je A ⇔ B valjana formula

3. Algebarske strukture Def. Binarna operacija f u skupu S je zatvorena, ako

(∀x, y ∈S )

xfy ∈S

Osobine zatvorene binarne operacije * u skupu S: 1. (∀x, y ∈ S ) x ∗ y ∈ S = y ∗ x 2. (∀x, y , z ∈S ) ( x ∗ y ) ∗ z = x ∗ ( y ∗ z ) 3. (∃e ∈ S ) (∀a ∈ S ) a ∗ e = e ∗ a element) (N)

(komutativnost) (K) (asocijativnost) (A) (neutralni ili jedinični

(∃e' ∈S )

(e′ - lijevi neutralni element)

(∀a ∈S )

e'∗a = a

(LN) 16

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE (∃e' ' ∈ S ) (∀a ∈ S ) a ∗ e' ' = a element) (DN) 4. (∀a ∈ S ) (∃a −1 ∈ S ) a ∗ a −1 = a −1 ∗ a = e (I)

FAKULTET (e′ ′

-

desni

(inverzni

neutralni element)

Def. Neprazan skup S snabdjeven sa jednom ili više zatvorenih

operacija f1, f2, ..., fn bilo koje dužine naziva se algebarska struktura (ili algebra), u oznaci (S, f1, f2, ..., fn).

3.1. Grupa Def. Specijalno, za n=1, skup S snabdjeven jednom binarnom zatvorenom operacijom je grupoid, u oznaci (S, *). Primjeri: (R,+), (R, • ), (Q,+), (Z, • )

Def. Ako grupoid (S,*) zadovoljava i uslove da je − − − −

* * * *

asocijativna, tada je (S, *) polugrupa, je (A) i (N), tada je (S, *) monoid, je (A), (N), (I), tada je (S, *) grupa, je (A), (K), (N), (I), tada je (S, *) Abelova grupa.

Primjeri: − − − − −

(N, +), (N, •) - komutativni monoidi (PA, ∪), (PA, ∩) - komutativni monoidi (Z, +), (Q, +), (R, +) - Abelova grupa (R\{0},•), (Z\{0},•) - Abelova grupa ({1, -1}, •) - Abelova grupa

Teorema. Ako je (S,*) grupa, njen neutralni element je jedinstven. Dokaz: Ako postoje dva neutralna elementa e1, e2 ⇒ (∀x ∈ S ) ( x ∗ e1 = e1 ∗ x = x ∧ x ∗ e 2 = e 2 ∗ x = x ⇒ e1 = e 2 ∗ e1 = e 2 ⇒ e = e Teorema. Ako je (S,*) grupa, svaki njen element ima jedinstveni inverzni element. Dokaz: Ako postoje dva inverzna elementa a1−1 , a 2−1 elemente a tada je a ∗ a1−1 = a1−1 ∗ a = e ∧ a ∗ a 2−1 = a 2−1 ∗ a = e ⇒ a 1−1 = a1−1 ∗ e = a 1−1 ∗ ( a * a 2−1 ) = ( a 1−1 * a ) * a 2−1 = e ∗ a 2−1 = a 2−1 ⇒ a =a 1

−1 1

2

−1 2

Def. Ako je (S1,*) i (S2,•) dva grupoida, tada su ovi grupoidi izomorfni, ako postoji bijekcija f S1 na S2 tako da važi: (∀x, y ∈ S 1 ) f ( x ∗ y ) = f ( x ) • f ( y ) Primjer:

17

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

(R+, •) je izomorfno sa (R, +), jer postoji bijekcija lnx: R+→R, tako da je ln(x⋅ z)=lnx +lny. Izomorfni grupoidi su iste strukture. Ako je jedan od njih grupa, i onaj drugi mora biti grupa.

3.1. Prsten. Tijelo. Polje. Bool-ova algebra Posmatra se algebarska struktura (S, *, °), gdje su * i ° binarne zatvorene operacije na S. Operacije ° je distributivna u odnosu na *, ako važi (∀x, y , z ∈ S ) ( x ∗ y )  z = ( x  z ) ∗ ( y  z ) (∀x, y , z ∈ S )

x  ( y ∗ z) = ( x  y) ∗ ( x  z)

-(DD) desna distributivnost -(LD) leva distributivnost

Def. (S,*, °) je prsten, ako je

− (S,*) – Abelova grupa, − (S, °) – polugrupa, − ° je distributivna prema *. Ako je ° komutativna operacija, to je komutativan presten. Primjeri: (Z, +, •)

Def. (S,*, °) je tijelo, ako je −

(S,*) – Abelova grupa,

−

(S

−

° je distributivna prema *.

\ { 0} ,° ) –grupa (0 je neutralni element operacije *)

Def. Tijelo (S,*, °) je polje, ako je (S

\ { 0} ,° ) Abelova grupa.

Primjeri: (R, +, °)

Def. (S,*, °) je Bool-ova algebra, ako je − − − operacije −

*,° su (A) i (K). * i ° su obostrano distributivne. postoji neutralni lement e1 operacije * i neutralni elemnt e2 °. (∀x ∈ S )

(∃x ' ∈ S )( x * x ' = e 2 ∧ x  x ' = e1 )

Primjeri: (P, ∪, ∩) i ({0,1}, ∨, ∧) 18

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

4. Relacijske strukture 4.1 Parcijalno uređeni skup Osobine binarne relacije ρ u skupu S: 1. (∀x ∈S ) xρx 2. (∀x, y ∈ S ) x ρ y ⇒ y ρ x (∀x, y ∈ S ) x ρ y ∧ y ρ x ⇒ x = y 3. ili x ≠ y ∧ x ρ y ⇒ ¬y ρ x 4. (∀x, y , z ∈S ) x ρ y ∧ y ρ z ⇒ x ρ z )

- refleksivnost - simetričnost - antisimetričnost - tranzitivnost

ρ je relacija ekvivalnecije, ako zadovoljava 1,2, 4. ρ je relacija poretka, ako zadovoljava 1,3, 4.

Def. Neprazan skup S snabdjeven nekom relacijom poretka ρ naziva se parcijalno uređen skup, u oznaci (S, ρ ). Primjeri: (R, ≤ ) , (P, ⊆), (N, /)

Def. Parcijalno uređen skup (S, ρ ) je lanac ako su mu svaka dva elementa urediva tj. važi. (∀x , y ∈S )

( x ρ y ∨ y ρ z)

Primjeri:

(R, ≤ ) - lanac (N, /), (P, ⊆) – nisu lanci

Def.

Najmanji element a skupa (S, ρ ):(∀y∈S) aρ y. Najveći element a skupa (S, ρ ):(∀y∈S) yρ a. Minimalni element a skupa (S, ρ ): (∃ y∈S) (y≠ a ∧ y≤ a) Maksimalni element a skupa (S, ρ ): (∃ y∈S) (y≠ a ∧ a≤ y). Svaki najmanji (najveći) element je i minimalni (maksimalni). Kod lanca je svaki minimalni (maksimalni) element najmanji (najveći) element. Primjeri:

elementi

(PA, ⊆), A={1, 2, 3}, ∅ je najmanji, a A najveći elemnt. (PA \ {∅, A} , ⊆) - {1}, {2}, {3} - minimalni elementi {1,2}, {1,3}, {2,3} - maksimalni

Teorema. Ako postoje najveći ili najmanji element, oni su jedinstveni Dokaz: Ako postoje dva najveća elementa a1, a2 , tada

( ∀y ∈ S )

y ρ a 1 ∧ y ρ a 2 ⇒ a 2 ρ a1 ∧ a1 ρ a 2 ⇒ a1 = a 2

19

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

4.2 Supremum. Infimum. Rešetka Def. Neka je (S, ρ ) parcijalno uređen skup i S1⊂ S. Tada je a∈S gornja (donja) međa skupa S1, ako je (∀y ∈ S 1 ) y ρ a tj. (∀y ∈ S 1 ) a ρ y Supremum skupa S1 je najmanji element u skupu gornjih međa skupa S1. Infimum skupa S1 je najveći element u skupu donjih međa skupa S1. Primjeri: - (R, ≤ ), S1={-1, 1}: donje međe a≤ -1, inf S1= -1 gornje međe a≥ 1, sup S1= 1 - (N, ⁄ ), gdje je a⁄ b⇔(∃ k∈N) b=ka, S1={12, 30} gornje međe: 60k, k=1,2,.., sup{12, 30}=60 donje međe: 2,3,6 inf{12, 30}=6

Def. Parcijalno uređen skup (S, ρ ) je mreža ili rešetka ako svaka dva njegova elementa imaju supremum i infimum.

Teorema. Svaki lanac je rešetka. Primjeri: a) (N, ⁄ ), sup (a, b) = najmanji zajednički sadržalac (a,b) inf (a, b) = najveći zajednički dijelilac (a,b) b) (S, ρ ) S1 = {0, 2, 6}, ρ = {(0, 0), (2, 0), (6, 0), (2, 2), (2, 6), (6, 6)} S1 = {0, 6}

 donjemeđe : 2, 6, infS1 = 6   gornjameđe : 0, supS = 0   1

S1 = {0, 2}

 donja međe : 2,  gornjameđe : 0, 

S1 = {2, 6}

 donja međe : 2, infS1 = 2    gornja međe : 0, 6 supS 1 = 6

infS1 = 2  supS1 = 0

5. Osnovi teorije grafova 5.1 Definicija grafa 20

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Def. Ako je X neprazan konačan skup i ρ binarne relacije u X, tada se uređeni par G=(x,ρ ) naziva graf. Elementi skupa X su čvorovi , a elementi skupa ρ grane (ivice) grafa.

Geometrijska predstava grafa: − čvorovi grafa iz X se prikazuju kao međusobno različite tačke ravni ili prostora. Ako (x,y)∈ρ , tada odgovarajuće tačke spajamo neprekidnom linijom koja se orijentiše od x ka y. Ako (x,y)∉ ρ , odgovarajuće tačke nisu povezane linijom. Primjer: X = {a , b, c, d }, p = {( a , a ), ( a , b), ( a , c ), ( a , d ), (b, b), (b, d ), ( c, a )} a c

b d

Ivica koja spaja čvor sa samim sobom zove se petlja. Svakoj relaciji se može pridružiti graf kao geometrijska predstava i svakom grafu kao figuri se mogu pridružiti neka binarna relacija u skupu čvorova. Osobine binarnih relacija na grafu: 1. Refleksivnost: svaki čvor grafa ima petlju . 2. Simetričnost: između svaka dva različita čvora gdje postoji ivica, postoji i ivica u suprotnom smeru. 3. Antisimetričnost: svaka dva različita čvora imaju najviše jednu ivicu koja ih spaja. 4. Tranzitivnost: za svaki par nadovezanih ivica (x,y) i (y,z), x postoji ivica (x,z) koja ih zatvara.

y

z

Primjer:

X = {0,2,6}, p = {(0,0), ( 2,0), (6,0), ( 2,2), ( 2,6), (6,6)}

21

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

-Relacija poretka

2

0

FAKULTET

6 Def.

Ako je kod grafa (X, ρ ) relacija ρ antisimetrična , graf je orijentisan. Ako je kod grafa (X, ρ ) relacija ρ simetrična , graf je neorijentisan. Kod neorijentisanog grafa se svi parovi grana koje spajaju čvorove zamjenjuju jedinstvenim neorijentisanim granama. Primjer: zamjenjuje se

c

c a

a

b

b

Postoje i grafovi koji nisu ni orijentisani ni neorijentisani. Primjer:

Postoje i drugačije definicije neorijentisanog grafa:

Def.

Uređeni par (X, U), gdje je X neprazan skup, a U ⊆

{( x, y ), x, y ∈ X } i antisimetrično je, naziva se orijentisani graf.

Uređeni par (X, U), gdje je X neprazan skup, a U ⊆ {( x, y ) , x, y ∈ X } tj. U je podskup skupa neuređenih parova iz X, je neorijentisani graf. Primjeri: (X,U), X = { a, b, c}, U = {(a, a), (a, b), (a, c), (b, c)}

a - neorijentisan graf.

b c

22

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

5.2. Matrična interpretacija grafa Def.

Neka su svi čvorovi nekog grafa (X,ρ ) uređeni po nekom proizvoljnom poretku u niz x1, x2,...,xn. . 1, ( x i x j ) ∈ ρ , Matrica A = a , kod koje je a ij = 0, drugacije  ij

nxm

je matrica susedstva grafa (X, ρ ).

Matrica susedstva neorijentisanog grafa je simetrična tj. aij =aji za svako i,j ∈{1,2,..,n}. Za matricu susedstva orijentisanog grafa važi da je (∀i, j, i ≠ j ) aij=1 ⇒ aji=0. Za aii=1, postoji petlja u čvoru xi . Def. Neka su svi čvorovi i ivice neorijentisanog grafa (X,ρ ) uređeni u nizove x1, x2,..., xn tj. i1,i2,..., im. B=b Matrica , kod 1, ako je x i jedna od krajnjih tacaka ivice i j . b ij =   0, drugacije ij

nxm

koje

je

Primjer: a c

b

a a 1 b 0 A=  c 0 d  0

b 1 0 0 0

c 0 1 0 1

d 1 0  0 0

d a b c

( a , b) a 1 A= b 1  c  0

(a, c) 1 0 1

(b, c ) 0  1   1 

5.3 Putevi u grafu Def. Zadat je graf G=(X,ρ ). Niz ivica iz ρ (x1, x2), (x2, x3), ..., (xn-1, xn) je put dužine n grafa G od x1 do xn. (x1 je početni, a xn završni čvor). Ivice i čvorovi u putu se mogu ponavljati.

23

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Def. Ako se svi čvorovi nekog puta različiti, tada je to elementarni put (prolazi kroz svaki čvor puta samo jedan put). Def. Ako je x1 =xn , tada se put naziva zatvoteni put. Umesto (x1, x2), (x2, x3), ..., (xn-1, xn) piše se x1, x2, ..., xn. Primjer: -

d d b b

-c-e –c–e –d–c –d–c

-f-c–b - nije elementarni put –f–c–b–d - nije elementarni, ali je zatvoren –e–f - otvoren i elementaran – b, e – e, c – e – f –c – zatvoren i elmentaran d

e c

a b

f

Def. Neka je G=(X,U) neorijentisani graf. Niz ivica iz U {x1, x2}, {x2,

x3}, ..., {xn-1, xn} je lanac u G od x1 do xn. (x1 je početni, a xn završni čvor). Ivice i čvorovi u putu se mogu ponavljati. Def. Ako se svi čvorovi lanca različiti, to je elementarni lanac. Def. Ako je x1=xn , lanac se naziva ciklus. Primjer: a, b, c, d, b,

- lanac, ali ne elementarni f, e, b, d - elementarni lanac b, f, e, b, d, c, b - ciklus ali ne elementarni b, c, d, b - elementarni ciklus a

b e f c

d

Def. Ako je (X,ρ ) neorijentisani graf bez petlji, lanac koji prolazi tačno jedan put kroz sve ivice grafa je Euler- ov lanac. (isto važi i za orijentisani graf i Eulerov put) Def. Ako je (X, ρ ) neorijentisani graf, lanac (ciklus) koji kroz sve čvorove prolazi tačno jedan put je Hamiltonov lanac (ciklus). (Isto važi i za orijentisani graf, Eulerov put i Hamiltonov put) Primjeri:

24

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE a

FAKULTET Eulerov put: a-b-c-d-b-f-e-b Hamiltonov put: ne postoji

b c d e

c

f

Nema ni Eulerov ni Hamiltonov put

a b

d

a,b,c,d,f,e,a – Hamiltonov put d,c,b,a,c,e,d,f,e,a,f – Eulerov put

b a

c

e f

d

5.4 Neki specijalni grafovi

Potp un graf

K

Grafciklu s

C

Grafput

P

Nulagraf

N

Svaka dva čvora spojena su ivicom

n

Ivice obrazuju ciklus

n

Ivice obrazuju put

n

Graf sadrži samo čvorove

n

K Potpuni biparitn i graf

n, m

Skup čvorova se može podijeliti na dva skupa, tako da čvorovi u istom skupu nisu spojeni, a svaka dva čvora iz različitih skupova su spojeni

25

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

K 3, 2

K

zvijezda

1, n

Mrež a

Orijentisani graf koji ne sarži ni jedan yatvoreni put niti petlju

5.5 Stablo (drvo) Def. Stablo je neorijentisani graf bez petlji kod koga između bilo koja dva čvora postoji jedinstveni elementarni lanac. Primjeri:

Def. Stablo sa korijenom (ukorijenjeno ili orijentisano stablo) je stablo kod koga postoji specijalno uočeni čvor koji predstavlja korijen.

26

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Primjer: Nivoi a b

c e

d f

g

0

Visina stabla: 3

1 2

h

3

Def. Nivo čvora x nekog stabla je dužina elementarnog lanca od korijena do tog čvora (korijen ima nivo 0). Visina (dužina) stabla je najveći nivo čvora u stablu.

Terminologija u ukorijenjenom stablu Ako je dat elementarni lanac od korijena do nekog čvora, npr. a, b, f, h do h tada je − f roditelj (otac) od h, h je djete (sin) od f, − a, b, f su preci od h, h je potomak od a, b, f, − g i h braća, − ako neki čvor nema djece, zove se list. Ako neki čvor nije list, on je čvor grane.

Def. Čvor x nekog stabla zajedno sa svim svojim potomcima

predstavlja podstablo ovog stabla sa korijenom x. Def. Binarno stablo je ukorijenjeno stablo gdje svaki čvor ima najviše dva djeteta Čvor x nekog (lijevo ili desno).

27

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Primjeri:

Primjeri: Stablo pretraživanja u bazama podataka, gdje se svakom čvoru stabla pridružuje neki podatak, tako da je podatak u lijevom podstablu uvijek “manji” od podataka u desnom podstablu. 17 4 2

23 7

6

O

19 9

A

45 37

A B

u

A N

T

T

99

6. Teorija konačnih automata - formuliše apstraktne modele rada sistema koji se može opisati na sljedeći način: u la z ut

s ta n je st

iz la z it

Sistem se posmatra u diskretnim vremenskim trenucima t (t=0,1,2,…) i u svakom od njih ga karakteriše neko stanje st u kome se nalazi. U svakom trenutku t na ulaz u sistem dolazi neki ulazni signal ut koji izaziva (eventualno) mijenjanje njegovog stanja u stanje s t i na izlazu izlazni signal it. Pošto stanje st i izlaz it zavise, ne samo od ulaza ut već i od prethodnog stanja sistema st-1 na koga ovaj ulaz nailazi, ovakav jedan sistem radi sa nekom vrstom primitivne unutrašnje memorije.

6.1 Konačna mašina

28

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Sada se abstraktni model koji opisuje rad ovakvog sistema može definisati na sljedeći način: Def. Konačna mašina se sastoji od: konačnog skupa U ulaznih simbola, konačnog skupa I izlaznih simbola, konačnog skupa S stanja, funkcije prelaza stanja f:S× U→S, gdje f(s,u)=s′ znači da,ako ulaz u dođe u sistem koji je u stanju s,tada se stanje mijenja u s′ , funkcije izlaza g: S× U→I, gdje g(s,u)=i znači da,ako ulaz u dođe u sistem koji je u stanju s,tada je izlaz i, početnog stanja sistema σ *∈S. Ovakva konačna mašina se označava sa M=(U,I,S,f,g, σ *). Primjer:

U={a,b}, I={0,1}, S={σ 0,σ 1}, σ * =σ

U

f

g

i l i

S a

b

a

b

σ

σ

σ

0

1

0

0

1

σ

σ

σ

1

0

1

1

1

0

f(σ 0,a )= σ 0

g(σ 0,a )= 0

f(σ 0,b )= σ 1 f(σ 1,a )= σ 1 f(σ 1,b )= σ 1

g(σ 0,b )= 1 g(σ 1,a )= 1 g(σ 1,b )= 0

Jedna konačna mašina se može u potpunosti definasati korištenjem takozvanog dijagrama prelaza.

Def. U dijagramu prelaza za konačnu mašinu M=(U,I,S,f,g,σ *) svako

stanjeσ iz S se predstavlja kao neki čvor ovog dijagrama. Od čvora σ 1 do čvora σ 2 postoji orijentisana ivica ako postoji ulaz u, u∈U, takav da važi f(σ 1,u)=σ 2. Ako je, pri tome, g(σ 1,u)=i, ovoj ivici se dodeljuje oznaka u/i. Čvor koji predstavlja početno stanje σ * označen je strelicom. Primjer: ima oblik:

Dijagram prelaza za konačnu mrežu iz prethodnog primjera

a /1

a /0 σ0

b /1

σ1 b /0 29

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Sada se rad konačne mašine M može opisati na sljedeći način: Na ulazu u mašinu se nalazi jedan niz ulaznih simbola (ulazni niz). Polazeći od početnog stanja, svaki od ovih simbola prevodi sistem iz stanja u stanje (u skladu sa funkcijom prelaza) pri čemu se generiše odgovarajući izlazni simbol (u skladu sa funkcijom izlaza). Ovaj niz izlaznih simbola (izlazni niz) se zato može formalno definisati na sljedeći način:

Def. Niz y1, y2, …, yn, je izlazni niz mašine M koji odgovara ulaznom nizu x1, x2, …, xn ako postoji niz stanja σ 0, σ 1,…, σ n,∈ S tako da je σ 0 =σ * σ i = f(σ i-1, xi), i=1,n yi = g(σ i-1, xi), i=1,n

Primjer: Ako je na ulazu konačne mašine iz primjera ni x=aababba, odgovarajući niz stanja kroz koje mašina prolazi je σ 0, σ 0, σ 0, σ 1, σ 1, σ 1, σ 1, σ 1. Odgovarajući izlazni niz je y=0011001. Mnoge operacije koje se više u digitalnom računaru mogu se prikazati kao konačne mašine. Primjer: xt

zt

yt

sa b ira c

c t-1

ct z a s to j

Serijski sabirač sabira dva binarna broja x=0 xn xn-1 …x0 i y=0 yn yn-1 … y0. Na ulazu se u diskretnim vremenskim trenucima t=0,1,…,n+1 nalaze parovi (x0, y0), …,(xn, zn), (0, 0). Stanje sabirača u trenutku t se karakteriše prenosnim bitom ct, tj. prenosom na sljedeće cifarsko mesto pri sabiranju u trenutku t. Sabiranjem binarnih cifara xt, yt i prethodnog stanja ct-1, dobija se kao izlaz binarna cifra zt i mijenja se stanje sabirača u ct. Rezultat sabiranja je izlazni niz zn+1 zn, …,z0. Sabirač se može prikazati kao konačna mašina na sljedeći način: Skupovi ulaznih i izlaznih simbola su U={00,01,10,11} i I={0,1}. Skup stanja je S={σ 0,σ 1}, gdje σ 0 označava da nema prenosa na sljedeće cifarsko mesto, dok σ 1 označava da takav prenos postoji. Sada se dijagram prelaza ove mašine može prikazati kao:

30

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE 0 0 /0

FAKULTET 0 1 /0

0 1 /1 0 0 /1 σ0

1 0 /0 σ1

1 1 /0

1 1 /1

1 0 /1

Ako treba sabrati dva linerna broja x=0010 i y=0111, tada ovom sabiranju odgovara ulazni niz (0,1), (1,1), (1,0), (0,0), a njemu odgovarajući izlazni niz prethodno definisane konačne mašine je z =1001, što je i rezultat sabiranja. Korištenjem konačne mašine se mogu formalno prikazati mnogi postupci koji imaju za cilj da na određeni način prepoznaju unapred zadate osobine ulaznog niza. Primjer:

Konačna mašina definisana dijagramom prelaza: 1 /0

0 /0

0 /0

1 /0 σ0

1 /1

σ1

1 /1 σ3

σ2

0 /1

0 /0 daje na izlazu 1 čim registruje 101 u ulaznom nizu i nadalje. U ostalim slučajevima daje 0. Međutim, za neke osobine ulaznih nizova, ne mogu se formirati konačne mašine koje bi ih prepoznale. Primjer: Ne postoji konačna mašina koja na ulazu ima niz 0 i 1 i daje izlaz 1 uvijek kada je broj 1 i 0 jednaki, u ostalim slučajevima daje 0. Stvarno, stanja ovakve mašine trebalo bi da budu σ 0 – isti broj 1 i 0 σ 1 – broj 1 veći za 1 od broja 0 σ 2 – broj 1 veći za 2 od broja 0 ° ° °

σ

1

σ

2

′

′

– broj 0 veći za 1 od broja 1 – broj 0 veći za 2 od broja 1 ° ° °

Međutim, trebalo bi da bude beskonačno mnogo stanja, pa konačna mašina ne može da se formira na takvom skupu stanja. 31

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

1 /0

1 /0 σ0

σ1

0 /1

σ2

0 /0

...

1/ 1 0/ 0

σ 1′

1/ 0 0/ 0

σ 2′

...

6.2 Konačni automat Specijalni slučaj konačne mašine su konačni automati. Oni su od posebnog ineresa, jer su vezani za formalne jezike i gramatike.

Def.1 Konačni automat A=( U,I,S,f,g,σ *) je takva konačna mašina kod koje je I={0, 1} i gdje je izlaz određen sljedećim stanjem mašine.

Drugim rečima, kod konačnih automata važi da, bilo kako došli u neko stanje, daju uvijek isti izlaz tj. u njihovom dijagramu prelaza sve ivice koje ulaze u isto stanje imaju isti izlaz. Primjer: a /1

b /0 a /1

a /1 σ0

b /0

σ1

σ2

b /0 U ovoj konačnoj mašini za svako stanje važi da sve ivice koje ulaze u njega imaju isti izlaz. Zato ona predsatvlja konačni automat. Stanja za koja važi da uvijek kada je automat u njima daju izlaz 1 zovu se prihvatajuća stanja. Sada se konačni automat može definisati na drugačiji način: Def.2 Konačni automat A se sastoji od: − konačnog skupa U ulaznih simbola, − konačnog skupa S stanja, − funkcije prelaza stanja f: U× S → S, − podskupa A⊆ S prihvatajućih stanja, − polaznog stanja σ *∈S. U oznaci A= (U,S,f,A,σ *). 32

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

U dijagramu prelaza konačnog automata se prihvatajuća stanja obilježavaju sa , a oznake izlaza se ne navode. a

b a

σ0

σ1

b

Primjer: Konačni automat iz prethodnog primjera se može prikazati kao: a

b a

a σ0

σ1

b

σ2

b Svakom ulaznom nizu konačnog automata A odgovara jedan orijentisani put koji polazi od početnog stanja σ o. Ako se taj put završava u nekom prihvatajućem stanju, tada A prihvata (prepoznaje) taj ulazni niz. Pojam prihvaćenog ulaznog niza može da se definiše na sljedeći način:

Def. Automat A=(U,S,f,A,σ *) prihvata (prepoznaje) ulazni niz x1, x2 , … , xn, ako postoji niz stanja σ o,σ 1,…, σ n,takvih da je σ o=σ * f(σ i-1 xi)= σ i, i = B = b σ n∈ A. ij n x m

Skup svih ulaznih nizova koje automat A prepoznaje označava se sa Ac(A). Primjer: Konačni automat iz prethodnog primjera prihvata ulazni niz aabbba, jer se odgovarajući niz stanja završava sa σ 1. Ovaj automat ne prihvata baabbabb, jer se odgovarajući niz stanja završava u σ o . Konačni automat je u suštini jedan algoritam koji odlučuje da li je ili ne zadati niz prihvatljiv. Često treba naći takav konačni automat koji prepoznaje (prihvata) sve nizove sa tačno određenim osobinama i samo njih. Primjer: Automat koji prepoznaje sve nizove nad skupom {a, b} koji sadrže neparan broj a može se definisati sljedećim dijagramom prelaza. 33

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET b

b a σ0

σ1

a

gdje σ o označava stanje u kome je broj a paran, a σ broj a neparan.

1

stanje u kome je

Def. Dva konačna automata A i A′ su ekvivalentna ako prepoznaju isti skup nizova tj. Ac(A) =Ac(A′ ) Primjer: Dva automata a

b a

σ0

σ1 b

b σ0

a

σ1

b a

a

σ2

i

b

su ekvivalentna, jer oba prepoznaju nizove koji se sastoje samo od b.

7. Formalni jezici. Gramatike 7.1 Formalni jezici U opštem slučaju jezik je skup reči i metoda za njihovo kombinovanje koji se koristi i "razume" od strane određene zajednice. Pravila formiranja reči u ovakvim prirodnim jezicima su veoma kompleksna i teška za karakterizaciju. Formalni jezici i gramatike modijeliraju i formalno opisuju prirodne jezike i pravila formiranja njihovih reči, a u cilju lakše komunikacije sa računarom. Def. Neka je A neki konačan skup. Formalni jezici L nad azbukom A je poskup od A*, gdje je A* skup svih nizova (reči) nad A.. Primjer: Za A={a,b}, jezik L može da sadrži skup svih nizova nad A koji imaju neparan broj a tj. L= {a, ab, ba, abb, bab, bba,...} 34

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

7.2 Gramatike Def. Gramatika G se sastoji od: − konačnog skupa N nezvršnih slova, − konačnog skupa T završnih slova, gdje N∩ T=∅ − konačnog podskupa P⊂[(N∪ T)*-T*]× (N∪T)* koji se naziva skup pravila izvođenja − polaznog slova σ *∈N. U oznaci G=(N,T,P, σ *) Ako (A,B)∈P, tada se to često označava sa A→B. A∈(N∪T)*-T* i B∈(N∪T)* tj. A i B su nizovi koji se sastoje od nezavršnih i završnih slova tako da A mora da sadrži bar jedno nezavršno slovo, dok B može da se sastoji samo od završnih. Polazaći od zadate gramatike G može se generisati neki jezik tj. koristeći pravila ove gramatike mogu se izvesti nizovi (reči) ovog jezika. Def. Zadata je gramatika G =(N,T,P,σ *). Ako je α→ β neko njeno pravilo, tj. (α ,β )∈P, i xα y∈(N∪ T)*, tada je xβ y direktno izvodivo iz xα y, u oznaci xα y⇒ xβ y. Ako α i∈(N∪ T)* za i= 1, n i α i⇒α i+1 za i= 1, n −1 , tada jeα n •

izvodivo iz α 1, u oznaci α 1 ⇒ α n. Jezik L(G) generisan gramatikom G, L(G) je skup svih nizova nad T izveden iz σ *. Primjer 1: Gramatika G= (N, T, P, σ *) je zadata sa N={σ *, S}, T={a, b} i P={σ *→bσ *, σ *→aS, S→bS, S→b}. Na osnovu pravila S→bS niz abSbb je direktno izvodiv iz aSbb tj. aSbb⇒ abSbb. •

Takođe, σ * ⇒ bbab pomoću niza izvođenja σ *⇒ bσ *⇒ bbσ *⇒ bbaS⇒ bbab. Odredimo opšti oblik reči nad T izvedene iz početnog slova σ * ove gramatike: σ *⇒ bσ *⇒ ... ⇒bnσ *⇒ bnaS⇒ bnabS⇒ ... ⇒ bnabmS⇒ bnabm+1, za m≥ 0 i n≥ 0, gdje bk označava k uzastopnih pojavljivanja slova b u reči. To znači da jezik L(G) generisan gramatikom G sadrži sve reči ovoga oblika i samo njih tj. sadrži sve one nizove nad {a,b} koji sadrže samo jedno a a završavaju se sa b.

35

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Napomenimo da je u opštem slučaju za zadatu bilo kakvu gramatiku G teško naći oblik opšteg člana njenog jezika L(G). Osnovu jedne gramatike čine njen skup pravila izvođenja. Pomoću ovih pravila se, polazeći od početnog slova i koristeći dva disjunktna skupa slova, izvode reči jezika ove gramatike i to nad skupom završnih slova kao njegovom azbukom. Nezavršna slova služe samo kao pomoćni simboli pri ovom izvođenju. Gramatike i njena pravila mogu se kondenzovanije prikayati pomoću tzv. Backus-ove normalne forme (BNF). Def. U Backus-ovoj normalnoj formi se prikazuju: − nezavršna slova između uglastih zagrada < ...> , − pravila S→T kao S::=T, − pravila S→T1, S→T2,..., S→Tn kao S::=T1T2...Tn. Primjer: Gramatika iz Primjera 1. može se prikayati u obliku BNF kao < σ *>::=b< σ *>a<S> <S>::=b<S>b Mnogi poznati skupovi iz algebre brojeva mogu se prikazati kao jezici generisani određenim gramatikama koje definišu pravila formiranja elemenata ovih skupova. Primjer 2: Ako se cijeli broj shvati kao niz cifara od 0 do 9, ispred koga stoji (neobavezno) + ili -, tada se skup svih cijelih brojeva može smatrati jezikom generisanim sljedećom gramatikom: ::=0123456789 ::= ::= Polazno slovo : Sada se cijeli broj – 980 može izvesti iz početnog slova sljedećim nizom izvođenja: ⇒⇒-⇒⇒-⇒⇒-9 ⇒-98⇒-980. U zavisnosti od oblika pravila neke gramatike postoje tri tipa gramatike (prema klasifikaciji Čomskog): Def. Neka je G=(N, T, P, σ *) neka gramatika i λ prazan niz (reč).

36

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

a) Ako je svako pravilo izvođenja gramatike G oblika α Aβ→ α δ β , gdje je α ,β ∈ (N∪T)*,A∈N, δ ∈ (N∪T)*\ {λ} to je kontekstno zavisna gramatika. b) Ako je svako pravilo izvođenja gramatike G oblika A→ δ za A∈N, δ ∈ (N∪T)*\ {λ} , to je konteksno slobodna (nezavisna) gramatika, c) Ako je svako pravilo izvođenja gramatike G oblika A→α ili A→α B, gdje je A,B∈N, α∈ T*\{λ} , to je regularna gramatika. Svaka regularna gramatika je i kontekstno kontekstno slobodna je i kontekstno zavisna.

slobodna,

a

svaka

Primjer: Gramatika iz Primjera 1. je regularna, a iz Primjera 2. je konteksno slobodna. Def. Jezik L je kontekstno zavisan (slobodan, regularan) ako postoji kontekstno zavisna (slobodna, regularna) gramatika G tako da je L=L(G). Primjer 3: U Primjeru 1 prikazano je da postoji jedna kontekstno slobodna gramatika koja generiše skup cijelih brojeva. Međutim, skup cijelih brojeva može se generisati i sljedećom gramatikom: ::=+- ::=01234567890...9 Polazno slovo : ,

broj> cijeli

gdje je * završno slovo koje označava blanko. Ova gramatika je regularna, pa je zato skup cijelih brojeva jedan regularan jezik. Def. Gramatike G1 i G2 su ekvivalentne, ako je L(G1)=L(G2) . Primjer: Gramatike iz Primjera 2 i 3 su ekvivalentne, jer generišu isti skup – skup cijelih brojeva.

7.3 Veza između automata i regularnih gramatika Može da se pokaže da se za svaki konačan automat A može konstruisati regularna gramatika G tako da se jezik L(G) poklapa se skup A c(A) svih nizova koje taj automat prepoznaje. Tvrdnja: Neka je A=(U,S,f,A,σ *) konačni automat i G=(N, T, P, σ *) gramatika kod koje je N=S, T=U, σ * početno slovo, a skup svih pravila izvođenja P definiše se na sljedeći način: 37

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

− ako f(s,x)=s′ ¸ tada s→x s′∈ P, − ako f(s,x)=s′ i s′∈ A¸ tada s→x s′ , s→x∈P. Tada je skup svih nizova koje prepoznaje automat A jednak jeziku L(G) generisanom gramatikom G. Primjer: Automatu A koji prepoznaje sve nizove nad {a,b} takve da sadrže neparan broj a, zadatom dijagramom prelaza b b a σ0

σ1

a

odgovara sljedeća gramatika G=(N, T, P, σ *): N={σ 0, σ 1}, T={a, b}, σ *=σ 0 i P= {σ 0→aσ 1, σ 0→a, σ 0→bσ 0, σ 1→aσ 0, σ 1→bσ 1, σ 1→b }. Obrnuto, ako je zadata neka regularna gramatika G, onda se konstrukcija automata A takvog da je Ac(A)=L(G), ne može izvesti direktno. Regularnoj gramatici G se može, prvo, dodijeliti tzv. nedeterministički konačni automat NA takav da je Ac(NA)=L(G). Def. Nederministički konačni automat NA sastoji se od U,S,A,σ * i funkcije prelaza oblika f: S × U → PS tj. f(s,u)=s′∈ PS, gdje je PS partitativni skup skupa stanja S. Znači da automat NA, delovanjem ulaza u na stanje s, prelazi u jedno od stanja iz podskupa stanja s′ tj. stanje u koje će NA preći nije jednoznačno određeno. Podskup s′ može biti i prazan. Primjer: NA=(U, S, f, A, σ *) je određeno sa U={a, b}, S={σ *, C, F}, A={ F} i funkcijom f definisanom sa U

f a

b

C

σ∗

C

∅

{C, F}

F

∅

∅

S

σ∗

ili dijagramom prelaza b

b b

a σ

∗

C

F

38

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Tvrdnja: Neka je G=(N, T, P, σ *) regularna gramatika i NA nedeterministički konačni automat kod koga je U=T, S=N∪{F}, gdje je F∉N∪ T, A∈{F} i f ( s, u ) = {s' s →us ' ∈P} ∪{F s →u ∈P} . Tada je skup svih nizova koje prepoznaje NP jednak jeziku L(G). Primjer: Zadata je G=(N, T, P, σ *) sa T={a, b}, N={σ *, C}, σ * kao početnim slovom i pravilima P= {σ *→bσ *, σ *→aC, C→bC, C→b}. Nederministički automat NA koji odgovara ovoj gramatici je dat u prethodnom primjeru tj. njegov dijagram prelaza je: b b b

a σ

∗

F

C

Svaki nedeterministički automat se može transformisati u ekvivalentni deterministički automat. Tvrdnja: Neka je NA=(U, S, f, A, σ *) nedeterministički konačni automat i neka je S′ =PS, U′ =U, σ *′ ={σ *}, A′ = {x⊆ Sx∩ A ≠∅} i ∅, akoje X = ∅   f′ (X,x)=  f ( s, x ), ako je X ≠ ∅  s∈X

Tada je konačni automat A′ =(U′ , S′ , f′ , A′ , σ *′ ) ekvivalentan automatu NA. Primjer: Automat A′ =(U′ , S′ , f′ , A′ , σ *′ ), ekvivalentan automatu NP iz prethodnog primjera, može se definisati na sljedeći način: U′ ={a,b}, S′ ={∅, {σ *}, {C}, {F}, {σ *, C}, {σ *, F}, {C, F}, {σ *, C, F}}, A′ ={ {F}, {σ *, F}, {C, F}, {σ *, C, F}}, σ *′ = {σ * }, a funkcija f′ se može definisati dijagramom prelaza: b

b a

{ σ* } b

a

{C }

a

∅

{ σ * ,F } a b {F }

a

a

a

{ σ * ,C ,F }

b

b { σ * ,C }

b

a { C ,F }

b

39

PANEVROPSKI UNIVERZITET APEIRON POSLOVNE INFORMATIKE

FAKULTET

Pošto, polazeći od {σ *} A′ očigledno nikada ne može doći u stanja {σ *, F}, {σ *, C}, {σ *,C, F} i { F}, tada se dijagram prelaza može konačno redukovati na: b

b

a {σ* }

a

{C }

b

{ C ,F }

∅

b

a Ovako konstruisani automat A′ prepoznaje sve nizove koje generiše gramatike G iz prethodnog primjera.

40