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 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.
Ejemplo1
Aquí se describe una MT M2 que reconoce el lenguaje consistente de todas las cadenas de 0s cuya longitud es una potencia de 2. La MT decide el lenguaje A = { 02n | n ≥ 0}.
M2 = “Sobre la cadena de entrada w:
1. Recorrer la cinta de izquierda a derecha, marcando un cero si y otro no.
2. Si en el paso 1 la cinta contiene sólo un cero, aceptar.
3. Si en el paso 1 la cinta contiene más de un cero y la cantidad de ceros es impar, rechazar.
4. Regresar la cabeza de la cinta hasta la posición más a la izquierda.
5. Ir al paso 1.”
· Q = { q1, q2, q3, q4, q5, qaceptar, qrechazar }
· Σ = { 0 }
· Γ = { 0, x, Џ }
· δ se describe en el diagrama de estados de la figura 4.4
· Los estados inicial de aceptación y rechazo son q1, qaceptar, qrechazar, respectivamente
En la figura 4.4 la etiqueta 0 →Џ, R aparece en la transición de q1 a q2. Esto significa que, cuando M2 se encuentra en el estado q1 con la cabeza de la cinta leyendo un 0, la máquina va al estado q2, escribe Џ y mueve la cabeza de la cinta a la derecha (R). En otras palabras δ(q1, 0) = (q2, Џ, R). Para mayor claridad se usa 0 → R en la transición de q3 a q4, lo cual significa que M2 se mueve a la derecha cuando lee un 0 en el estado q3, pero no altera la cinta, δ(q3, 0) = (q4, 0, R).
A continuación podemos ver una corrida de M2 sobre la cadena de entrada 0000.
Ejemplo2
El siguiente ejemplo es una descripción formal de M1 = (Q, Σ, Γ, δ, qo, qaceptar, qrechazar). La máquina de Turing que decide el lenguaje B = { w#w | w Є { 0, 1 } * }.
· Q = { q1, q2, … , q14, qaceptar, qrechazar }
· Σ = { 0, 1, # }
· Γ = { 0, 1, #, x, Џ }
· δ se describe en el diagrama de estados de la figura 4.5
· Los estados inicial de aceptación y rechazo son q1, qaceptar, qrechazar, respectivamente
·
Ejemplo 3
La máquina de Turing M4 resuelve el llamado problema de la distinción. Se da una lista de cadenas sobre { 0, 1 } separadas por # y su trabajo es aceptar si todas las cadenas son distintas. EL lenguaje es
E = { #x1#x2# … #xk | cada xi Є { 0,1 }* y xi ≠ xj para cada i ≠ j }.
M4 = “Sobre la cadena de entrada w:
1. Colocar una marca en el símbolo más a la izquierda en la cinta. Si dicho símbolo es un blanco, aceptar. Si dicho símbolo es un #, continuar al siguiente paso. De otra manera, rechazar.
2. Barrer a la derecha hasta el siguiente # y colocar una segunda marca sobre este. Si no se encuentra otro # antes de un símbolo blanco, sólo xi está presente, entonces aceptar.
3. Con movimientos de zig-zag, comparar las dos cadenas a la derecha de los símbolos # marcados. Si son iguales, rechazar.
4. Mover la marca más a la derecha hacia el siguiente #. Si no se encuentra otro # antes de un símbolo blanco, mover la marca más a la izquierda al siguiente # y la segunda marca a un lado. Si no se encuentra otro # para la marca más a la derecha, significa que ya han sido comparadas todas las cadenas, aceptar.
5. Ir al paso 3.”
es la siguiente, sea:
