| prepustit ćemo se životu da bismo bili slobodni bez planova i navika o njemu ćemo moći sniti |
priđi tu sam samo tebe čekam sve je moguće sve je dopušteno |
dodi slušaj ove riječi što trepere na zidovima u svibnju što svjedoče nam o istini da se sve jednoga dana može izmijeniti |
priđi tu sam samo tebe čekam sve je moguće sve je dopušteno |
|
vrijeme življenja le temps de vivre (georges moustaki / zdravko dovedan) | |||
Primarni će predmet našeg bavljenja biti skupovi čiji su elementi znakovi i nizovi znakova. Ovdje se uvode osnovne definicije i terminologija koji se odnose na njih. Potom je dana definicija formalnog jezika i ukratko opisani regularni skupovi i izrazi koji su imali posebno značenje u razvoju teorije formalnih jezika.
Znak je jedinstven, nedjeljiv element, kao što su: a, b, ..., A, B, ..., 0, 1, ..., +, -, *, itd. Alfabet je konačan skup znakova. Najčešće ćemo ga označivati sa A Na primjer, A ={0,1} jest alfabet, poznat kao binarni alfabet .
Ako se znakovi alfabeta A poredaju jedan do drugog dobije se niz znakova (engl. string ) ili "povorka", ili "nizanica". Na primjer, nizovi znakova nad binarnim alfabetom su: 00, 01, 10, 11, 000, 001, 010, 011, itd. Operacija dopisivanja znaka iza znaka, ili niza iza niza, naziva se nastavljanje ili konkatenacija nizova.
Duljina niza znakova jest broj znakova sadržanih u nizu znakova. Na primjer, niz je znakova 010101 duljine 6. Često se duljina niza znakova x označuje s d( x ) ili | x |. Na primjer, |000|=3. Niz znakova aaaa...a, sačinjen od n jednakih znakova, piše se kao a n . Na primjer, umjesto 000 može se napisati 0 3 .
Dva su niza x i y, x=a 1 ...a n i y=b 1 ...b m , jednaka , tj. x=y , ako su jednake duljine, n=m, i ako je a 1 =b i za i=l, ..., n.
Neka su x i y nizovi znakova nad alfabetom A. Kaže se da je x prefiks ("početak"), a y sufiks ("dočetak") niza xy i da je y podniz niza xyz ( x kao prefiks i y kao sufiks niza xy istodobno su i njegovi podnizovi). Ako je x?y i x je prefiks (sufiks) niza y , kaže se da je x svojstveni prefiks (sufiks) od y .
Definira se i niz znakova koji ne sadrži nijedan element. Naziva se prazan niz . Označivat ćemo ga s e ili ?. Duljina praznog niza jednaka je 0, |e|=0, odnosno, ako je a bilo koji znak, vrijedi a 0 =e. Ako je x=a 1 ...a n niz, obrnuti niz (ili "reverzni" niz) jest x R , x R =a n . . . a 1 .
Skup svih nizova znakova koji se mogu izgraditi nad alfabetom A , uključujući i prazan niz e i sam alfabet, označivat ćemo sa A *. Sa A + označivat ćemo skup A *\{e}. Primijetiti da su A * i A + beskonacni ali prebrojivi skupovi! Sa A * k označivat ćemo konačan skup (podskup od A *) svih nizova znakova nad A duljine od 0 do k.
Primjer 1.1
Nad binarnim alfabetom definirani su skupovi nizova znakova:
A* ={e,0,1,00,01,10,11,000,001,010,011,100,... }
A* 2 = {e,0,1,00,01,10,11}
Slijedi definicija formalnog jezika:
Definicija 1.1
Ako je A alfabet i A * skup svih nizova znakova nad A , jezik L nad alfabetom A jest bilo koji podskup od A *, tj.
L Í A *
Često se piše L ( A ) da se naznači definiranost nekog jezika L nad alfabetom A . Nizovi znakova koji čine elemente jezika nazivamo rečenice . Dakle, jezik je skup rečenica.
Primjer 1.2
Evo nekoliko primjera jezika definiranih nad binarnim alfabetom:
L 1 = {0,1} L 2 = {00 ,01 ,10 ,11}
L 3 = {000 ,001 ,010 ,011 ,100 ,101 ,110 ,111}
L 4 = {0, 010 ,01010 ,0101010 ,010101010,... }
L 5 = A * = {e, 0, 1 ,00 ,01 ,10 ,11 ,000 ,001 ,010 ,011 ,100,... }
Iz definicije formalnog jezika slijedi da je to skup, pa se u posebnom slučaju mogu definirati dva jezika, L 1 = Æ i L 2 ={e}.
Definicija 1.2
Za jezik L u kojem za sve njegove rečenice ? vrijedi da nisu svojstveni prefiks (sufiks) ni jednoj rečenici x , x?L i x ? ? , kaže se da ima svojstvo prefiksa (sufiksa).
Primjer 1.3
Jezik {0 n | n = 0} nema svojstvo prefiksa jer je, na primjer, niz 0 svojstveni prefiks za sve rečenice (nizove) 0 n ,n>l, dok jezik {0 n | n>0} ima svojstvo prefiksa, jer se ne može naći ni jedna rečenica koja bi bila svojstveni prefiks nekoj drugoj rečenici, ali nema svojstvo sufiksa.
S obzirom na to da je jezik skup, primjenom poznatih operacija nad skupovima mogu se iz definiranih graditi novi jezici.
Elementi jezika su nizovi znakova pa se može definirati i operacija nastavljanja.
Definicija 1.3
Ako su L 1 i L 2 jezici, L 1 Í A 1 * i L 2 Í A 2 * , tada je L 1 L 2 nastavljanje (ulančavanje ili konkatenacija) ili produkt jezika L 1 i L 2 :
L 1 L 2 = { xy | x ? L 1 , y ? L 2 }
Primjer 1.4
Ako je L 1 = {0, 1} i L 2 = {00 ,01 ,10 ,11}, tada je:
L 3 = L 1 L 2 = {000 ,001 ,010 ,011 ,100 ,101 ,110 ,111}
Definicija 1.4
Zatvarač jezika L , označen s L * , definiran je sa:
(l) L 0 ={e} (2) L n = LL n-1 , n=l (3) L *=? L n n = 0
Pozitivni zatvarač od L , označen sa L + , jest L * \{e} . Primijetiti da je L + = LL * = L * L .
Često se promatraju nizovi znakova konačne duljine koji se mogu smatrati jedinstvenom, nedjeljivom cjelinom. Takvi nizovi znakova nazivaju se simboli ili riječpi.
Primjer 1.5
Nad alfabetom
A ={a, b, c, d , e, f}
može se definirati simbole, nizove jednakih znakova duljine 2: aa, bb, cc, dd, ee, f f.
Skup svih simbola definiran nad alfabetom A označivat ćemo s V i nazivati rječnik. Buduci je V Í A *, zaključujemo da je V jezik. U posebnom se slučaju i alfabet može smatrati skupom simbola duljine 1, pa ćemo ponekad umjesto "znak" reći "simbol" (dakako, obrnuto ne vrijedi!).
Primjer 1.6
Nad alfabetom A ={I, V, X, L, C, D,M} može se definirati rječnik
V ={I, V, IV, X, IX, L, XL, C, XC, D, CD, M, CM}
Jezik je definiran kao podskup skupa svih nizova znakova nad alfabetom. Najčešće je to dosta velik ili beskonačan skup. Zbog toga bi teško bilo i nepraktično definirati ga navodeći eksplicitno sve njegove elemente.
Postoji nekoliko metoda za specificiranje skupa koji čini jezik. Jedna metoda koristi formalizam regularnih skupova i regularnih izraza . Druga metoda koristi generativni sustav nazvan gramatika . Svaka rečenica jezika može se izvesti koristeći pravila gramatike (nazvana "produkcije").
Treća metoda pripada klasi automata. Koristi posebnu proceduru koja poslije konačno mnogo izračunavanja i dosezanja konačnog stanja "izbacuje" rečenicu jezika. Takvi automati nazivaju se generatori .
Regularni skupovi jesu klasa jezika, tzv. regularnih jezika . Imali su posebno značenje u početnom razvoju teorije formalnih jezika, krajem pedesetih godina dvadesetog stoljeća. Ovdje ćemo pokazati kako se teorija regularnih skupova i izraza može primijeniti u specifikaciji jezika.
Definicija 1.5
Neka je A alfabet. Regularni skup ( regularni jezik ) nad A definiran je rekurzivno na sljedeći način:
Dakle, podskup od A * jest regularan ako i samo ako je Ø, {e} ili {a}, za neki a u A , ili se može dobiti iz njih konačnim brojem primjene operacija unije, nastavljanja i operacije *.
Definicija 1.6
Regularni izrazi na A oznacuju odredene regularne skupove. Definirani su, takoder rekurzivno, na sljedeći način:
Ako je pp* regularni izraz, može se napisati kao p + . Ako ne postoji dvoznačnost u nekom regularnom izrazu, suvišne se zagrade mogu izbaciti. Može se zamisliti da operacija * (i + ) ima najviši proritet, potom operacija nastavljanja i na kraju operacija + .
Primjer 1.9
Regularni izraz 101 (101)* opisuje skup (jezik) koji sadrži niz 101 ili nizove dobivene konkatenacijom niza 101:
L ={101, 101101, 101101101, 101101101101,...}
Primjer 1.10
Regularni izraz (0(1)*+0) može se napisati kao 01* + 0. Evo još nekoliko primjera regularnih izraza i odgovarajućih regularnih skupova:
Lako se može pokazati da se za svaki regularni skup može pronaći bar jedan regularni izraz koji ga označuje. I obrnuto, za svaki regularni izraz može se naći regularni skup kojeg taj izraz označuje.
Nažalost, za svaki regularni skup postoji beskonačan broj regularnih izraza koji ga označuju. Reći ćemo da su dva regularna izraza jednaka (=) ako označuju isti regularni skup. Ako su a, ß i ? regularni izrazi, tada vrijede sljedeća algebarska svojstva: