ࡱ> Oy(    "PowerPoint.Show.80BMicrosoft PowerPoint Presentation/ 0DArialingsong Sttdu0 0"DTimes New Romanttdu0 0 DWingdingsRomanttdu0 00DAdobe Fangsong Std R0 0 @Ddobe Fangsong Std R0 0PDVivaldingsong Std R0 0B A0. @n?" dd@  @@`` x4Z **>>       //HG,,.. >>   ^5ij stuvwxyz{|}~ 0AA@8RS -Q ʚ;َm8ʚ;g4RdRdk 0ppp@ <4dddd@w 0t@u0 <4!d!d@x 0tX___PPT108DAdobe Fangsong Std R 0 DArialFangsong Std R 0" pp8f___PPT9H@@?  %flTeorija Formalnih JezikaL      &Danica Mili 164/07H     uSavremeni prevodioci i interpretatori programskih jezika zasnivaju se upravo na rezultatima teorije formalnih jezika. vOpis formalnih jezika Alfabet (azbuka, vokabular) je kona ni skup znakova. Re  (string, word) na nekom alfabetu je niz znakova tog alfabeta. Re  je kona na ako je niz koji je predstavlja kona an, odnosno re  je beskona na ako je niz beskona an.R/@8   BDu~ina re i je ukupan broj znakova koji ini re . (Ako imamo neku re  z, njena du~ina se ozna ava kao |z|) Prazna re  (ozna avamo je sa ) je re  du~ine nula. R a    f          ^Ako su u i v dve re i na nekom alfabetu njihovim spajanjem (nadovezivanjem, konkatenacijom) dobijamo re  uv i va~i da je |uv| = |u| + |v| Re  u je podre  re i v ako postoje re i x i y takve da je v=xuy. Ako je x prazna re  i v=uy onda je u prefiks a ako je y prazna re  i v=xu onda je u sufiks reci v.0/    V      Y        9                              Oznake:$  Pw= wn+1=wwn w  - re  u kojoj je redosled znakova obrnut u odnosu na w. A+ - skup svih re i nad alfabetom A izuzev prazne re i  A* - skup svih re i uklju ujui i     ( ( 6    (( (2      |     l"   6Jezik je bilo koji podskup skupa svih re i. Ako je L jezik na alfabetu A, njegov komplement C(L) je skup A*\L tj skup svih re i alfabeta koje nisu u L. nn         Nad jezicima nad istim alfabetom se primenjuju: Unarna operacija zatvorenja (Klinijeva zvezdica) definisana sa L*={w: w=w1w2..wk za neko ke"0 wi  L, i = 1, k} gde je L neki jezik. Binarna operacija spajanja definisana sa L1.L2={w: w=xy, x  L1, y  L2 } Unarna operacija komplementiranja jezika, binarne operacije unije, preseka itd.."0n0  !             *`hh`h``````h    $$( ((((,`,S0 0j                                                                          Predstavljanje jezika2   2Vrai se: Zadavanjem postupka koji generiae sve re i jezika u nekom redosledu, tako da se svaka re  pojavi kao izlaz nakon nekog kona nog broja koraka rada. Zadavanjem postupka za prepoznavanje koji za svaku re  jezika dobija kao ulazni podatak odgovara sa  da ako pripada jeziku, dok za re i koje ne pripadaju jeziku odgovara sa  ne (ili se eventualno ne zaustavlja, zavisno da je skup re i odlu iv ili ne.)F ZZ" h                  0        (                        dSistemi za generisanje jezika su: gramatike, regularni izrazi itd. Sistemi za prepoznavanje jezika obuhvataju apstraktne maaine, takozvane automate, koji se dobijaju raznim restrikcijama modela Tjuringove maaine. Jezici za koje postoje postupci generisanja i/ili prepoznavanja su barem parcijalno odlu ivi.@3 1$                             Gramatike VDef: Gramatika je ureena etvorka G=<VN, VT, P, S> gde su: VN - skup neterminalnih znakova VT - skup terminalnih znakova P - skup pravila izvoenja S - po etni simbol $  L                                   I va~i da su:  2VN, VT i P neprazni kona ni skupovi VN )" VT = V=VN U VT P je skup izraza oblika !, gde su   V*.VN.V* I   V* S  VN   ( ( (9 ( ((  ( (                           Ako su  i  re i na alfabetu V i ako je ! P, onda se re   direktno izvodi u gramatici G iz re i  ( u oznaci !) Ako su 1, 2... n re i na alfabetu V za koje je 1!G2,..., n-1!Gn onda se ka~e da se re  n izvodi iz re i 1 (u oznaci 1!*Gn) Du~ina izvoenja 1!*Gn je broj primena pravila izvoenjaG   "             ( ( ((  ( (    (  "       '    $ Jezik L(G) generisan gramatikom G je skup {w: S !*Gw, w VT*} Dve gramatike G1 I G2 su ekvivalentne ako je L(G1)=L(G2)w0 (  ( ( (     ( (  *                     &Hijerarhija omskog$   Gramatike tipa 0 (gramatike bez ograni enja) uklju uju sve formalne gramatike. Generiau sve jezike koje mo~e prepoznatiTjuringova maaina. Gramatika tipa 1 (konteksno osetljive) ako va~i da je svako pravilo izvoenja ! i ||e"||. Jezici koje gramatike ovog tipa opisuju su ta no svi jezici koje mo~e prepoznatilinearno ograni en automat (nedeterministi ka Tjuringova maaina ija je traka ograni ena konstantom puta du~ina ulaza.) 6}> "# "  P   a   j Gramatika tipa 2 (konteksno slobodna)  ako za svako pravilo izvoenja ! gramatike G i va~i da je  neterminalni znak i da je  neprazna re . Kontekstno slobodni jezici su teorijska baza za sintaksu veine programskih jezika. Gramatika tipa 3 (regularna)  ako su pravila izvoenja A !aB, odnosno A !a, gde su A, B VN i a VT. Ovakve gramatike generiau regularne jezike.}7      U*      (      ( ,  G>     C 0 Jezici koji im odgovaraju nazivaju se: Jezici tipa 0 ili parcijalno odlu ivi jezici Jezici tipa 1 ili konteksno osetljivi jezici Jezici tipa 2 ili konteksno slobodni jezici Jezici tipa 3 ili regularni jezici(''Z% + +                       Primer:  G=<{A, B, S}, {0,1,..,9}, {S!0, S!1,& , S!9, S!AB, A!1,& , A!9, B !0, B!1,& , B!9, B !BB}, S}> -konteksno slobodna gramatika koja generise jezik koji se sastoji od prirodnih brojeva. G=<{A, S}, {0,1,..,9}, {S!0, S!1,& , S!9, S!1A, S!2A,& , S!9A, A !0, A !1,& , A !9, A !0A, A !1A,& , A !9A},S}  regularna gramatika koja generiae isti jezikO          $ $$ $$ $$ $$ $$ $$ $$ $$ $$ $$ $d$ $((, ,, ,004 44 488< << <                  5                                                            x Na osnovu ograni enja koja se postavljaju jasno je da su gramatike tipa 3 istovremeno i tipa 2, a gramatike tipa 2 su istovremeno i tipa 1 i da su gramatike tipa 1 istovremeno i tipa 0.   *Prema klasifikaciji omskog,  ne pripada ni jednom od jezika tipa 1, 2 ili 3. Definicija se slabi dodavanjem pravila S ! , gde je S po etni simbol i on se ne nalazi sa desne strane ni jednog od pravila izvoenja. Pravilo S !  mo~e se primeniti samo u prvom koraku izvoenja.N[  g  3       Zf1  Ako je L jezik tipa 1, 2 ili 3 tada su istog tipa i jezici L U {} i L \ {}6[F    R                        F(Ne)odlu ivi problemi kod gramatika$$&$  pGramatika je odlu iva ako je odlu iv njome generisani jezik shvaen kao skup. (Odlu iv je problem da li neka re  pripada jeziku) Odlu ive su sve gramatike tipa 1 ili viaeg, pa za svaki odgovarajui jezik postoji postupak koji za svaku re  koja pripada jeziku odgovara sa  da , a za one koje ne pripadaju sa  ne .69                Sledei problemi nisu odlu ivi u opatem slu aju, tj. za gramatike tipa 0:JJ&. C Da li proizvoljna re  pripada jeziku generisanom gramatikom Da li je jezik generisan gramatikom podskup jezika generisanog drugom gramatikom Da li su dve gramatike ekvivalentne Da li je generisan jezik prazan Da li je generisan jezik beskona anX        Tue sisteme &Neodlu iv problem Posmatra se kona an skup J parova re i za koje se ka~e da je x~y ako (x,y) ili (y,x) pripadaju skupu J. Postavlja se pitanje da li dve re i w i u ekvivalentne, odnosno da li se proizvoljnim brojem zamena podre i iz w odgovarajuim re ima sa kojima su u relaciji ~ mo~e dobiti re  u. Zapravo, postavlja se pitanje da li w!*u u gramatici iji skup pravila sadr~i x !y i y !x za (x,y) J O9F@& %       R* Postov problem korespodencije p Za zadati alfabet A posmatraju dve liste od po k re i l1=w1,w2,& wk i l2=u1,u2,& uk, a postavlja se pitanje da li postoji niz brojeva i1, i2,& ,im, me"1, tako da je wi1wi2& wim=ui1ui2& uim613! & 8                      ?  0` 3Wo+ff3̙` 33f33̙3` ! <yxG`wglZff` yE[AQpff3k` 31m̙3f` 3333̙3` O~̙Zƺ` ffff̙` ǵfZƺ` fff3fZ̙>?" dd@*?nZd@`K `7@d` n?" dd@   @@``PR    @ ` `0p>> h `  (  T `   "`   6Dl"  D0 \ }`  "}`  6tl"}` D0 B  s *DjJ"`,$D  0  6Xl "@` l T Click to edit Master title style! !$  0l "@` l RClick to edit Master text styles Second level Third level Fourth level Fifth level!     S   0@l #" `b@  l P*     0l #" ``@  l R*     0l "`` l R*  `B   s *D"     L ?? Base"pp  H  0޽h ? 3333̙3___PPT10i. 3l+D='  = @B +  Layers/  R 0   / (  tT   "  6 vS> BJx}z 8Oq޷L~} (h4-*| ]ԿR?)yev(GY7hɞ1w>?a"?ܜe74"#¼?I+7Wb삆=^ |~݂ _7O͸9!]qG ΏqZby&חr]ye/,lɧYkCwn#M>VH\+͌\V7giY0D]%I#mLj1ӟ.XYs,LB[[gnsں>li'֦Rӹ|'e]nH7EЗL[+%2kǛb^7MP)׫k{>Y(zRٞZijnƭɧԽi47ZCG2Vg* ^&nQo.κ!ӓΧ .5ѥT<4BJ[+r}3Ck ܗXNKT/Evtg_$LaвsW~T`UiFR6U &>+WxłITν6]teT1M ƹ1SKlVc׿[ם{`ܫ8~ ^!|8f|/8aӌ?dθqxR+ٓ{\.eE I:r>z^7gs֢n̖՞ۖη2"ه즇h+x'_ZeHȁGK2؟j= q,^#U)ŴH_7EaS"*'+;(%Цnݑ жN+/GCOͧdY_*~o˜ \k˒FO3E 4,^W%pFugaHNȹjd-)eU5;M\L 碞D bi2TJ\Gآ l?eш~ԩ_[5Mu,Eaz;S^FGs$ &R>quJ# gFE|'>y=qc"jj"e=$܋ {Ix^Ozb Kxx7x%<Ʋxb/4zbo*OoyD,#c=K d6}ʧDK4b(^"񐈷xXE<"w!~GEKğ]"RO=v9h2.vʥa5@G} ˆ%$9@eUToLRz^]< %ؑ .' |?Ud4̌LtxS{'UB1ALB#9X+)/m&TYg$Yq\V¿TqD0/#;o~)MvȚEDŸVz %+:zY/\5d$c/X\Ľ$5S@B!8>8$jRbZ8,c-Yt,O"Iq.eAIrw>o--HQxK@Xh ڑRrañ-A,/9oq:xb h?@M6Kߴ!2׆gl8Z>җLXbbidDs8Ķ}L5ظ-3&k[JoP_el^NW T(i/KOdp/W;`MN J(3d>,qsl|*2Z j5؃_[>o U<H,ʹD0U,HqM /JOE1ACJdBʪ,g7ql{SW'JdG[Ҳ.-]AC8Cx]fj["n)vPpu Un*C  WQݰvؘSWhJp4Ⱀ9 7RM9hﭐ\~}JÄ);rmd󧔦܈>W@L;\_.i@b>Leh@}dΕ4]ÈB%[eƭ W2JRyTi &e^:V%b5 <f}jkʵOKhS,/(=<&XI%yz"PsO .l LMV^ŵ{f5\eA76E_R!f#;Iѕ<ˑfKQG 62hHrDfOv-WmVF @\bܭmP%9F R\Ap"Svww9w"`VWE#.Ӑ'3l D"QOKdK'Gyg)W דG̖& rWtBJygsrĕ{SWDŽlRY6x ˜.Slv9qudHA6e)rM)[/3(n@,qN;S.dmPGve,Lrb  o(u0\1“tir[%1Nȱs#}rYJRzDL::O'{1eOSԗƸ$Q{4CX }q(ߙ!_5Qjh4 ӎf1 t9 S,3%%ӭԔmkk-Ôk8lמx}vꛠ14N+ntV>@tKqYQLAE~l;Xw/,p|B(ѹ0C$\ uJ;-`2O+p'x&q^ (HCylF %ŝ(k^hq~uҎʩ;,+nڪ\bnq'ʳ,R#ZVo6}ӵhgӀqg=?^i[ZʲNL$,ݪOZx[9ʟƯK᧤Ҳ;"_eW~°Ec}nHM&5cdI&2aR.Cc"%78TUYbrUSARrEkש T^n"D&=q*%w1 ƼRL4 %U'J{`fIJАO̻=DuZh>]>l+b(k:5H؞ek:!SXg}&Ѭ+>>5"S0wbkG`)tJ^##q#\/X1چ=$#^1Y{І^`^eEfS`"5vaև(Ԗ**4W"zla =v {ڸwFМ]~SAAtn)V.Ӛ?+&8yrr= \<>~ǧ<՚ZL&s5nJQeU (B`=SbVQ#r>_͓{=$SexRzK(QړKd'&Xl#-rBDIBzlO>ϋl mԭ)Ju%^˖IY1m-6J'N͟RkC^ Hl *n0EoW`Jz^NR[>): H甘UL'6n5pszhp ~ue!lTiUCؕ`BCV  j ³i+Y˥T50fj*Û?lv_Nv1D(%GrȇSAnBQ},;^oPGahGϢ6A>?1iE-4;:Yk@⧆: 7C=x4ꚾ1lZMw9%aL r9lU(CC#]S;撄aKP^`?}DŽpCAd.J$ITyq=\G)jDg0 >m6="#;0ԫMϙL,Vb"ZCd& 7׈j3%L7ʧ{W(ԜϚ|EY6uw#V]F`n Y}V/ig[<^^O.=(x-A;Ŝr+'[( #@Pe3cWwSQ+h7+xWƯVL-嗄*ǻg'"1 5mְD%y* @h<qbei9t5 k$]K=Xs0B˖npHhҟ;f ^_-^[xdiPmmd=Cx*^sm8]=Qwy-]]~'%_Z3d5!(8s8v\+u~'Et#]dRi=?:'Aѽ09 ^)-~ p@R݆<>zB'tm2f`k].cajGR['}V=Â$G ?ye'l7 bTQ{$ywg2( -| mL#֢:Uq[ G/;O4mp,rw{NX^'8 psGtҧub[W(G?N`Kcb#FY{A7m۠2@_'Nޓ"#Tsdw E&Jܲ~Vg8n˚ϛ\:d`e;j?ٟ{ Q]n࡝:Su.6z$R?HV +_FKI֑w<.ܶ#T9zU͓1}GnONO^Hd9Y^y.Y[ΨvoU(y&;Ĉ^P:1^iG\m/^'1WFV 6B-)?HK+gӣ@{:tn.`j O]b˧:o6?qeijy po/ۢvz53_4>w#gUoBX>" |orxJ[$qhy N{7]9'(ɴE.jAd4pg smeHyro KDL'$ q92N5/ћDڽK1Ň,yw o\i4i4k5jOv5 C iq\}9AߡS_'D̼-Lo<>STn]TmJk?,LJKFu@_N|w4T:{,1 7/%ttBl)AZHQ+p5 rɩPzyv˳)۲aꢮ0l*ֆ0M )/ fީ,;fN?Ժ94=w {OSد`+~Ǎ|uv٣17+8c^9'z- ޠ*Д6ÆmeGfyJy 1ڞRځ&cMu6]`C#P >NGy-'1_[ʍH%e,ԫToi NdU^Hiv@PKw͝6򤸝xQ|'^oS]#>aod lXo隰VLpjÞQ ljnR ]bζ7u |u:ּ63Y=}naE$Rvqƾ\!&:m1q<%|Ø:ﲌ ,[= OX4#=o:O{?IM9՟b2iaWg.ս̝?>I sIy@M7>u*m1]:YV՟$um$~'+ 8C$֒onT 4lgӢyu_~p((QP)8GKWr&7L#JkXP/qb}hOfC )×76U.f"2>}F1N]$+t ywN"tیZ:!%z+2rd#QĽ]EBe8&O7r,&Ij+NTTƘ7u K܍}-Qv[u>ǘLIok ~#t-v֕|}5XW&yt۟z_6?:p]ӝb< 8;IwujKDX}p}!%nj&u{$|>w}_} Xq{AB*GjaP!>ƞH\M%?d1}b#O$csNLDNr "?Dk0e#,ve;i7 ͎!N&¹8Y6JlM)yOWt?0gbk%Ώ(1{-bs&ݗ=9j@^D`N05jhZKFT$їb( " ֪' ytr"| `0߻oc@/kٜ RewM".KNĜq}/a/Yi1>OԸ?#?5p{Nk ,cTM1n1oqKcvVvVC(ӜV@^ihVf ͌P4O>4NWhʷk! {FM:q QoPM4PI>}'!VE+oJPWB' ڍ(kwr]x 6`.i7A"u,8oܾ@oThi5}-V1g;3ET[E.U(nK3xK\*rX |lgLS~XK3yOQz 'LlY o UDhzm EB\K7vg`-o2[5dM.:HC&]GmZmp5'*5*E8Z}he!wx(9*>RlR(c |cϔ}*BjNlOg^m*Mkw~;݉Q_1QeqmF"%G4~n(p-5ao2߉;߉_6b>l~}޹wޱLZ\oJ~5zDiu k(`@Z 4!-g^4Ǚa7Q>Qs)oBs*n}1aY4UMÜs29\Ŝ?=sn>snirΜ9׎=8@oo,Ut\]o}fefO+K$\%L9lg֨S[SiWaRۚ AS%7 3КnЊaMԁ1Q=y8x`-4΋;V+5c_4b -{Uh*%Aci{@??xqӞF$:Ƃ&kM#M#P״sO+;ڃAhmJ;D;?kgaps@STuP_c!L>U? iY@[,V&4;|?.}q"n"LmS~nᷰgf!ZK 4͹9M|*ɘ9cœN +`XP-@vI%96 W(,/AaV֛%(75 `)fRon.[+ʘ"LK+5zxpf=>{lG{}Po0֌{,~/* M'~-9<߾=ye/DY,W2QLhxeBc*x5͸&ݼe땗,UQ54 &8'fw}Wg]1u"p;鱓=~duc_CMoYW*+{ڼW1M^@^є}WƀWhTy%ZD5 +}}JtvWeSVSXdVC,WWP5\r5܅3{Gc_hcMjK豸=?'&3y&=.U8Y?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{}~Root EntrydO)Current UserSummaryInformation(|PowerPoint Document(DocumentSummaryInformation8Root EntrydO)@Current User/SummaryInformation(|PowerPoint Document(_9nalognalog