Maquinas de Turing 4.4

 Lenguajes aceptados por la Maquina de Turing.

Lenguajes aceptados por una maquina Turing

Aceptan lenguajes formales que pueden ser generados por una gramática de tipo 0: recursivamente innumerable. 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.

Máquinas de Turing Deterministas y no Deterministas

La entrada de una máquina de Turing viene determinada por el estado actual y el símbolo leído, un par [estado, símbolo], siendo el cambio de estado, la escritura de un nuevo símbolo y el movimiento las acciones a tomar en función de una entrada. En el caso de que para cada par estado y símbolo posible exista a lo sumo una posibilidad de ejecución, se dirá que es una máquina de Turing determinista, mientras que en el caso de que exista al menos un par [estado, símbolo] con más de una posible combinación de actuaciones se dirá que se trata de una máquina de Turing no determinista.

La función de transición δ en el caso no determinista, queda definida como sigue:

¿Cómo sabe una máquina no determinista cuál de las varias actuaciones tomar? Hay dos formas de verlo: una es decir que la máquina es "el mejor adivino posible", esto es, que siempre elige la transición que eventualmente la llevará a un estado final de aceptación. La otra es imaginarse que la máquina se "clona", bifurcándose en varias copias, cada una de las cuales sigue una de las posibles transiciones. Mientras que una máquina determinista sigue un solo "camino computacional", una máquina no determinista tiene un "árbol computacional". Si cualquiera de las ramas del árbol finaliza en un estado de aceptación, se dice que la máquina acepta la entrada.

La capacidad de cómputo de ambas versiones es equivalente; se puede demostrar que dada una máquina de Turing no determinista existe otra máquina de Turing determinista equivalente, en el sentido de que reconoce el mismo lenguaje, y viceversa. No obstante, la velocidad de ejecución de ambos formalismos no es la misma, pues si una máquina no determinista M reconoce una cierta palabra de tamaño n en un tiempo O(t(n)), la máquina determinista equivalente reconocerá la palabra en un tiempo O(2t(n)). Es decir, el no determinismo permitirá reducir la complejidad de la solución de los problemas, permitiendo resolver, por ejemplo, problemas de complejidad exponencial en un tiempo polinómico.

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 cuadrupla 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.