prikaz prve stranice dokumenta Problemi odluke u teoriji formalnih jezika
Access restricted to students and staff of home institution
master's thesis
Problemi odluke u teoriji formalnih jezika
Split: University of Split, University of Split, Faculty of science, 2018. urn:nbn:hr:166:658795
Čepo, Ivana
University of Split
Faculty of Science
Department of Mathematics

Institutional repository: Repository of Faculty of Science

Cite this document

Čepo, I. (2018). Problemi odluke u teoriji formalnih jezika (Master's thesis). Split: University of Split, Faculty of Science. Retrieved from https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo, Ivana. "Problemi odluke u teoriji formalnih jezika." Master's thesis, University of Split, Faculty of Science, 2018. https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo, Ivana. "Problemi odluke u teoriji formalnih jezika." Master's thesis, University of Split, Faculty of Science, 2018. https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo, I. (2018). 'Problemi odluke u teoriji formalnih jezika', Master's thesis, University of Split, Faculty of Science, accessed 28 February 2025, https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo I. Problemi odluke u teoriji formalnih jezika [Master's thesis]. Split: University of Split, Faculty of Science; 2018 [cited 2025 February 28] Available at: https://urn.nsk.hr/urn:nbn:hr:166:658795

I. Čepo, "Problemi odluke u teoriji formalnih jezika", Master's thesis, University of Split, Faculty of Science, Split, 2018. Available at: https://urn.nsk.hr/urn:nbn:hr:166:658795

Metadata
TitleProblemi odluke u teoriji formalnih jezika
Title (english)Decision problems in formal language theory
AuthorIvana Čepo
MentorMilica Klaričić Bakula (mentor)
Committee memberMilica Klaričić Bakula (predsjednik povjerenstva)
Committee memberJurica Perić (član povjerenstva)
Committee memberMarija Bliznac Trebješanin (član povjerenstva)
GranterUniversity of Split
Faculty of Science
(Department of Mathematics)
Split
Defense date and country2018-01-31, Croatia
Scientific / art field,
discipline and subdiscipline		NATURAL SCIENCES
Mathematics
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.
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:166:658795
Study programmeTitle: Mathematics; specializations in: major in pure mathematics, major in computing, major in teaching
Course: major in computing
Study programme type: university
Study level: graduate
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourceText
File originBorn digital
Access conditionsAccess restricted to students and staff of home institution
Terms of useLicence In copyright icon
Created on2018-06-20 15:08:19