prikaz prve stranice dokumenta Problemi odluke u teoriji formalnih jezika
Pristup korisnicima matične ustanove
diplomski rad
Problemi odluke u teoriji formalnih jezika
2018. urn:nbn:hr:166:658795
Čepo, Ivana
Sveučilište u Splitu
Prirodoslovno-matematički fakultet
Odjel za matematiku

Citirajte ovaj rad

Čepo, I. (2018). Problemi odluke u teoriji formalnih jezika (Diplomski rad). Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo, Ivana. "Problemi odluke u teoriji formalnih jezika." Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2018. https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo, Ivana. "Problemi odluke u teoriji formalnih jezika." Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, 2018. https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo, I. (2018). 'Problemi odluke u teoriji formalnih jezika', Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, citirano: 14.11.2024., https://urn.nsk.hr/urn:nbn:hr:166:658795

Čepo I. Problemi odluke u teoriji formalnih jezika [Diplomski rad]. Split: Sveučilište u Splitu, Prirodoslovno-matematički fakultet; 2018 [pristupljeno 14.11.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:166:658795

I. Čepo, "Problemi odluke u teoriji formalnih jezika", Diplomski rad, Sveučilište u Splitu, Prirodoslovno-matematički fakultet, Split, 2018. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:166:658795

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:166:658795
Prijavite se u repozitorij kako biste mogli spremiti objekt u svoju listu.
Podaci o radu
NaslovProblemi odluke u teoriji formalnih jezika
Naslov (engleski)Decision problems in formal language theory
AutorIvana Čepo
MentorMilica Klaričić Bakula (mentor)
Član povjerenstvaMilica Klaričić Bakula (predsjednik povjerenstva)
Član povjerenstvaJurica Perić (član povjerenstva)
Član povjerenstvaMarija Bliznac Trebješanin (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Splitu
Prirodoslovno-matematički fakultet
(Odjel za matematiku)
Split
Datum i država obrane2018-01-31, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		PRIRODNE ZNANOSTI
Matematika
Sažetak
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.
Sažetak (engleski)
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.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:166:658795
Studijski programNaziv: Matematika; smjerovi: teorijski, računarski, nastavnički
Smjer: računarski
Vrsta studija: sveučilišni
Stupanj studija: diplomski
Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaPristup korisnicima matične ustanove
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Datum i vrijeme pohrane2018-06-20 15:08:19