CLASE 39 MT y ALL

Vista previa del material en texto

ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L. 
Alan Mathison Turing:
Alan M. Turing fue un brillante matemático, 
criptoanalista e informático teórico, de nacionalidad 
inglesa. Nació el 23 de Junio de 1912 en Maida Vale 
un distrito residencial al oeste de Londres y falleció 
en la misma ciudad un 7 de Junio de 1954.
Dentro de los importantes aportes realizados por 
Turing, podemos destacar:
1) Formalizó los conceptos de algoritmo y computación con su Máquina 
de Turing.
2) Es considerado el padre de la Inteligencia Artificial.
3) Fue clave su participación en el equipo de criptoanálisis de la máquina 
de criptografía alemana Enigma.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
Lenguajes, Gramáticas y 
Modelos Generales.
U.T.N. – F.R.T. 
S. y S. de los L.
MÁQUINA DE TURING (MT):
La Máquina de Turing fue concebida por Alan M. Turing en 1936, como 
un modelo matemático abstracto que representa la solución de cualquier 
problema algorítmico y en particular el reconocimiento de lenguajes de 
Tipo 0 o Irrestrictos. 
Para su mejor comprensión lo representaremos con el siguiente esquema:
  e1 e2
••• ••• en-1 en 
•••• ••••
Cinta Infinita
Control
Cabezal de Lec./Esc.
0 1
2
X
3
.
. .Es
ta
d
o
s
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MÁQUINA DE TURING (MT):
El modelo dispone de una cinta infinita dividida en casilleros 
que pueden contener un símbolo cada uno. Un cabezal de 
lectura y escritura sobre la cinta. Un control que puede 
responder de distintas formas según el estado en el que se 
encuentre. 
Al comienzo la cinta esta llena de espacios en blanco () y se 
escribe la palabra que se desea analizar (ei), el cabezal está en 
la posición del primer símbolo de dicha palabra; en cuyo caso 
se dice que el control se encuentra en el ESTADO INICIAL. 
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MÁQUINA DE TURING (MT):
A partir de ese estado inicial el modelo comienza a funcionar realizando las 
siguientes acciones:
1) LEE un símbolo
2) De acuerdo al ESTADO ACTUAL y al símbolo leído:
a) ESCRIBE otro símbolo (que puede ser el mismo)
b) MUEVE el cabezal un lugar hacia la derecha o izquierda 
(eventualmente no se mueve) 
c) Transiciona a un NUEVO ESTADO (que puede ser el mismo)
3) Repite 1) y 2) hasta que se llega a alguno de los llamados ESTADOS 
FINALES, en cuyo caso se dice que la palabra escrita inicialmente es 
ACEPTADA. O hasta que se llega a un estado en el que no está definida 
una transición para el símbolo leído, en cuyo caso se dice que se produce 
un BLOQUEO de la MT y la secuencia de entrada es RECHAZADA.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MÁQUINA DE TURING (MT):
Definición formal de una MÁQUINA DE TURING:
MT =  Q , ΣE , ΣA , q0 , F , f 
Q : Conjunto finito y no vacío de estados.
ΣE: Alfabeto de símbolos de entrada.
ΣA: Alfabeto de símbolos auxiliares (incluye a “”).
q0 : Estado inicial (perteneciente a Q)
F : Conjunto de estados finales (incluido en Q)
f : Función de control o transición.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MÁQUINA DE TURING (MT):
La función de transición se define como:
f : (Q-F) x (EA)  Q x (EA) x {I,N,D}
donde los símbolos I, N y D representan los movimientos del 
cabezal de lectoescritura sobre la cinta, hacia la izquierda, nulo y 
hacia la derecha respectivamente. 
El dominio no incluye a F, es decir que los estados finales son de 
parada. Todos los símbolos se pueden leer y escribir, pero 
inicialmente solo hay espacios en blanco y una secuencia de 
símbolos de entrada.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MÁQUINA DE TURING (MT):
De acuerdo a la hipótesis de Turing, el lenguaje universal 
E
* queda dividido en tres subconjuntos:
➢ Todas las palabras aceptadas por la MT.
➢ Todas las palabras rechazadas por la MT.
➢Aquellas palabras que hacen que la MT no se 
detenga, o sea que no se aceptan ni se rechazan.
Esto implica que todo LI tiene una MT que es capaz de 
reconocerlo, pero que su complemento NO SIEMPRE tendrá 
una MT que lo acepte. 
E
*
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MÁQUINA DE TURING (MT):
Representación formal de la función de transición:
Tabla de Transición
Grafo de Transición
msq’eq
Mov.Sím.Sal.Est.Nue.Sím.Ent.Est.Act.
Fq0 q’q
(e,s,m)
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MÁQUINA DE TURING (MT):
En ambos casos se representa cada pareja estímulo/ /reacción, 
compuesta por el par (estado actual, símbolo de entrada) y la terna 
(estado nuevo, símbolo de salida, movimiento) respectivamente.
Un aspecto importante a tener en cuenta en cada modelo aceptor de 
lenguaje, es la característica determinista o no-determinista de las 
funciones de control. Que se refiere a la posibilidad de que dicha 
relación tenga o no varias alternativas de transición para un mismo 
estímulo. Es decir que se dice determinista cuando se trata 
estrictamente de una función desde el punto de vista matemático.
En el caso de la MT se puede afirmar que se trata de un modelo 
DETERMINISTA por naturaleza. Es decir que para toda MT No-
Determinista existe una MT determinista equivalente.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE MT:
MT=  Q , ΣE , ΣA , q0 , F , f 
Q = { 1, 2, 3, 4, 5, 6, 7, 8 } 
E = { a, b } A = {  } 
q0 = 1 F = { 8 }
Cabe destacar que esta MT es determinista en contraposición del 
modelo AP correspondiente al mismo lenguaje, que como vimos 
tiene solución únicamente No-Determinista.
Lenguajes, Gramáticas y 
Modelos Generales.
Esta MT acepta el LIC 
Palíndromo sobre el 
alfabeto de símbolos {a, b}.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE MT:
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE MT:
G
R
A
F
O
 D
