En matemáticas, lógica y ciencias de la computación, un lenguaje formal (un conjunto de secuencias finitas de símbolos tomados de un alfabeto fijo) es llamado lenguaje recursivo si es un subconjunto recursivo del conjunto de todas las secuencias finitas posibles sobre el alfabeto del lenguaje. Es decir, un lenguaje formal es recursivo si existe una máquina de Turing que siempre se detiene cuando dada una secuencia finita de símbolos del alfabeto del lenguaje - llamada cadena de caracteres, o palabra - como entrada, acepta solo esas palabras que son parte del lenguaje y rechaza todas las otras palabras. Los lenguajes recursivos También se denominan lenguajes decidibles.
El concepto de decidibilidad puede ser extendido a otros modelos de computación. Por ejemplo, se puede hablar de lenguajes decidibles en una máquina de Turing no determinista. Por lo tanto, cuando una ambigüedad es posible, el sinónimo usado para "lenguaje recursivo" es lenguaje Turing decidible, en vez de simplemente "lenguaje decidible".
La clase de todos los lenguajes recursivos es a menudo llamada R, aunque este nombre también es usado para la clase RP.
Los Lenguajes Recursivos son cerrados bajo las siguientes operaciones. Sean L y P lenguajes recursivos, entonces los siguientes lenguajes son recursivos:
La Cerradura de Kleene
La imagen de φ(L) bajo un e-free homomorphism φ
La concatenacion
La unión
La intersección
El complemento de
La diferencia simétrica L Δ P
La diferencia
La última propiedad viene del hecho que el conjunto diferencia puede ser expresado con intersecciones y complementos.
Referencias
Michael Sipser (1997). «Decidability». Introduction to the Theory of Computation. PWS Publishing. pp. 151–170. ISBN0-534-94728-X.
Chomsky, Noam (1959). «On certain formal properties of grammars». Information and Control2 (2): 137-167. doi:10.1016/S0019-9958(59)90362-6.
lenguaje, recursivo, matemáticas, lógica, ciencias, computación, lenguaje, formal, conjunto, secuencias, finitas, símbolos, tomados, alfabeto, fijo, llamado, lenguaje, recursivo, subconjunto, recursivo, conjunto, todas, secuencias, finitas, posibles, sobre, al. En matematicas logica y ciencias de la computacion un lenguaje formal un conjunto de secuencias finitas de simbolos tomados de un alfabeto fijo es llamado lenguaje recursivo si es un subconjunto recursivo del conjunto de todas las secuencias finitas posibles sobre el alfabeto del lenguaje Es decir un lenguaje formal es recursivo si existe una maquina de Turing que siempre se detiene cuando dada una secuencia finita de simbolos del alfabeto del lenguaje llamada cadena de caracteres o palabra como entrada acepta solo esas palabras que son parte del lenguaje y rechaza todas las otras palabras Los lenguajes recursivos Tambien se denominan lenguajes decidibles El concepto de decidibilidad puede ser extendido a otros modelos de computacion Por ejemplo se puede hablar de lenguajes decidibles en una maquina de Turing no determinista Por lo tanto cuando una ambiguedad es posible el sinonimo usado para lenguaje recursivo es lenguaje Turing decidible en vez de simplemente lenguaje decidible La clase de todos los lenguajes recursivos es a menudo llamada R aunque este nombre tambien es usado para la clase RP Este tipo de lenguaje no estaba definido en la jerarquia de Chomsky Todos los lenguajes recursivos son tambien recursivamente enumerables Todos los lenguajes regulares libres de contexto y sensible al contexto son lenguajes recursivos Propiedades de Clausura EditarLos Lenguajes Recursivos son cerrados bajo las siguientes operaciones Sean L y P lenguajes recursivos entonces los siguientes lenguajes son recursivos La Cerradura de Kleene L displaystyle L La imagen de f L bajo un e free homomorphism f La concatenacion L P displaystyle L circ P La union L P displaystyle L cup P La interseccion L P displaystyle L cap P El complemento de L displaystyle L La diferencia simetrica L D P La diferencia L P displaystyle L P La ultima propiedad viene del hecho que el conjunto diferencia puede ser expresado con intersecciones y complementos Referencias EditarMichael Sipser 1997 Decidability Introduction to the Theory of Computation PWS Publishing pp 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 Vease tambien EditarLenguaje recursivamente enumerable Recursion Datos Q1455907 Obtenido de https es wikipedia org w index php title Lenguaje recursivo amp oldid 134862551, wikipedia, wiki, leyendo, leer, libro, biblioteca,
