Lenguajes Que Cepta Una Maquina De Turing

INSTITUTO TECNOLOGICO DE NUEVO LAREDO

TEORIA DE LA COMPUTACION LENGUAJES QUE ACEPTA LA MAQUINA DE TURING

Resumen
• La máquina de Turing es más una abstracción matemática que un dispositivofísico o mecánico.

• Se le denomina "máquina" eso se debe a que su funcionamiento puede ser descrito en términos de operaciones individuales muy sencillas que sugieren una implementación real muysimple

Lenguaje aceptado por una maquina de turing
• L(M) es el lenguaje aceptado por la maquina de turing • La cadena de entrada puede ser aceptada o rechazada sin necesidad de leerse completamente• El lenguaje o problema es recursivamente enumerable o computable cuando es calculado por la maquina de turing • El lenguaje es recursivo o decidible cuando es calculado por una maquina de turing quesiempre se detiene (tanto acepta como si no lo hiciera)

LENGUAJES RECURSIVAMENTE ENUMERABLES
• Los lenguajes aceptados por una maquina de turing se les conoce como LENGUAJES RECURSIVAMENTEENUMERABLES (RE) • El termino “Enumerable” proviene de que una maquina de turing puede listar o enumerar las cadenas del lenguaje • Los Lenguajes recursivamente enumerables es un conjunto de lenguajesbastante grande, incluye a los Lenguajes independientes de contexto.

LENGUAJES RECURSIVAMENTE ENUMERABLES
• Se detiene con cualquier cadena de lenguaje • La cual puede parar y rechazar o iterarindefinidamente con una cadena que no pertenece al lenguaje en contra a lenguajes recursivos

• Por lo que la maquina de turing se detendrá en todos los casos

TODOS LOS LENGUAJES
• REGULARES

•INDEPENDIENTES DE CONTEXTO
• DEPENDIENTES DE CONTEXTO • RECURSIVOS • SON RECURSIVAMENTE ENUMERABLES

Especificación de lenguajes formales
• Los lenguajes formales tienen una amplia variedad de formas• Cadenas producidas por GRAMATICA FORMAL • Cadenas producidas por una EXPRESION REGULAR • Cadenas aceptadas por un AUTOMATA

• Las cadenas están formadas por un conjunto de símbolos que...