E
 T
R
A
N
S
IC
IÓ
N
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
CONFIGURACIÓN DE UNA MT:
Una descripción instantánea de una MT requiere las siguientes 
especificaciones:
✓ Estado actual de la MT.
✓ Contenido de la cinta.
✓ Posición del cabezal. 
Esta terna se conoce como CONFIGURACIÓN de la MT y vamos a 
representar con la secuencia de símbolos que hay en la cinta antes 
de la posición del cabezal (i), seguida del estado actual (qk ), seguida 
de la secuencia que hay desde la posición del cabezal y delimitada 
por espacios en blanco: c1...ci-1qkci...cn
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
SECUENCIA DE CONFIGURACIÓN DE UNA MT:
Con el objetivo de representar la respuesta de una MT ante 
una secuencia de entrada, vamos a definir el operador ├─ 
de transformación directa de una configuración en otra: 
C1 ├─ C2 , que implica el pasaje de la configuración C1 a 
la configuración C2 mediante la aplicación de la función de 
transición una sola vez; y en caso de que se realicen varios 
pasos se indica con la nomenclatura: C1 ├─* C2
Una sucesión de varias configuraciones consecutivas se 
llama SECUENCIA DE CONFIGURACIÓN de la MT. 
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
LENGUAJE ACEPTADO POR UNA MT:
Se define el lenguaje aceptado por una MT como el 
conjunto de palabras que partiendo de una configuración 
inicial, llegan a una configuración que contiene un estado 
final de la MT. Formalmente se representa como:
L(MT) = {w / wE
*  q0w├─ * 1qF2  qF F }
Por otro lado, todas las palabras que partiendo de una 
configuración inicial llegan a una configuración donde se 
produce un bloqueo; se dice que son rechazadas por la MT.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE SECUENCIA DE CONFIGURACION:
Consideremos el ejemplo de MT anterior y las palabras:
w1 = aba , w2 = bb , w3 =  , w4 = ab
Las secuencias de configuración correspondientes serían:
1) 1aba ├─ 2ba ├─ b2a ├─ ba2 ├─ b3a
├─ 4b├─ 4b ├─ 1b ├─ 5
├─ 6 ├─ 8 final/acepta
2) 1bb ├─ 5b ├─ b5 ├─ 6b ├─ 7
├─ 1├─ 8 final/acepta
3) 1 ├─ 8 final/acepta
4) 1ab ├─ 2b ├─ b2 ├─ 3b bloqueo/rechazo
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATA LINEALMENTE LIMITADO (ALL):
El Autómata Linealmente Limitado es una MT que tiene restringida la 
longitud de su cinta, la cual se limita a la longitud de la secuencia de 
entrada inicial. Este modelo matemático abstracto representa la solución 
del problema de aceptación de lenguajes de Tipo 1 o LDC. 
Para su mejor comprensión lo representaremos con el siguiente esquema:
  e1 e2
