Maquinas con dos (o mas) cintas infinitas

Maquinas con dos (o mas) cintas infinitas

[pic 1]

1.Cada máquina estándar es una máquina con dos cintas que no usa la segunda cinta.

2.Simular la máquina de M de dos cintas en una máquina N con una cinta:

• M transita en función del estado actual y de los dos símbolos leídos (f(q.a.b)=(p,e,c,L,R)) y escribe dos nuevos símbolos en las cintas y mueve las dos cabezas de lectura/escritura.
• ¿Cómo se pueden simular los movimientos de la máquina M?

Idea:

        Representar el contenido de dos (o más) cintas en la máquina N en una cinta con varios tramos o pistas.

        [pic 2]

                                                                                                                                               Tramo 1

        Tramo 2

[pic 3]

Los estados de la máquina N tiene la forma [q,t1,t2,s1,s2] y almacenan :      

• q: el estado actual de la máquina M
• t1 y t2: los símbolos leídos en las pistas 1 y 2
• s1 y s2: unos símbolos que indican en que dirección de la cabeza se encuentran las marcas para el tramo 1 y 2 (L- izquierda R-derecha .-en esta)

Inicialmente N arranca con la cinta dada arriba en el estado [q0, ∙,∙,∙,∙ ]q0 es el estado inicial de M) y sucesivamente hace los mismos movimientos que la máquina M.

Para simular un movimiento de M, N hace lo siguiente:

• en función de s1 busca la marca para el tramo 1 y copia el símbolo marcado en t1 (deja este símbolo y su marca)
• hace lo mismo para el tramo 2
• suponemos que N esta en estado (r,a,b,?,?) entonces se simula el movimiento f(r,a,b)=(p,e,c,X,Y) de M

• busca el símbolo marcado en el tramo 1 , lo cambia por la e
• quita la marca de este tramo y lo pone en la posición que indica X (a la derecha o a la izquierda)
• hace lo mismo para el tramo 2 (cambiando b por c)
• cambia el estado de r a p (si p es final -> para)

Ha realizado el movimiento y empieza de nuevo.

Importante: en todo momento tiene que actualizar s1 y s2

Maquinas no deterministas

Maquinas no deterministas: M=(Γ,Σ,∙,Q,q0,f,F)

F es aplicación de Q x Γ en el conjunto de las partes Q x Γ x {I,D}

1.Cada maquina estándar es también una maquina no determinista (que no usa el concepto de no determinismo)

2. Simulación de una maquina no determinista M con una determinista N:

Idea: f(q,a)={(p,b,R),(r,c,L)}[pic 4]

1. Para cada posibilidad distinta crea un nuevo par de tramos en la cinta

Camino 1

                                                                Camino 2

1. Realiza en cada par de tramos un movimiento [pic 5]

Camino 1

Camino 2

1. Si uno de los estados alcanzados es final, entonces para.
2. En caso contrario repite los pasos 1 y 2 para todos los pares de tramos que haya

La maquina N simula una búsqueda en amplitud.

Obviamente, esta N tiene un “overhead” (que no se ha especializado).

13.3. MT para reconocer lenguajes

Ejemplo 1

Alfabeto:Σ={0,1} Lenguaje sobre Σ:L(0*)

Construimos M=({∙,0,1},{1,1},∙,{q0,q1},q0,f,{qq}), donde

f(q0,0)=(q0,0,R)

f(q0, ∙)=(q0, ∙,R)

q0000|-0 q000 |- 00 q00|-000 q0 ∙|-000∙ q1∙(para en estado final)

...