Rekurzivni jezik

Sa Wikipedije, slobodne enciklopedije
(Preusmjereno sa Odlučiv jezik)
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.

U matematici, logici i računarstvu, rekurzivni jezik je tip formalnog jezika koji se još zove i rekurzivan, odlučiv ili Turing-odlučiv. Klasa svih rekurzivnih jezika se često zove R, iako je to ime često korišteno i za klasu složenosti RP.

Ovaj tip jezika nije definisan u Chomskyjevoj hijerarhiji.

Definicije[uredi | uredi izvor]

U literaturi prevladavaju dvije definicije koncepta rekurzivnog jezika:

  1. Rekurzivni formalni jezik je rekurzivni podskup skupa svih mogućih riječi nad abecedom jezika.
  2. Rekurzivni jezik je formalni jezik za kojeg postoji Turingova mašina koja će, za svaki ulazni niz znakova (simbola) stati i prihvatiti niz ukoliko je on element jezika, a inače ga neće prihvatiti. Turingova mašina uvijek staje - poznata i pod nazivom odlučitelj - i kažemo da odlučuje rekurzivni jezik.

Svi rekurzivni jezici su rekurzivno prebrojivi. Svi regularni, kontekstno nezavisni i kontekstno zavisni jezici su rekurzivni.

Svojstva zatvorenosti[uredi | uredi izvor]

Rekurzivni su jezici zatvoreni nad sljedećim operacijama. To jest, ako su L i P dva rekurzivna jezika, tada su i sljedeći jezici također rekurzivni:

  • Kleeneov operator L^* jezika L
  • neprebrisujući homeomorfizam φ(L) jezika L
  • nadovezivanje (konkatenacija) L \circ P jezika L i jezika P
  • unija L \cup P
  • presjek L \cap P
  • komplement jezika L
  • razlika L - P

Posljednje svojstvo slijedi iz činjenice da se razlika skupova može izraziti preko presjeka i komplementa.

Reference[uredi | uredi izvor]