6. Cuáles son los lenguajes aceptados para una Máquina de Turing. De 3 ejemplos de cadena de estos lenguajes.

Una cadena de entrada w es aceptada por una MT M si el cómputo que se indica la configuración inicial q0w termina en una configuración instantánea:
 
p es un estado de aceptación, en la cual M se detiene completamente. El lenguaje L(M) aceptado por una MT M se define como:

M se para en: 
, Si la cadena de entrada en una máquina M pertenece a L(M), la maquina M siempre se detiene.

 Aceptan lenguajes formales que pueden ser generados por una gramática de tipo 0: recursivamente innumerable (r.e) Las maquinas de turing son los reconocedores de lenguaje más poderosos que existen.

Lenguajes regulares: las gramáticas (de tipo 3) formales definen un lenguaje describiendo como se pueden generar las cadenas del lenguaje… Las gramáticas regulares (aquellos reconocidos por un autómata finito). Son las gramáticas más restrictivas. El lado derecho de una producción debe contener un símbolo Terminal y como máximo un símbolo no Terminal.

Lenguajes Libres de contexto: Estas gramáticas conocidas también como gramáticas de tipo 2 o gramáticas independientes del contexto, son las que generan los lenguajes libres o independientes del contexto. Los lenguajes libres del contexto son aquellos que pueden ser reconocidos por un autómata de pila determínistico o no determínistico. Como toda gramática se definen mediante una cuádrupla G=N, T, S, P), siendo N un conjunto finito de símbolos no terminales; T un conjunto de símbolos terminales: P un conjunto finito de producciones; S es el símbolo distinguido o axioma.

EJEMPLOS:

Ejemplo 1: Reconocimiento de un Lenguaje Regular.

  

Este es un lenguaje regular porque puede ser definido también por la expresión regular:  (a+b)b(a+b)*

Ejemplo 2: Reconocimiento de una GLC, aceptada por un APD determinista.

 

Ejemplo 3: Reconocimiento de una GLC, aceptada por un APD no determinista.

CONCLUSIONES:

Nuestro primer ejemplo era solamente un AF convertido, y el lenguaje que aceptaba era Regular.

El segundo ejemplo aceptaba un lenguaje Libre de Contexto y No Regular y la MT dada empleaba alfabetos separados para escribir y leer.

La tercera máquina aceptaba un lenguaje que era también Libre de Contexto, pero que solo podía ser aceptado por un APD No Determinístico, sin embargo la MT diseñada es Determinística.