| Title | Problemi odluke u teoriji formalnih jezika |
| Author | Ivana Čepo |
| Mentor(s) | Milica Klaričić Bakula (thesis advisor)
|
| Abstract | U ovom diplomskom radu proučavamo probleme odluke vezane uz konačne automate, kontekstno slobodne gramatike, Turingove strojeve te linearno ograničene automate. Opisana je metoda dijagonalizacije za dokazivanje neodlučivosti problema prihvaćanja. Nadalje, Postovim problemom korespodencije pokazano je da problemi odluke nisu vezani samo uz teoriju izračunljivosti. Uvedena je metoda reducibilnosti, metoda računalne povijesti za dokazivanje neodlučivosti te reducibilnost preslikavanjem za dokazivanje Turing prihvatljivosti određenih jezika. Teorem o rekurziji koji ima važne primjene u teorijama odlučivosti dokazuje nam da Turingov stroj može dobiti svoj vlastiti opis i onda računati s njim. Nadalje, povezani su problemi odluke s odlučivim teorijama u kojima se odlučivost odnosi na provjeru istinitosti neke tvrdnje. |
| Keywords | decidable problems nondecidable problems reducibility reduction history of computation |
| Parallel title (English) | Decision problems in formal language theory |
| Committee Members | Milica Klaričić Bakula (committee chairperson)
Jurica Perić (committee member)
Marija Bliznac Trebješanin (committee member)
|
| Granter | University of Split
University of Split, Faculty of science |
| Lower level organizational units | Department of Mathematics |
| Place | Split |
| State | Croatia |
| Scientific field, discipline, subdiscipline | NATURAL SCIENCES
Mathematics
|
| Study programme type | university |
| Study level | graduate |
| Study programme | Mathematics; specializations in: major in pure mathematics, major in computing, major in teaching |
| Study specialization | major in computing |
| Academic title abbreviation | mag. math. |
| Genre | master's thesis |
| Language | Croatian |
| Defense date | 2018-01-31 |
| Parallel abstract (English) | In this master’s thesis we study decision problems related to finite automata, contex free grammars, Turing machines and linear bounded automata. It described diagonalization method for proving undecidability of decision problems. Further, with Post problem correspodence it showed that decision problems aren’t relate only with theory of computation. It introduced the theory of reducibility, the history method of reducibility for proving the undecidability and mapping reducibility for proving Turing acceptables of certain languages. Recursion theorem which has important application in theories of decidability proof us that Turing machine can obtain its own description and then compute with it. Finally, the problems od decidability related with theories of decidability in which decidability refers on review the truthfulness of some assertions. |
| Parallel keywords (Croatian) | odlučivost neodlučivost reducibilnost redukcija povijest računanja |
| Resource type | text |
| Access condition | Access restricted to students and staff of home institution |
| Terms of use |  |
| URN:NBN | https://urn.nsk.hr/urn:nbn:hr:166:658795 |