••• ••• en-1 en 
Cinta Finita
Control
Cabezal de Lec./Esc.
0 1
2
X
3
.
. .Es
ta
d
o
s
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATA LINEALMENTE LIMITADO (ALL):
El modelo es idéntico a la MT, salvo que dispone de una cinta 
finita. Al comienzo se escribe en la cinta la palabra que se 
desea analizar (ei), el cabezal de lecto-escritura se encuentra 
sobre la posición del primer símbolo de dicha palabra; en 
estas circunstancias se dice que el control se encuentra en el 
estado inicial. Automáticamente se coloca en los extremos de 
esta secuencia los símbolos especiales “” y “” a la izquierda 
y derecha respectivamente, los mismos actúan como límites 
para el desplazamiento del cabezal; de tal modo que no se 
puede desplazar más a la izquierda de “” ni más a la derecha 
de “”.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATA LINEALMENTE LIMITADO (ALL):
Definición formal de un Autómata Linealmente Limitado:
ALL =  Q , ΣE , ΣA , q0 , F , f 
Q : Conjunto finito y no vacío de estados.
ΣE: Alfabeto de símbolos de entrada.
ΣA: Alfabeto de símbolos auxiliares (incluye a “” y a “”).
q0 : Estado inicial (perteneciente a Q)
F : Conjunto de estados finales (incluido en Q)
f : Función de control o transición.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
AUTÓMATA LINEALMENTE LIMITADO (ALL):
La función de transición se define como:
f : (Q-F) x (EA)  Q x (EA) x {I,N,D}
El dominio no incluye a F, es decir que los estados finales son de 
parada. Todos los símbolos se pueden leer y escribir, pero 
inicialmente solo está la secuencia de símbolos de entrada 
delimitada por los símbolos “” y “”.
f(q ,  ) = (q’ ,  , D) 
f(q ,  ) = (q’ ,  , I)
 q  (Q-F)
 q’ Q 
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
En el caso de los ALL el lenguaje universal de símbolos de 
entrada E* , queda dividido en dos subconjuntos:
Es decir que para todo LDC existe un ALL que es capaz de 
aceptarlo y a la vez rechazar a su complemento. Lo que 
significa que el problema de reconocimiento de LDC siempre 
tiene solución con este modelo.
E
*
➢Todas las palabras aceptadas por el ALL.
➢Todas las palabras rechazadas por el ALL.
AUTÓMATA LINEALMENTE LIMITADO (ALL):
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
Representación formal de la función de transición:
Tabla de Transición
Grafo de Transición
msq’eq
Mov.Sím.Sal.Est.Nue.Sím.Ent.Est.Act.
Fq0 q’q
(e,s,m)
AUTÓMATA LINEALMENTE LIMITADO (ALL):
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
En ambos casos se representa cada pareja estímulo/ /reacción, 
compuesta por el par (estado actual, símbolo de entrada) y la terna 
(estado nuevo, símbolo de salida, movimiento) respectivamente.
Al igual que todos los modelos, la relación de transición puede ser 
determinista o no-determinista. 
Algunos autores afirman que el ALL es DETERMINISTA por 
naturaleza, es decir que para todo ALL No-Determinista existe un 
ALL Determinista equivalente. Otros lo ponen en duda, lo cierto es 
que hasta el momento no se pudo demostrar lo contrario. Por lo 
tanto a los fines prácticos asumiremos que si tiene esta propiedad.
AUTÓMATA LINEALMENTE LIMITADO (ALL):
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
ALL =  Q , ΣE , ΣA , q0 , F , f 
Q = { I, A, B, C, D, F } 
E = { a, b } A = {  ,  , X } 
q0 = I F = { F }
Este ALL acepta el lenguaje IGUAL sobre el alfabeto {a, b}, 
que contiene todas las palabras con igual cantidad de un 
símbolo que del otro.
EJEMPLO DE ALL:
La función de control f es 
determinista y se representa 
con su tabla y grafo de 
transición.
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE ALL:
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE ALL:
G
R
A
F
O
 D
