Рекурзивни језик

Из Википедије, слободне енциклопедије

Рекурзивни језик у математици, логици и рачунарству је тип формалног језика који се још назива и одлучивим или Тјуринг-одлучивим. Класа свих рекурзивних језика сее често назива R, мада се ово име користи и за класу RP.

Овај тип језика није дефинисан у хијерархији Чомског Chomsky 1959.

Дефиниције[уреди]

Постоје две главне еквивалентне дефиниције за концепт рекурзивног језика:

  1. Рекурзивни формални језик је рекурзиван подскуп у скупу свих могућих речи над азбуком језика.
  2. Рекурзивни језик је формални језик за који постоји Тјурингова машина која ће када јој се да било која улазна ниска да стане и прихвати ниску ако она припада језику, а да стане и одбаци ниску у супротном. Тјурингова машина се увек зауставља; позната је као одлучивач, и каже се да она одлучује рекурзивни језик.

Сви рекурзивни језици су и рекурзивно пребројиви. Сви регуларни, контекстно-слободни и контекстно-сензитивни језици су рекурзивни.

Својства затворења[уреди]

Рекурзивни језици су затворени у односу на следеће операције. Другим речима, ако су L и P два рекурзивна језика, онда су и следећи језици рекурзивни:

Последње својство следи из чињенице да се разлика скупова може изразити помоћу пресека и комплемента.

Види још[уреди]

Литература[уреди]

  • Michael Sipser (1997). „Decidability“. Introduction to the Theory of Computation. PWS Publishing. стр. 151-170. ISBN 0-534-94728-X. 
  • Chomsky, Noam (1959). „On certain formal properties of grammars“. Information and Control 2 (2): 137-167. DOI:10.1016/S0019-9958(59)90362-6. 

Спољашње везе[уреди]

Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.