Llenguage recursivo

En matemàtiques, llògica i ciències de la computació, un llenguage formal (un conjunt de seqüències finitas de símbols presos d'un alfabet fix) és cridat llenguage recursivo si és un subconjunt recursivo del conjunt de totes les seqüències finitas possibles sobre l'alfabet del llenguage. És dir, un llenguage formal és recursivo si existix una màquina de Turing que sempre es deté quan donada una seqüència finita de símbols de l'alfabet del llenguage —anomenada cadena de caràcters o paraula— com a entrada, accepta solament eixes paraules que són part del llenguage i rebuja totes les atres paraules. Els llenguages recursivos també es denominen llenguages decidibles.

El concepte de decidibilidad pot ser estés a uns atres models de computació. Per eixemple, es pot parlar de llenguages decidibles en una màquina de Turing no determinista. Per lo tant, quan hi ha ambigüitat, el sinònim usat per a "llenguage recursivo" és llenguage Turing-decidible, en lloc de simplement "llenguage decidible".

La classe de tots els llenguages recursivos és a sovint cridada R, encara que este nom també és usat per a la classe RP.

Este tipo de llenguage no estava definit en la jerarquia de Chomsky. Tots els llenguages recursivos són també recursivamente enumerables. Tots els llenguages regulars, lliures de context i sensibles al context són llenguages recursivos.

Propietats de Clausura

Els llenguages recursivos són tancats baix les següents operacions. Sean L i P llenguages recursivos, llavors els següents llenguages són recursivos:

• El Pany de Kleene $L^{*}$.
• L'image de φ(L) baix un morfismo i-lliure φ.
• La concatenació $L\circ P$.
• L'unió $L\cup P$.
• L'intersecció $L\cap P$.
• El complement de $L$.
• La diferència simètrica L Δ P.
• La diferència $L-P$.

L'última propietat ve del fet que el conjunt diferencia pot ser expressat en interseccions i complements.

Vore també

• Decidibilidad
• Llenguage recursivamente enumerable
• Recursión

Bibliografia

• Michael Sipser (1997). «Decidability», Introduction to the Theory of Computation, PWS Publishing, pp. 151–170. ISBN 0-534-94728-X.
• (1959).«On certain formal properties of grammars».Information and Control.2(2)

137–167.doi:10.1016/S0019-9958(59)90362-6.