Рекурзивно пребројив језик

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

У математици, логици и рачунарству, рекурзивно пребројив језик је тип формалног језика који се такође назива и парцијално одлучивим или Тјуринг-препознатљивим. Познат је као језик типа 0 у хијерархији Чомског која категорије формалне језике. Класа свих рекурзивно пребројивих језика се назива RE.

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

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

  1. Рекурзивно пребројив формални језик је рекурзивно пребројив подскуп у скупу свих могућих речи над азбуком језика.
  2. Рекурзивно пребројив језик је формални језик за који постоји Тјурингова машина (или нека друга израчунљива функција) која може да преброји све валидне ниске језика. Треба имати у виду да ако је језик бесконачан, изабрани алгоритам за пребројавање може да буде изабран тако да избегава понављања, јер је могуће тестирати да ли је ниска која је добијена за број n већ произведена за неки број мањи од n. Ако јесте, онда се рачуна излаз за улаз n+1 уместо за n (рекурзивно), али се опет проверава да ли је тај број нов.
  3. Рекурзивно пребројив језик је формални језик за који постоји Тјурингова машина (или нека друга израчунљива функција) која ће се зауставити и прихватити сваку реч језика, а или се зауставити и одбацити или бесконачно радити за сваку реч која не припада језику. Супротност овоме су рекурзивни језици, код којих се захтева да се Тјурингова машина зауставља у свим случајевима.

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

Постова теорема показује да RE, заједно са својим комплементом co-RE, одговара првом степену аритметичке хијерархије.

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

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

Треба имати у виду да рекурзивно пребројиви језици нису затворени за разлику скупова или комплемент. Разлика скупова L\P може али не мора да буде рекурзивно пребројива. Ако је L рекурзивно пребројив онда је комплемент од L рекурзивно пребројив ако и само ако је L уједно и рекурзиван.

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

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

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

  • Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
  • Kozen, D.C. (1997), Automata and Computability, Springer.
Теорија аутомата: формални језици и формалне граматике
Хијерархија
Чомског
Граматике Језици Минимални
аутомат
Тип-0 Без ограничења Рекурзивно пребројиви Тјурингова машина
 % (без уобичајеног имена) Рекурзивни Одлучивач
Тип-1 Контекст сензитивна Контекст сензитивни Линеарно-ограничени
 % Индексирана Индексиран Угњеждени стек
Тип-2 Контекст-слободна Контекст-слободни Недетерминистички потисни
 % Детерминистичка контекст-слободна Детерминистички контекст-слободни Детерминистички потисни
Тип-3 Регуларна Регуларан Коначни
Свака категорија језика или граматика је прави подскуп категорије директно изнад ње.