| dok sam spavao
dok sam sanjao kazaljke su se okretale prekasno je moje djetinjstvo je tako daleko već je sutra prolazi, prolazi vrijeme nema ga više puno |
dok sam te volio
dok sam te imao ljubav je otišla prekasno je bila si tako lijepa sam sam u svom krevetu prolazi, prolazi vrijeme nema ga više puno |
dok sam pjevao
svojoj dragoj slobodi drugi su je u lance okovali prekasno je neki su se čak i borili ja to nikada nisam znao prolazi, prolazi vrijeme nema ga više puno |
ipak još uvijek živim
ipak još uvijek vodim ljubav dode mi čak i da zasviram na svojoj gitari o dječaku kakav sam bio o dječaku kakvog sam stvorio prolazi, prolazi vrijeme nema ga više puno |
dok sam pjevao
dok sam te volio dok sam sanjao bilo je još vremena |
|
prekasno je
il est trop tard (georges moustaki/ zdravko dovedan) | ||||
Izučavanje teorije formalnih jezika zahtijeva strog, formalni pristup. Takoder pretpostavlja solidno predznanje iz matematike, posebno teorije skupova, grafova i matematičke logike. Sve to, veoma sažeto, dano je u ovom uvodnom poglavlju.
Skup intuitivno shvačamo kao kolekciju elemenata (ili članova) koji posjeduju izvjesna svojstva. Na primjer, skup dana u tjednu sačinjavaju sljedeći elementi: ponedjeljak, utorak, srijeda, četvrtak, petak, subota, nedjelja.
Ako je a element skupa S, piše se a Î S i cita " a je element skupa S", a ako nije, piše se a Ï S i čita " a nije element skupa S". Na primjer, petak Î S, svibanj Ï s, gdje je S skup dana u tjednu.
Elementi skupa mogu biti jedinke, koje predstavljaju sami sebe, ili neki drugi skupovi. Prikazuje se samo jedno pojavljivanje nekog elementa u skupu. Redoslijed pisanja elemenata skupa nije bitan. Primjeri:
{a,b,c} = {a,c,b} = {b,a,c} = {b,c,a} = {c,a,b} = {c,b,a}
{a,a} = {a}
{a,{b}} ¹ {a,b}
{a} ¹ {{a}}
Ako skup sadrži konačan broj elemenata, naziva se konačnim, a ako ima beskonačno mnogo elemenata, onda je beskonačan. Definira se i prazan skup, skup koji ne sadrži nijedan element. Označavat ćemo ga s Æ . Također se definira i prebrojiv skup, a to je ili konačan skup ili beskonačan skup u kojem su elementi uređeni tako da se uvijek može odrediti sljedeći, odnosno, kaže se da tada postoji bijekcija sa skupa prirodnih brojeva na taj skup.
Do pojma podskupa dolazi se promatranjem dijela nekog skupa. Kaže se da je B podskup skupa A ako je svaki element x iz B ujedno i element skupa A. U tom slučaju piše se
B Í A
Na primjer, skup
P={ponedjeljak, srijeda, petak}
podskup je skupa S svih dana tjedna, tj. P Í S. Piše se B Ì A i kaže da je B pravi podskup skupa A ako u A postoji najmanje jedan element koji nije u B. Ako se želi istaknuti da B, u krajnjem slučaju, može biti cijeli A, piše se B Í A. Partitivni skup nekog skupa A, označen s P(A), jest skup svih skupova koji se mogu izgraditi od elemenata skupa A, uključujući sam skup A i prazan skup. Ako skup A sadrži n elemenata, partitivni skup P(A) sadržavat ce n2 elemenata (skupova).
Skup se S smatra zadanim ako je nedvosmisleno rečeno, objašnjeno ili specificirano, što su elementi tog skupa. Zadati skup S znači dati ograničenje, propis ili svojstvo kojim su u potpunosti odredeni svi elementi skupa.
U nekim se slučajevima elementi skupa jednostavno navedu izmedu vitičastih zagrada. Na primjer:
S={l, 3, a, d}
Često je nemoguće nabrojiti sve elemente skupa koji se mogu zadati nekim propisom, kao na primjer kada se govori o skupu svih parnih brojeva. Premda je taj skup određen, nije moguće navesti sve njegove elemente, pa se piše
S={2, 4, 6, 8, 10, 12, ...}
Točkice naznačuju sve ostale elemente iz S koji se eventualno ne mogu navesti. U takvim je slučajevima prikladno skup zadati na sljedeći način:
S={x| P(x)} ili S={x: P(x)}
što se čita: "Skup S sadrži one elemente x za koje je ispunjeno svojstvo (ili predikat) P(x)". Na primjer, ako je N skup prirodnih brojeva, može se napisati
S={x| "x je paran"} ili S={x: x=2n, n Î N}
Postoji nekoliko operacija sa skupovima koje se mogu koristiti pri izgradivanju novih skupova. Neka su A i B skupovi. Unija od A i B, napisana kao A È B, jest skup koji sadrži sve elemente skupa A zajedno sa svim elementima skupa B:
A È B={x | x Î A ili x Î B}
Presjek skupova A i B, A Ç B, skup je elemenata sadržanih i u A i u B:
A Ç B={x| x Î A i x Î B}
Razlika skupova A i B, A\B, skup je elemenata koji pripadaju skupu A, a nisu u B:
A\B={x|x Î A i x Ï B}
Izravni ili Kartezijev produkt dvaju skupova A i B je skup:
AxB = { (a,b) I a Î A, b Î B}
Element tako nastalog skupa, (a,b), naziva se uređeni par. Na primjer, ako je A={a, b}, B={0,1}, Kartezijev produkt AxB jest skup
{(a,0), (a,l), (b,0), (b,l)}
Prva komponenta bilo kojeg para mora biti iz A, druga iz B. Zbog toga (0, a) nije element skupa AxB.
Relacija, oznacimo je s p, jest bilo koji podskup Kartezijevog produkta skupova. Na primjer, ako je N={ 1, 2}, M={ 0,1, 2, 3, 4, 5}, relacija p, p Í NxM, može biti
p={(l,0),(1,1), (1,2), (1,3), (2,0), (2,1), (2,2)}
Primijetiti da relacija p u ovom primjeru označuje svojstvo parova (x,y), x Î N, y Î M, da im je zbroj manji ili jednak 4. Isto svojstvo može se napisati kao xpy što se čita "x je u relaciji p sa y" ili "izmedu x i y postoji relacija p".
Funkcija (preslikavanje, transformacija) f iz skupa A u skup B jest relacija iz A u B takva da, ako su (a,b) i (a,c) u f, vrijedi b=c.
Ako je (a,b) u f često se piše b=f (a). Kaže se daje f(a) definirano tko postoji b u B tako daje (a, b) u f. Ako je f(a) definirano za sve a iz A, kaže se daje f potpuno preslikavanje sa A u B. Ako to nije ispunjeno, f je djelomično preslikavanje iz A u B. U oba slučaja piše se
f: A ® B
i kaže da je A domena, a B kodomena funkcije f.
Dobro poznavanje elemenata matematičke logike osnovni je uvjet shvaćanja problema formalnih jezika. Ovo potpoglavlje predstavlja kratki repetitorij matematičke logike.
Algebra sudova osnova je drugih dijelova matematičke logike, prijeko potrebna za njihovo razumijevanje. Izgraduje se na isti način kao i mnogobrojne matematičke teorije. Za osnovne pojmove uzima se neka klasa objekata, te neka svojstva, odnosi i operacije nad tim objektima. Ti se osnovni pojmovi smatraju polaznim, i za njih nije potrebno dati nikakvu definiciju. Osnovni pojmovi najcešće se objašnjavaju primjerima. Osnovni objekt kojeg proučava algebra sudova je elementarni sud. Na primjer, elementarni sudovi su:
"Broj 100 djeljiv je s 4" "Danas je lijepo vrijeme"
"Štef nema djevojku" "Mjesec je veci od Zemlje"
"17 je prost broj"
Svi elementarni sudovi moraju imati jedno i samo jedno svojstvo:
"biti istinit" ili "biti lažan"
Na primjer, sud "7 je veće od 5" je istinit, a sud "8 je prost broj" nije istinit. U daljnjem tekstu elementarne sudove označivat ćemo malim slovima a, b, c, itd.
Za primjene u programiranju posebno su važni elementarni sudovi nazvani relacijski izrazi. Općenito relacijski izraz sadrži dva izraza istog tipa (na primjer, dva aritmeticka izraza) izmedu kojih je napisana jedna od relacija:
= jednako * različito
< manje < manje ili jednako
> veće > veće ili jednako
Na primjer, relacijski izraz (elementarni sud) "9>5" čitat ćemo "9 je veće od 5".
Od elementarnih sudova moguće je, uz pomoć nekoliko logičkih operacija, graditi složene sudove. Jasno je da će i složeni sud biti istinit ili lažan. U daljnjem tekstu govorit će se o njegovoj "vrijednosti istinitosti", koja će biti označena s T za istinito, i s F za lažno.
Vrijednost istinitosti složenog suda ovisi o istinitosti sudova od kojih je složeni sud izgraden. Postoji nekoliko unarnih i binarnih logičkih operacija (logičkih veznika ili konektiva). Ovdje su opisane samo one osnovne; negacija, kao unarna logička operacija, te binarne logičke operacije:
• konjunkcija
• disjunkcija
• implikacija
Negacija je unarna logička operacija i ujedno najjednostavnija operacija algebre sudova. U govornom jeziku odgovara joj približno riječ"ne". Ako negaciju oznacimo s " Ø a", njezino djelovanje na sud a dano je u sljedećoj tablici:
| a | Ø a |
| F | T |
| T | F |
Ako je a neki sud, na primjer "5 je djelitelj od 7", -.a novije sud "5 nije djelitelj od 7". Sud -ia čita se "ne a" ili "non a".
Ako su a i b sudovi, onda je aAb novi složeni sud ili konjunkcija sudova a i b. Znak " Ù " čita se "i" ili "et". Djelovanje operacije konjunkcije definirano je sljedećom tablicom:
| A | b | a Ù b |
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
Treba zapamtiti da će složeni sud a Ù b biti istinit onda i samo onda ako su i a i b istiniti. Operacija konjunkcije po smislu približno odgovara vezniku ² i ² . Na primjer, elementarni sudovi "6 je djeljivo sa 3", "10 je veće od 5" istiniti su, pa je istinita i njihova konjunkcija "6 je djeljivo sa 3 i 10 je veće od 5". Medutim, elementarni sudovi "3 je djeljivo sa 7" i "3 je veće od 7" lažni su, pa je lažan i složeni sud "3 je djeljivo sa 7 i 3 je veće od 7".
Operacija disjunkcije najčešće se označuje sa " Ú " i čita "ili". Treba napomenuti da veznik "ili" u mnogim jezicima ima dva razlicita značenja. U jednom slučaju radi se o tzv. "isključnom", u drugom o "neisključnom" vezniku "ili". Razlika medu njima pokazana je u sljedećem primjeru:
Ako su a i b dva lažna suda, lažan je i složeni sud a Ú b. Ako je a istinito, a b lažno, ili a lažno, a b istinito, istinit je i složeni sud a Ú b. Stoje, Ipedutim, s vrijednošću istinitosti suda a Ú b ako su i a i b istiniti? U prvom slučaju, ako se složena izjava smatra istinitom, govori se u neisključnoj, u drugom o isključnoj disjunkciji.
U matematičkoj logici operacija disjunkcije odgovara neisključnom vezniku "ili". Iz prethodnih razmatranja slijedi definicija: disjunkcija sudova a i b, napisana kao a Ú b, složen je sud koji je lažan onda i samo onda ako su i a i b lažni. Iz te definicije slijedi tablica:
| a | b | a Ú b |
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
Implikacija se obično označuje sa "=>" i definira na sljedeći način: ako su a i b dva suda, a=>b (cita se "a implicira b") složeni je sud koji je istinit uvijek osim ako je a istinito, a b lažno. Tablica istinitosti implikacije dana je sa:
| a | b | a Þ b |
| F | F | T |
| F | T | T |
| T | F | F |
| T | T | T |
Operacija implikacije odgovara, u određenom smislu, veznicima "ako..., onda...". Sud "ako je a, onda je b" može se shvatiti kao Ø a Ú b. U većini slučajeva pogodnije je sud a=>b zamijeniti sudom Ø (a Ù Ø b). Takvo značenje implikacije ističe činjenicu da pri istinitosti a=>b ne može nastupiti slučaj da je a istinito, a b lažno. To odgovara važnom svojstvu implikacije da istina ne može implicirati neistinu. Na kraju treba napomenuti da se sud a=>b ne podudara uvijek po smislu sa sudom "ako je a, onda je b". Otuda, da bi se izbjegli eventualni nesporazumi, složeni je sud a=>b bolje čitati "a implicira b".
Uporabom navedenih logičkih operacija i uvođenjem zagrada mogu se, kao i u algebri, graditi razni složeni sudovi ili logički izrazi. Na primjer:
(a Ú b) Ù c (a Ù b) Þ (c Ú d) Ø a Ú (b Þ c)
Logičke varijable koje se pojavljuju u izrazima mogu biti elementarni sudovi, na primjer "x<6", ili nosioci logičkih vrijednosti dobivenih kao rezultat prethodnog izračunavanja (nekog logičkog izraza). Takoder se može pojaviti logička konstanta F, čija je vrijednost istinitosti uvijek "laž", i logička konstanta T čija je vrijednost istinitosti uvijek "istina". Logički izrazi koji sadrže samo operacije negacije, konjunkcije i disjunkcije, te zagrade, nazivaju se Booleove formule. Za Booleove formule vrijede sljedeći zakoni:
1) Zakon komutacije:
x Ú y º y Ú x
x Ù y º y Ù x
2)Zakon asocijacije:
x Ú (y Ú z) º (x Ú y) Ú z
x Ù (y Ù z) º (x Ù y) Ù z
3) Zakon idempotentnosti:
x Ú x º x
x Ù x º x
4) Zakon distribucije:
x Ú (y Ù z) º (x Ú y) Ù (x Ú z)
x Ù (y Ú z) º (x Ù y) Ú (x Ù z)
5) De Morganov zakon:
Ø (x Ù y) º Ø x Ù Ø y
Ø (x Ù y) º Ø x Ú Ø y
6)Zakon dvostruke negacije:
Ø Ø x º x
Posebno je česta uporaba de Morganovog zakona u programiranju.
Graf je apstraktni matematički objekat. No, uobičajeno je da se njegov geometrijski prikaz - lik sastavljen od točaka i crta koje ih spajaju - naziva graf.
Grafovima (stablima) je moguće opisati mnoge strukture u računarskim znanostima. Ovdje je izložen koncept teorije grafova koji ima posebne primjene u teoriji formalnih jezika.
Neformalno, grafovi su likovi sastavljeni od točaka od kojih su neke (dvije po dvije) spojene krivuljama.
Postoji nekoliko definicija grafa. Ovdje su dane dvije, ona kojom se pojam grafa povezuje s pojmom binarne relacije, i definicija prema C. Bergeu.
Definicija 0.1
Neka je X={x 1 ,x 2 , . . . ,x n } neprazan skup i r binarna relacija u r Í X ´ X. Uredeni se par G = (X, r ) naziva graf, elementi skupa X čvorovi, a elementi skupa r grane grafa.
Na primjer, ako je X 1 ={l,2, 3, 4}, a r 1 ={ (1,1) , (1, 2) , (2, 3) , (2, 4) , (3,4), (4,3)}, primjer grafa je G 1 =(X 1 , r 1 ).
Slijedi definicija grafa prema C. Bergeu:
Definicija 0.2
Neka je X={x 1 ,x 2 , . . ., x n } neprazan skup i P(X) njegov partitivni skup. Definira se preslikavanje d sa X u P (X), tj. za svaki x i Î X je d (x i ) Î P (X). Graf je definiran skupom X i preslikavanjem d, tj. graf je uredeni par ?= (X, d).
Na primjer, graf ? iz prethodnog primjera može se definirati kao ? = (X, d), gdje je X=X i , a funkcija d definirana je sa:
d (1) = {1,2}
d (2) = {3,4}
d (3) = {4}
d (4) = {3}
Graf može biti prikazan crtežom ili matricom susjedstva. Prikaz grafa crtežom je na sljedeći način: Najprije se nacrtaju čvorovi x i , ..., x n kao točke ili kružnice u ravnini (ili prostoru). Njihov razmak i pozicija potpuno su proizvoljni. Potom se spoje čvorovi za koje vrijedi (x i /x j ) Î r . Čvor x i , prikazan kružnicom ili točkom, spaja se sa x j neprekinutom crtom i usmjerava strjelicom od x i k x j Grana (x i, x j ) izlazi iz čvora x i i ulazi u čvor x j . Ako (x i, x j ) Ï r , čvorovi x i i x j nisu izravno povezani na crtežu.
Ako je (x i , x i ) Î r , čvor x i treba spojiti sa samim sobom. Takva se grana naziva petlja. Smjer petlje nema posebnog značenja pa može biti izostavljen.
Ako su čvorovi x i i x j povezani s dvije grane, (x i , x j ) i (x j , x i ), na crtežu se povlače dvije crte, ili jedna crta obostrano usmjerena, ili jedna crta bez oznake usmjerenja. Na primjer, graf G 1 = (X 1, r 1 ), gdje su X 1 i r 1 kao što je ranije definirano.
Osim crtežom, graf može biti prikazan kvadratnom matricom čiji je red jednak broju čvorova. Takva se matrica naziva matrica susjedstva ili Booleova matrica (jer su joj elementi 0 ili 1). Element a ij na presjeku i-tog retka i j-tog stupca u toj matrici, jednak je 1, ako je (x i , x j ) Î r , odnosno 0 ako to nije ispunjeno. Na primjer, graf G može biti prikazan sljedećom matricom susjedstva:
| 1 | 2 | 3 | 4 | |
| 1 | 1 | 1 | 0 | 0 |
| 2 | 0 | 0 | 1 | 1 |
| 3 | 0 | 0 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 |
Najprije dajemo definiciju puta u grafu potom još nekoliko važnih definicija:
Definicija 0.3
Niz čvorova (x 0 , . . . ,x n ), n=l, jest put duljine n od čvora x 0 do čvora x n ako postoji grana koja izlazi iz čvora x i-1 i ulazi u čvor x i, za l=i=n. Ako izmedu čvorova a i b grafa G postoji put duljine k, k=l, tada je a prethodnik od b, odnosno, b je slijednik od a. Ako je k=l, a je izravni prethodnik od b. Tada je b izravni slijednik od a.
Definicija 0.4
Kružni ili zatvoreni put jest put (x 0 , , x n ) u kojem je x n =x 0 .
Definicija 0.5
Graf G =(X, r ) jest povezan ako postoji put od a do b za sve parove različitih čvorova.
Definicija 0.6
Ulazni stupanj čvora x grafa G = (X, r ), x Î X, jest broj grana koje ulaze u x. Izlazni stupanj jest broj grana koje izlaze iz čvora x.
Na kraju ovoga poglavlja dajemo još nekoliko definicija koje se odnose na posebnu skupinu grafova - stabla.
Definicija 0.7
Stablo, označimo ga s t, jest povezani graf G = (X, r ) s n=l čvorova i m=n-l grana.
Definicija 0.8
Korijen stabla jest čvor x sa svojstvima:
ulazni stupanj od x jednak je 0,
svi ostali čvorovi stabla imaju ulazni stupanj jednak 1, i
-svaki je čvor iz X slijednik od x.
List stabla t jest čvor z sa svojstvom da mu je izlazni stupanj jednak 0.
Korijen je označen s 1. Čvorovi 2 i 3 izravni su slijednici od 1, a cvor 3 izravni prethodnik čvorovima 4 i 5.
Ako je t stablo, iz njegove definicije slijedi da ne sadrži petlje i da postoji jedinstveni put od korijena do svakog njegova čvora.
Definicija 0.9
Podstablo stabla t = (X, r ) jest stablo t ' = (X', r ') takvo da:
- X' nije prazan i sadržan je u X, tj. X' Í X,
- r '= (X'× X' ) n r i
- nijedan čvor iz X\X' nije slijednik čvora X'.