grmatica

Teoría de Autómatas I
Máquinas de Turing y lenguajes estructurados por frases

-1-

MÁQUINAS DE TURING Y
LENGUAJES ESTRUCTURADOS POR FRASES
MÁQUINAS DE TURING
- Son máquinas teóricas capaces de aceptar lenguajes generados por gramáticas
estructuradas por frases.
- Una máquina de Turing tiene una cabeza de lectura/escritura que avanza
bidireccionalmente por una cinta infinita por laderecha.
• Entrada: contenido inicial de la cinta.
• Salida: contenido final de la cinta.
- Símbolos de cinta:
• Símbolos de entrada: Σ
• Símbolos de cinta: Γ ⊇ Σ
- Transiciones: δ(p,x) = (q,y) donde:
• p,q: estados
• x ∈ Σ : símbolo de entrada
• y ∈ Γ ∪ {L,R} : símbolo de cinta o desplazamiento
- En una transición, la máquina de Turing lee un símbolo de la cinta, cambia de estado yescribe un símbolo o efectúa un desplazamiento a izquierda o derecha.
- Ejemplo de diagrama de transiciones

- Proceso de reconocimiento de una cadena:
• Se parte del estado inicial, y la cinta contiene símbolos de entrada.
• Se efectúan las transiciones pertinentes según la función de transición.
• Si la cabeza lectora rebasa el extremo izquierdo de la cinta, la cadena es
rechazada y el procesotermina (terminación anormal).
• Si la máquina alcanza el estado de parada, la cadena es aceptada.

Teoría de Autómatas I
Máquinas de Turing y lenguajes estructurados por frases

-2-

- MT: M(S,Σ,Γ,δ,i,h)
• S: conjunto finito de estados.
• Σ: alfabeto de entrada.
• Γ: alfabeto de símbolos de cinta.
• δ: función de transición (determinista): S x Γ → S x (Γ∪{L,R}).
• i: estado inicial.• h: estado de aceptación o de parada.
- En general, las máquinas de Turing son deterministas.
TESIS DE TURING
El poder computacional de una máquina de Turing es tan grande como el de cualquier
sistema computacional posible.
COMBINACIÓN DE MÁQUINAS DE TURING
- Pasos:
1. Eliminar la característica de inicio de los estados iniciales de todas las máquinas,
excepto de la primera.
2.Eliminar la característica de parada de todas las máquinas, e incluir un nuevo estado
de parada.
3. Para cada estado de parada p y para cada x ∈ Γ:
a) Si la nueva máquina se debe detener al llegar a p con x, añadir un arco x/x de p al
nuevo estado de parada.
b) Si al llegar al estado p con el símbolo actual x la máquina compuesta debe
transferir el control a la máquina M(S,Σ,Γ,δ,i,h), dibujar unarco con etiqueta x/z
de p al estado q de M tal que δ(i,x) = (q,z).
CONSTRUCCIÓN MODULAR DE MÁQUINAS DE TURING
- Construcción de máquinas de Turing complejas a partir de bloques elementales.
x
- Transferencia de control entre máquinas: → M1  → M2

- Transferencia de control con varios símbolos:
x, y, z
w
w
→ M1  →} → M2 → M3


Teoría de Autómatas I
Máquinas de Turing ylenguajes estructurados por frases

Bloques de construcción básicos

- Bloques más complejos

-3-

Teoría de Autómatas I
Máquinas de Turing y lenguajes estructurados por frases

-4-

Teoría de Autómatas I
Máquinas de Turing y lenguajes estructurados por frases

-5-

EVALUACIÓN DE CADENAS
- Aceptación de una cadena
• Situación inicial:
∗ Cabeza en el extremo izquierdo de lacinta.
∗ La cadena de entrada empieza en la segunda posición de la cinta.
• Situación final:
∗ Máquina de Turing en estado de parada.
- Lenguaje aceptado por una máquina de Turing: conjunto de cadenas que acepta.
- Una máquina de Turing puede escribir un mensaje de aceptación si acepta una cadena.
• Mensaje de aceptación: ∆Y∆∆∆
- Símbolos especiales
• #: extremo izquierdo de la cinta
• *:extremo derecho de la porción alterada de la cinta
- Si la máquina es M, la máquina final es:

• M0 es igual que M, salvo que:
∗ Si M0 alcanza #, se desplazará una casilla a la izquierda (terminación
anormal)
∗ Si M0 alcanza *, debe desplazarlo un lugar a la derecha ejecutando
→ R * L∆

Teoría de Autómatas I
Máquinas de Turing y lenguajes estructurados por frases

-6-

Máquinas de...