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

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

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

Дефиниције

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

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

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

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

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

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

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

Види још

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