Aunque existen varias definiciones equivalentes, ésta es una de las principales:
Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una máquina de Turing que acepta y se detiene con cualquier cadena del lenguaje. Pero que puede parar y rechazar, o bien iterar indefinidamente, con una cadena que no pertenece al lenguaje, en contraposición a los lenguajes recursivos en cuyo caso se requiere que la máquina de Turing pare en todos los casos.
Los lenguajes recursivamente enumerables son cerrados con las siguientes operaciones. Esto es, si y son dos lenguajes recursivamente enumerables, entonces los siguiente lenguajes son recursivamente enumerables también:
lenguaje, recursivamente, enumerable, matemáticas, lógica, informática, lenguaje, recursivamente, enumerable, tipo, lenguaje, formal, también, llamado, parcialmente, decidible, turing, computable, conocidos, como, lenguajes, tipo, jerarquía, chomsky, definició. En matematicas logica e informatica un lenguaje recursivamente enumerable es un tipo de lenguaje formal que es tambien llamado parcialmente decidible o Turing computable Son conocidos como lenguajes tipo 0 en la Jerarquia de Chomsky Definicion EditarAunque existen varias definiciones equivalentes esta es una de las principales Un lenguaje recursivamente enumerable es un lenguaje formal para el cual existe una maquina de Turing que acepta y se detiene con cualquier cadena del lenguaje Pero que puede parar y rechazar o bien iterar indefinidamente con una cadena que no pertenece al lenguaje en contraposicion a los lenguajes recursivos en cuyo caso se requiere que la maquina de Turing pare en todos los casos Todos los lenguajes regulares independientes de contexto dependientes de contexto y recursivos son recursivamente enumerables Propiedades de cierre EditarLos lenguajes recursivamente enumerables son cerrados con las siguientes operaciones Esto es si L displaystyle L y P displaystyle P son dos lenguajes recursivamente enumerables entonces los siguiente lenguajes son recursivamente enumerables tambien el cierre estrella L displaystyle L de L displaystyle L la concatenacion L P displaystyle L circ P de L displaystyle L y P displaystyle P la union L P displaystyle L cup P de L displaystyle L y P displaystyle P la interseccion L P displaystyle L cap P de L displaystyle L y P displaystyle P Notese que los lenguajes recursivamente enumerables no son cerrados con la diferencia ni el complementario L P displaystyle L setminus P puede no ser recursivamente enumerable L displaystyle bar L es recursivamente enumerable si y solo si L displaystyle L es tambien recursivo Vease tambien EditarLenguaje recursivo Datos Q1073063Obtenido de https es wikipedia org w index php title Lenguaje recursivamente enumerable amp oldid 128536502, wikipedia, wiki, leyendo, leer, libro, biblioteca,
