Teorija algoritama, automata i jezika

  • View
    48

  • Download
    5

Embed Size (px)

DESCRIPTION

Ova knjiga je zbirka zadataka iz predmeta Teorija algoritama, automata i jezika, na prvoj godini Master akademskih studija na Departmanu za Raunarske nauke Prirodno-matematikog fakulteta uNiu.

Transcript

  • DR MIROSLAV D. CIRIC, redovni profesorPrirodno-matematickog fakulteta Univerziteta u NiuDR JELENAM. IGNJATOVIC, docentPrirodno-matematickog fakulteta Univerziteta u Niu

    TEORIJA ALGORITAMA, AUTOMATA I JEZIKA ZBIRKA ZADATAKAprvo izdanje, 2012

    IzdavacPRIRODNO-MATEMATICKI FAKULTETUNIVERZITETA U NIU

    Za izdavacaPROF. DR DRAGAN OREVIC, dekanUrednikPROF. DR IVAN MANCEVRecenzentiPROF. DR STOJAN BOGDANOVICPROF. DR PREDRAG STANIMIROVICtampaM KOPS CENTAR, NITira: 120 primerakaISBN 978-86-83481-87-3

    CIP - ,

    519.713(075.8)(076)519.76(075.8)(076), ., 1964Teorija algoritama, automata i jezika :

    zbirka zadataka /Miroslav D. Ciric, JelenaM. Ignjatovic. - 1. izd. - Ni :Prirodno-matematicki fakultet, 2012 (Ni : Mkops centar). - VIII, 183 str. : graf.prikazi, tabele ; 24 cmTira 120. - Bibliografija: str. 177-178. -Registar.ISBN 978-86-83481-87-31., ., 1973 []a) , b)

    COBISS.SR-ID 188136460OdlukomNastavno-naucnog veca Prirodno-matematickog fakulteta uNiu,broj 1072/1-01 od 21.12.2011. godine, ova knjiga je odobrena kao pomocniudbenik za predmet Teorija algoritama, automata i jezika.

  • Miroslav D. CiricJelena M. Ignjatovic

    Teorija algoritama, automata ijezika

    Zbirka zadataka

    Ni, 2012

  • Predgovor

    Ova knjiga je zamiljena, prvenstveno, kao zbirka zadataka iz predmetaTeorija algoritama, automata i jezika, na prvoj godiniMaster akademskih studijana Departmanu za Racunarske nauke Prirodno-matematicog fakulteta uNiu. Problemi koji se obraduju i izucavaju u okviru ovog predmeta obuh-vataju formalne jezike, automate i druge modele izracunavanja. Zadatakpredmeta je ne samo da se studenti upoznaju sa brojnim primenama auto-mata i formalnih jezika, vec i sa osnovnimmatematickim (prvenstveno alge-barskim) pojmovima i alatima koji se koriste za opis apstraktnih objekatakoji se izucavaju u racunarskim naukama.

    Ideja za pisanje ove zbirke rodila se nakon viegodinjeg izvodenja vebii predavanja iz napred pomenutog predmeta. Na srpskom jeziku ne postojizbirka zadataka koja prati program ovog kursa. Poznata nam je samo jednazbirka na engleskom jeziku, ali se ona samo delimicno bavi tom tematikom.Dakle, knjiga je prvenstveno namenjena potrebama pomenutog predmeta,sa naglaskom na probleme teorije jezika i automata koji su racunarski reivi,uz primenu alata iz univerzalne algebre, teorije polugrupa i teorije grafova.Trudili smo se da prikupimo mnotvo razlicitih primera, pocev od osnovnihpitanja vezanih za elementarne definicije i koncepte, do onih naprednih kojizahtevaju poznavanje sofisticiranijih matematickih alata. Ideje i tehnike do-kazivanja objanjene su na konstruktivan nacin, uz primenu indukcije i re-kurzije kad god je to moguce. Zbog ovakve koncepcije zbirku mogu kori-stiti i studenti doktorskih studija u oblasti racunarskih nauka i matematike,za predmet Formalni jezici, automati i izracunljivost, kao i studenti tehnickihnauka i svi oni koji su zainteresovani za reavanje problema iz oblasti teori-jskog racunarstva.

    Zbirka se sastoji iz pet glava. Svaka glava najpre sadri teorijske osnoveza probleme koji se u njoj reavaju, a nakon toga veci broj uradenih primerai zadatke predvidene za samostalni rad studenata, cije se reavanje baziraili neposredno sledi iz nekog od uradenih zadataka. Odredeni broj primerapredstavlja poznate teoreme iz ove oblasti koje su formulisane u obliku zada-taka.

    v

  • vi Predgovor

    U prvoj glavi reavaju se neki osnovni problemi vezani za razna uredenjana polugrupi reci, definiu se pojmovi jezika i gramatike, daje njihova klasi-fikacija i kroz veliki broj primera se reavaju problemi vezani za ovu oblast,ukljucujuci i probleme izvodenja u gramatici.

    Druga glava posvecena je automatima bez izlaza i jezicima koji mogu bitiraspoznati konacnim automatima. Predstavljeni su algoritmi za konstrukcijuminimalnog automata datog jezika,minimizaciju datog automata, konstruk-ciju sintaksickog monoida datog jezika, kao i primeri iz kojih se vidi znacaji primena Kleenijeve teorema i Leme o napumpavanju.

    U trecoj glavi reavaju se problemi vezani za predstavljanje konteksno-nezavisnih jezika pomocu konteksno-nezavisnih gramatika, obradene su re-dukcije ovih gramatika, a potom i primeri konstrukcije potisnih automatakao apstraktnih maina koje raspoznaju konteksno-nezavisne jezike.

    Cetvrta glava se bavi deterministickim i nedeterministickim Turingovimmainama, kao najoptijommatematickom formalizacijom pojma algoritma.Turingove maine opisuju tacno jezike generisane proizvoljnim gramatika-ma i precizno definiu granicu izmedu problema koji su algoritamski reivi ionih koji to nisu.

    Uposlednjoj glavi govori se o automatima sa izlazom, automatimaMealy-evog iMooreovog tipa, o transformacijama reci i funkcijama koje semogu re-alizovati takvim automatima, kao i problemima ekvivalentnosti i minimiza-cije automata sa izlazom.

    Koristimoprilikuda se zahvalimorecenzentima,Prof. dr StojanuBogdano-vicu i Prof. dr Predragu Stanimirovicu, na vrednim primedbama i savetima.Zahvalnost dugujemo i koleginicama Ivani i Zorani Jancic, koje su paljivocitale rukopis i dale niz korisnih sugestija. Drugi autor se posebno zahvaljujesvojoj majci, gospodi Svetlani Kovacevic, za ogromno strpljenje i podrkutokom pisanja ove knjige.

  • Sadraj

    1 Formalni jezici i gramatike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1. Reci, uredenja na recima i jezici . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Formalne gramatike . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.3. Hijerarhija Comskog (Chomsky) . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.4. Regularni jezici i regularni izrazi . . . . . . . . . . . . . . . . . . . . . . . . . . . 281.5. Reprezentacija regularnih izraza pomocu grafova . . . . . . . . . . . 30

    2 Regularni jezici i konacni automati . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372.1. Deterministicki konacni automati . . . . . . . . . . . . . . . . . . . . . . . . . . 372.2. Minimalni automat jezika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.3. Minimizacija automata bez izlaza . . . . . . . . . . . . . . . . . . . . . . . . . . 492.4. Sintaksicki monoid jezika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622.5. Nedeterministicki automati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 662.6. Najveca desna kongruencija na monoidu reci . . . . . . . . . . . . . . . 812.7. Raspozntljivi jezici. Lema o napumpavanju . . . . . . . . . . . . . . . . . 842.8. Regularni izrazi. Regularni jezici. Teorema Kleenea . . . . . . . . . . 87

    3 Kontekstno-nezavisni jezici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 933.1. Konacni automati i konteksno-nezavisne gramatike . . . . . . . . . 933.2. Kontekstno-nezavisne gramatike . . . . . . . . . . . . . . . . . . . . . . . . . . . 953.3. Lema o napumpavanju za kontekstno-nezavisne jezike . . . . . . 1063.4. Stabla izvodenja i parsirajuca stabla . . . . . . . . . . . . . . . . . . . . . . . . 1083.5. Potisni automati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

    4 Turingove maine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1294.1. Konstrukcija Turingovih maina . . . . . . . . . . . . . . . . . . . . . . . . . . . 1294.2. Turingove maine i jezici tipa 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

    5 Automati sa izlazom . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1475.1. Predstavljanje i konstrukcija automata sa izlazom . . . . . . . . . . . 1475.2. Preslikavanja indukovana automatima . . . . . . . . . . . . . . . . . . . . . 1545.3. Ekvivalentni automati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

    vii

  • viii Sadraj

    5.4. Homomorfizmi i kongruencije . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1675.5. Minimizacija automata sa izlazom . . . . . . . . . . . . . . . . . . . . . . . . . 170

    Literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

    Indeks pojmova . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

  • Glava 1

    Formalni jezici i gramatike

    1.1. Reci, uredenja na recima i jezici

    Neka je X neprazan skup koji nazivamo alfabet, a cije elemente nazivamoslova. Rec (string) nad alfabetomX definie se kao konacan niz x1x2 . . .xn, gdesu x1,x2, . . .xn X slova. Duina reci u, koju oznacavamo sa |u|, je broj slovau toj reci. Prazan niz slova oznacava se sa e i naziva prazna rec. Jasno je da je|e| = 0.

    Neka su u = x1x2 . . .xn i v = y1y2 . . . ym reci nad alfabetom X, pri cemu sux1, . . .xn, y1, . . . , ym X. Reci u i v su jednake ako su jednake kao nizovi, tj. akoje m = n i xi = yi, za svaki i {1,2, . . . ,n}.

    Osnovna operacija nad recima je operacija nadovezivanja ili konkatenacije.Konkatenacijom reci u = x1x2 . . .xn i v = y1y2 . . . ym dobijamo rec

    u v = uv = x1x2 . . .xny1y2 . . . ym.

    Ova operacija je asocijativna i uvodimo sledece oznake:

    x0 = e, x1 = x i xk = xx . . .xk

    .

    Reverzna rec date reci u = x1x2 . . .xn jeste rec u = xn . . .x2x1.Jezik je proizvoljan skup reci nad datim alfabetom ukljucujuci i prazan

    skup.Skup svih reci, ukljucujuci i praznu rec, nad proizvoljnim alfabetom

    X, oznacicemo sa X. Sa X+ oznacavamo X \ {e}. Skup X+ sa operacijomnadovezivanja predstavlja polugrupu koju nazivamo polugrupa reci, dok jeX, u odnosu na operaciju konkatenacijemonoid sa jedinicom e koji