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

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

Дефиниције

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

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

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

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

Својства затворења

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

• Клинијева звезда $L^{*}$ над L
• Конкатенација $L\circ P$ L и P
• унија $L\cup P$
• пресек $L\cap P$

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

Види још

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

Спољашње везе

• Класе RE на сајту Complexity Zoo

Литература

• Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
• Kozen, D.C. (1997), Automata and Computability, Springer.