Рекурзивни језик у математици, логици и рачунарству је тип формалног језика који се још назива и одлучивим или Тјуринг-одлучивим. Класа свих рекурзивних језика сее често назива -{R}-, мада се ово име користи и за класу -{RP}-.
Овај тип језика није дефинисан у хијерархији Чомског .
Дефиниције Постоје две главне еквивалентне дефиниције за концепт рекурзивног језика: Рекурзивни формални језик је рекурзиван подскуп у скупу свих могућих речи над азбуком језика. Рекурзивни језик је формални језик за који постоји Тјурингова машина која ће када јој се да било која улазна ниска да стане и прихвати ниску ако она припада језику, а да стане и одбаци ниску у супротном. Тјурингова машина се увек зауставља; позната је као одлучивач, и каже се да она одлучује рекурзивни језик.
Сви рекурзивни језици су и рекурзивно пребројиви. Сви регуларни, контекстно-слободни и контекстно-сензитивни језици су рекурзивни.
Својства затворења Рекурзивни језици су затворени у односу на следеће операције. Другим речима, ако су -{L}- и -{P}- два рекурзивна језика, онда су и следећи језици рекурзивни: Клинијева звезда слика од -{φ(L)}- у односу на -{e}--слободни хомоморфизам -{φ}- конкатенација унија пресек комплемент од -{L}- разлика скупова
Последње својство следи из чињенице да се разлика скупова може изразити помоћу пресека и комплемента.
Види још Рекурзивно пребројив језик Рекурзија Рекурзивни акроним
Референце
Литература
Категорија:Теорија рекурзије Категорија:Формални језици Категорија:Теорија израчунљивости