Access restricted to students and staff of home institution
master's thesis
21   0
Decision problems in formal language theory
Ivana Čepo (2018)
University of Split
University of Split, Faculty of science
Department of Mathematics
Cite this document...

Čepo, I. (2018). Problemi odluke u teoriji formalnih jezika (Master's thesis). 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, 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, 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, University of Split, Faculty of science, accessed 23 March 2019, https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo I. Problemi odluke u teoriji formalnih jezika [Master's thesis]. Split: University of Split, University of Split, Faculty of science; 2018 [cited 2019 March 23] 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, 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
University 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: Matematika; smjerovi: teorijski, računarski, nastavnički
Study programme type: sveučilišni
Study level: diplomski
Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
Type of resourcetext
File originBorn digital
Access conditionsRestricted access
Terms of usehttp://rightsstatements.org/vocab/InC/1.0/
Created on2018-06-20 15:08:19