E
 T
R
A
N
S
IC
IÓ
N
I
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLO DE ALL:
Los conceptos de CONFIGURACIÓN, SECUENCIA DE 
CONFIGURACIÓN y LENGUAJE ACEPTADO por un 
ALL, son similares a los de una MT.
En este ejemplo de ALL tenemos las siguientes secuencias de 
configuración para las palabras: w1 = ab , w2 = b
1) Iab ├─ AXb ├─ BXb ├─ XBb ├─ CXX
├─ CXX ├─ IXX ├─ XIX ├─ XXI ├─ XDX
├─ DXX ├─ DXX ├─ FXX final/acepta
2) Ib ├─ bI ├─ Db bloqueo/rechaza
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
MT TRANSFORMADORA DE SECUENCIAS:
Se puede ver a la MT como un modelo general de 
procesamiento de datos, capaz de realizar cualquier 
transformación sobre una secuencia inicial y obtener una 
secuencia final que cumpla ciertas condiciones.
La secuencia inicial representa los datos de entrada y la 
secuencia final los datos de salida o resultado de un 
problema algorítmico.
En estos casos la aceptación de la secuencia inicial se puede 
interpretar como la validación de los datos de entrada, ya 
que si no son válidos se rechazan. 
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLOS DE MT CALCULADORA:
1) El sistema de numeración unario utiliza secuencias de 
símbolos “1” para representar los números enteros 
positivos y la palabra vacía “” para el número cero.
Número Decimal Número Unario
0 
1 1
2 11
3 111
4 1111
5 11111
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLOS DE MT CALCULADORA:
1.1) MT que incrementa un número unario:
Q = { 1, 2, 3 } , A = {  } , E = { 1 } , q0= 1 , F= { 3 }
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLOS DE MT CALCULADORA:
1.2) MT que suma dos números unarios separados por +:
Q = { 1, 2, 3, 4, 5 } , A = {} , E = {1, +} , q0= 1 , F= { 5 }
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLOS DE MT CALCULADORA:
2) MT que incrementa en uno un número binario natural:
Q={1, 2, 3, 4, 5, 6} , A={} , E={0, 1} , q0=1 , F={6}
Para comprender la lógica que utiliza este modelo se puede 
asociar con los estados los siguientesnemotécnicos:
1:Inicio 2:Suma 3:Con acarreo 
4:Sin acarreo 5:Desborde 6:Final
Lenguajes, Gramáticas y 
Modelos Generales.
ING. JORGE BUABUD
U.T.N. – F.R.T. 
S. y S. de los L.
EJEMPLOS DE MT CALCULADORA:
Lenguajes, Gramáticas y 
Modelos Generales.