CLASE 41 MT Especiales-LRE-LR

Vista previa del material en texto

ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
CONSTRUCCIÓN DE UNA MT:
Como se pudo comprobar mediante los ejemplos vistos oportunamente, 
las MT pueden desempeñar muchas actividades además de 
reconocimiento de lenguajes. También dijimos que esta máquina se 
toma como modelo teórico de las computadoras y que cualquier 
problema que tenga solución algorítmica tiene una MT asociada.
Veremos ahora como construir una MT capaz de realizar alguna tarea 
compleja a partir de la combinación de otras MT sencillas.
La idea básica consiste en combinar dos MT permitiendo que 
compartan la misma cinta, de tal modo que cuando una termine su 
ejecución la otra comience, tomando como secuencia inicial y posición 
del cabezal de lectura/escritura, la que dejó la primer MT.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
CONSTRUCCIÓN DE UNA MT:
Composición de Máquinas de Turing: Sean MT1 y MT2 dos MT sobre 
el mismo alfabeto E y el mismo alfabeto auxiliar A , donde:
MT1 =  Q1 , E , A , q01 , F1 , f1 
MT2 =  Q2 , E , A , q02 , F2 , f2 
con Q1 y Q2 son disjuntos.
La composición de MT1 y MT2 es la máquina de Turing MT3 con 
componentes: MT3 =  Q1  Q2 , E , A , q01 , F2 , f3  y
f1(q, e) si qQ1 y f1(q, e)  (p, s, m)  pF1
f3(q, e) = f2(q, e) si qQ2
(q02, s, m) si qQ1 y f1(q, e) = (p, s, m) y pF1
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
EJEMPLOS DE CONSTRUCCIÓN DE MT:
Los siguientes son ejemplos de MT sencillas con alfabeto de entrada 
{a, b} , que realizan tareas básicas sobre la cinta:
M1: MT que busca el primer M2: MT que escribe una “a”
blanco de la derecha. en el casillero actual.
(a,a,D)
(,,D)
11 12
(b,b,D)
(a,a,N)
21 22
(,a,N)
(b,a,N)
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
EJEMPLOS DE CONSTRUCCIÓN DE MT:
M3: MT que mueve el cabezal M4: MT que permite bifurcar 
un lugar a la izquierda. según lea una “a” o una “b”
(a,a,I)
(,,I)
31 32
(b,b,I)
(a,a,D)
41
43
(b,b,D)
42
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
EJEMPLOS DE CONSTRUCCIÓN DE MT:
M5: MT que escribe una “a” después del segundo espacio en blanco a la 
derecha. Esto se logra con la composición M1-M1-M2.
(a,a,D)
(,,D)
51
(b,b,D)
(a,a,D)
(,,D)
52
(b,b,D)
(a,a,N)
53 54
(,a,N)
(b,a,N)
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
EJEMPLOS DE CONSTRUCCIÓN DE MT:
M6: MT que si la secuencia comienza con “b” lo cambia por “a” y sino 
escribe una “a” después del primer blanco de la derecha. Esto se 
logra con una composición M4-(M3 / M1)-M2.
(a,a,D)
61
(b,b,D)
(a,a,I)
(,,I)
63
(b,b,I)
(a,a,D)
(,,D)62
(b,b,D)
(a,a,N)
64 65
(,a,N)
(b,a,N)
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
VARIANTES DE LAS MT:
Con el objetivo de simplificar el diseño de MT para problemas más
complejos, se puede plantear variaciones de la MT. Dentro de las más
usuales se encuentran las MT Multicinta y las MT Multipista.
Las primeras constan de N cintas infinitas con N cabezales
independientes, de tal modo que inicialmente se escribe secuencias de
entrada en las N cintas y los cabezales comienzan en una posición
determinada de las cintas, normalmente en el extremo izquierdo de las
secuencias de entrada. El control de cada uno de los N cabezales se
hace en forma independiente mediante N Funciones de Transición
similares a una MT de una sola cinta.
En el caso de la MT Multipista, la única diferencia es que los cabezales
están restringidos a realizar todos juntos el mismo movimiento.
Lenguajes, Gramáticas y 
Modelos Generales.
U.T.N. – F.R.T. 
S. y S. de los L. 
VARIANTES DE LAS MT:
Como ejemplo veamos la solución para reconocimiento del lenguaje
anbncn, con MT Simple y con MT Multicinta:
Lenguajes, Gramáticas y 
Modelos Generales.
Podemos ver que la versión Multicinta resulta
más eficiente.
ING. JORGE BUABUD
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
LOS ACEPTORES DE LENGUAJES:
Comprobación de pertenencia: La comprobación de pertenencia 
responde al problema de verificar si una palabra w dada está incluida 
en el lenguaje que genera una gramática G. Este problema es de 
fundamental importancia al encarar el diseño de la etapa de análisis 
de cualquier programa traductor de lenguajes. 
Se puede afirmar que este problema siempre tiene solución para 
los lenguajes de tipo 1 o LDC, y por jerarquía de Chomsky para los 
lenguajes de tipo 2 o LIC y los lenguajes de tipo 3 o LR.
Sin embargo, para los lenguajes de tipo 0 o LI no existe un 
algoritmo general que permita comprobar la pertenencia de una 
palabra w a un lenguaje generado por una gramática irrestricta.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
LOS ACEPTORES DE LENGUAJES:
La dificultad que se presenta en las GI es la permisividad de reglas 
compresoras. El problema se plantea cuando se desea obtener 
todas las palabras de longitud menor o igual a N. En este caso las 
secuencias intermedias que se van obteniendo en el proceso de 
derivación pueden disminuir de longitud, entonces no se sabrá con 
seguridad cuando terminar este proceso y de esta forma entrar en 
un posible lazo infinito.
Este inconveniente se relaciona con el llamado “PROBLEMA DE 
LA PARADA DE LA MT” (The Halting Problem), que constituye 
el primer problema sin solución algorítmica demostrable.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
PROBLEMA DE LA PARADA DE LA MT:
La MT fue ideada en la década de 1930 por el matemático inglés Alan 
Mathison Turing , con el objetivo de responder al problema central de la 
Teoría de la Computación. Este problema consiste en encontrar formas 
de representación de procesos, de manera tal que siempre sea posible 
decir si el proceso se puede representar algorítmica-mente o no. En 
otras palabras, la tesis de Turing pretendía demostrar que no todo 
problema bien definido tiene una solución algorítmica.
Para ello supuso que su modelo era una forma de representación de la 
solución algorítmica de un problema. Codificó esta máquina y la colocó 
como entrada de otra MT, a la cual se conoce como Máquina Universal 
de Turing (MUT), que debía ser capaz de determinar si la MT codificada 
se detendría o no ante cualquier secuencia de entrada. 
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
PROBLEMA DE LA PARADA DE LA MT:
La MUT se considera como un modelo de modelos, ya que nos permitiría analizar 
el comportamiento de otra MT.
La prueba realizada por Turing , que se conoce como “el problema de parada o 
detención de la MT” (The Halting Problem), consistió en suponer una MT1 que 
recibe como secuencia de entrada la codificación de otra máquina MT0 y 
determinar si ésta se va a detener o no para cualquier entrada válida de la misma. 
De tal modo que también será capaz de hacerlo para la codificación de si misma, es 
decir que podrá determinar si MT1 se detendrá para cualquier secuencia de 
entrada. Luego supuso una MT2 que se detiene si MT0 no lo hace y viceversa. 
Esto se puede lograr haciendo que MT2 entre en un ciclo infinito cuando MT0 se 
detiene.
Bajo estas suposiciones ¿qué sucede si MT2 trabaja sobre la codificación de si 
misma?. Pues sucederá que MT2 se detendrá si MT2 no se detiene y no se 
detendrá si MT2 se detiene. O sea una contradicción total.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
PROBLEMA DE LA PARADA DE LA MT:
Estesimple razonamiento demuestra por el absurdo, que tal máquina no 
puede existir. Lo que a su vez equivale a decir que “el problema de la 
parada de la máquina de Turing” no puede ser resuelto algorítmicamente.
Utilizando el problema de la parada de la MT como referencia, se ha 
probado que otros problemas son también insolubles. Entre los más 
conocidos, tenemos los siguientes:
✓ El problema de la equivalencia de las gramáticas libres de contexto.
✓ La ambigüedad de las GLC.
✓ La comprobación de pertenencia para gramáticas sin restricciones.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
LOS ACEPTORES DE LENGUAJES:
Para demostrar que siempre es posible resolver el problema de 
comprobación de pertenencia para GDC, GIC y GR, vamos a 
definir el siguiente algoritmo constructivo:
Dada una G = N, T, P, S y una palabra w de longitud N:
1)T0 = { S }
2)Tk = Tk-1  {  / ||  N   Tk-1     }
3)Repetir 2) hasta que: (Tk==Tk-1) o (wTk)
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
LOS ACEPTORES DE LENGUAJES:
Veamos a continuación un ejemplo de aplicación de este 
algoritmo con la GDC vista anteriormente y la palabra “abbc”:
G =  N , T , P, S 
N = { S, T, B, D } T = { a, b, c }
P: 1) S → T , 2) DB → BD , 3) D → c , 4) T → aTBD , 5) T → abD , 6) bB → bb
T0 = { S }
T1 = { S, T }
T2 = { S, T, aTBD, abD }
T3 = { S, T, aTBD, abD, aTBc, abc }
T4 = T3
Como vemos el algoritmo 
se detiene con un 
resultado negativo en 
cuanto a la comprobación 
de pertenencia de “abbc”
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
APLICACIÓN: Resolubilidad y Complejidad.
Función Computable: Una función “f” se dice Turing 
Computable o simplemente Computable, si para la misma existe 
una MT que es capaz de obtener el valor de f(w) para todo w 
perteneciente al dominio de “f”. 
Problemas de decisión: Son aquellos problemas cuyo resultado 
se puede representar con una función de rango binario con 
valores (falso/cierto, si/no, 0/1). 
Resolubilidad o “Decidibilidad”: Cuando un problema de 
decisión es computable por una MT se dice que es decidible o 
resoluble, de lo contrario se dice que es indecidible o irresoluble.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
APLICACIÓN: Resolubilidad y Complejidad.
Lenguajes Recursivamente Enumerables: Los lenguajes generados 
solo por gramáticas irrestrictas o de Tipo 0 según Jerarquía de 
Chomsky, se conocen como lenguajes irrestrictos o recursivamente 
enumerables, debido a que sus palabras se pueden generar 
mediante la aplicación de reglas gramaticales recursivas sobre la 
cinta de una MT. Esto a la vez permite que una MT sea capaz de 
reconocer las palabras de un LRE, por lo que se dice que son 
“aceptables” por una MT.
Como vimos en oportunidad de estudiar las MT, existen secuencias 
del universo del lenguaje aceptado que pueden producir un bucle 
infinito. Esto significa que los complementos de algunos LRE no 
son aceptables por una MT y por lo tanto no son LRE.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
APLICACIÓN: Resolubilidad y Complejidad.
Lenguajes Recursivos: Los LRE cuyos complementos también son 
LRE o sea aceptables por una MT, se conocen como Lenguajes 
Recursivos. Se dice que estos lenguajes son “decidibles” por una 
MT, ya que todas las palabras del universo del lenguaje producen la 
detención o parada de la MT. 
O sea que el problema de decisión que plantea la comprobación de 
pertenencia para Lenguajes Recursivos, siempre tiene solución 
algorítmica y por lo tanto es resoluble o decidible. 
También podemos afirmar que el conjunto de Lenguajes 
Dependientes del Contexto o de Tipo 1, es un subconjunto de los 
Lenguajes Recursivos.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
APLICACIÓN: Resolubilidad y Complejidad.
Propiedades de los lenguajes aceptables y decidibles por MT:
Se puede afirmar que los LRE son cerrados para las 
operaciones de intersección, unión, concatenación y estrella 
de Kleene, no así para el complemento.
En el caso de los Lenguajes Recursivos se puede demostrar 
que son cerrados para todas las operaciones mencionadas 
anteriormente.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
APLICACIÓN: Resolubilidad y Complejidad.
Complejidad Algorítmica:
La complejidad de un algoritmo se puede medir en lo temporal y en 
lo espacial.
Desde un punto de vista teórico la complejidad temporal se mide en 
función de la cantidad de pasos que lleva una MT asociada al 
algoritmo, en detenerse. Se distingue aquellos algoritmos que 
tienen un tiempo de ejecución acotado por una función polinomial, 
los que se detienen en un tiempo razonable; de aquellos cuya 
cantidad de pasos aumenta exponencialmente, provocando demoras 
en su ejecución que pueden resultar totalmente imprácticas. 
En cuanto a la complejidad espacial se suele medir en función de la 
cantidad de casilleros que utilizaría la MT asociada al algoritmo.
Lenguajes, Gramáticas y 
Modelos Generales.